Big Number Arithmetic C Program The goal is to perform several multiplication functions/algorithims using unlimited length...
Big Number Arithmetic C Program
The goal is to perform several multiplication functions/algorithims using unlimited length digits (BigInts) and compare their execution times.
The program requires a header file which includes all functions needed by the .c file.
Required functions:
ClassicalMult (bigInt A, bigInt B, int base) - this function multiplies two big integers using the classical multiplication algorithim.
KaratsubaMult (bigInt A, bigInt B, int base) - this function multiplies two big integers using the Karatsuba multiplication algorithim.
ToomMult (bigInt A, bigInt B, int base) - this function multiplies two big integers using the Toom3 multiplication algorithim.
CompareAlgorithms(charfirstalgorithm, charfirstalgorithm, int size) - Compares two of the multiplication algorithims using size_digit random numbers
- Return Values for this function are the execution time for each algorithim and the subtraction of the results of the two algorithms
- pass "c" for classical, "k" for karatsuba, or "t" for Toom-Cook
Large_Rnd (bigInt size) - creates a size_digit random number (BigInt)
Timer () - measures the execution time
PrintBI (bigInt A) - prints a BigInt to stdout
GetBI(bigInt A) - reads in a bigInt from stdin
menu(int item) - this is in main()
- The following options should be included in the menu and all
of the required functions also should be created.
1-Adding two big integers (two options: user mode, random
mode)
2-Multiplication of two big integers using classic algorithm (two
options: user mode, random mode)
3-Multiplication of two big integers using Karatsuba algorithm (two
options: user mode, random mode)
4-Multiplication of two big integers using Toom-Cook algorithm (two
options: user mode, random mode)
5-Comparing the execution time ofmultiplication algorithms (two
options: user mode, random mode)
6-Testing the correctness of algorithms
7-Continue or quit
Any helper or auxillary functions should also be included in the header .h file and .c file.
such as addition, subtraction, base conversion, data type conversion, etc
Test Data
Choose one pair of 1000-digit random numbers. Compare the execution time of all of the multiplication algorithms and show the results.
The final result should be the average of at least 10 times
Comments Should explain the algorithms shortly and precisely. Any assumptions should be explained clearly.
*The default base is 10
**edit**
I got working functions for printBI, Large_Rnd, and the addition.
I just really need help with all the multiplication and compareAlgorithm functions
Homework Answers
Provided C++ code done as per your requirements.
- "Screenshot of the program code" for better understanding.
- "Code to copy" for run the program in your IDE.
Screenshot of the code:
main.c:
BigArithmetic.h:
Sample Output:
Code to copy:
main.c:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "BigArithmetic.h"
#define RANDOM_LENGTH 100
// function to print the menu.
void print_menu(void)
{
putchar('\n');
printf("1. Addition of two big integers");
printf("\n2. Multiplicaiton of two ",
"big integers (Classical)");
printf("\n3. Multiplicaiton of two",
" big integers (Karatsuba)");
printf("\n4. Multiplicaiton of two",
" big integers (Toom-Cook)");
printf("\n5. Compare the execution ",
"time of multiplication algorithms");
printf("\n6. Test the correctness of algorithms");
printf("\n7. Print menu\n");
printf("8. Quit\n");
putchar('\n');
}
// Main function
int main(void)
{
// preefined functuion to generate the random value.
srand(time(NULL));
// Declare the variable and allocate the memory.
bigInt *big_num1 =
(bigInt *)malloc(sizeof(bigInt));
bigInt *big_num2 =
(bigInt *)malloc(sizeof(bigInt));
bigInt *big_num_sum =
(bigInt *)malloc(sizeof(bigInt));
bigInt *big_num_product =
(bigInt *)malloc(sizeof(bigInt));
int valid_response = 0;
int menu_selection = 7;
char mode_selection;
// Timer variables.
clock_t begin;
clock_t end;
// initialization of the
// multiplication variable.
big_num_product->digits[0] = '0';
big_num_product->digits[1] = '\0';
// use while to run all the part
// of the quaetion.
while (menu_selection != 8)
{
// Call the aprint_menu function
//to print the options.
print_menu();
printf("Please make a selection: ");
scanf(" %d", &menu_selection);
switch (menu_selection)
{
// addition of the numbers.
case 1:
// check the valid response.
while (valid_response == 0)
{
// promt the user to select
//the mode of the execution.
printf("User mode or random mode? (u/r): ");
scanf(" %c", &mode_selection);
mode_selection = tolower(mode_selection);
if (mode_selection == 'u' ||
mode_selection == 'r')
{
valid_response = 1;
}
else
{
printf("Invalid response.",
" Please enter 'u' or 'r'.\n");
}
}
valid_response = 0;
putchar('\n');
// if the selection mode is user.
if (mode_selection == 'u')
{
printf("Enter a big integer:\n");
GetBI(big_num1);
printf("Enter another big integer:\n");
GetBI(big_num2);
addition(big_num1, big_num2, big_num_sum);
printf("The sum is:\n");
PrintBI(big_num_sum);
}
// if te selection mode is random.
else
{
Large_Rnd(big_num1, RANDOM_LENGTH);
Large_Rnd(big_num2, RANDOM_LENGTH);
begin = clock();
addition(big_num1, big_num2, big_num_sum);
end = clock();
printf("Big integer 1:\n");
PrintBI(big_num1);
printf("\nBig integer 2:\n");
PrintBI(big_num2);
printf("\nThe sum is:\n");
PrintBI(big_num_sum);
printf("\nExecution time: %f seconds\n",
Timer(begin, end));
}
break;
// Classical multiplicaiton
case 2:
// check the valid response.
while (valid_response == 0)
{
printf("User mode or random mode? (u/r): ");
scanf(" %c", &mode_selection);
mode_selection = tolower(mode_selection);
if (mode_selection == 'u'
|| mode_selection == 'r')
{
valid_response = 1;
}
else
{
printf("Invalid response.",
" Please enter 'u' or 'r'.\n");
}
}
valid_response = 0;
putchar('\n');
// start the execution of the user mode.
if (mode_selection == 'u')
{
printf("Enter a big integer:\n");
GetBI(big_num1);
printf("Enter another big integer:\n");
GetBI(big_num2);
big_num_product = ClassicalMult
(big_num1, big_num2,
big_num_product, 10);
printf("The product is:\n");
PrintBI(big_num_product);
}
// start the calculation of the random mode.
else
{
Large_Rnd(big_num1, RANDOM_LENGTH);
Large_Rnd(big_num2, RANDOM_LENGTH);
begin = clock();
big_num_product = ClassicalMult
(big_num1, big_num2, big_num_product, 10);
end = clock();
printf("Big integer 1:\n");
PrintBI(big_num1);
printf("\nBig integer 2:\n");
PrintBI(big_num2);
printf("\nThe product is:\n");
PrintBI(big_num_product);
printf("\nExecution time: %f seconds\n",
Timer(begin, end));
}
break;
// Karatsuba Multiplication
case 3:
// check for the valid response.
while (valid_response == 0)
{
printf("User mode or random mode? (u/r): ");
scanf(" %c", &mode_selection);
mode_selection = tolower(mode_selection);
if (mode_selection == 'u'
|| mode_selection == 'r')
{
valid_response = 1;
}
else
{
printf("Invalid response.",
" Please enter 'u' or 'r'.\n");
}
}
valid_response = 0;
putchar('\n');
// User mode
if (mode_selection == 'u')
{
printf("Enter a big integer:\n");
GetBI(big_num1);
printf("Enter another big integer:\n");
GetBI(big_num2);
big_num_product = karatsubaMult
(big_num1, big_num2, big_num_product, 10);
printf("The product is:\n");
PrintBI(big_num_product);
}
// Random mode
else
{
Large_Rnd(big_num1, RANDOM_LENGTH);
Large_Rnd(big_num2, RANDOM_LENGTH);
begin = clock();
big_num_product = karatsubaMult
(big_num1, big_num2, big_num_product, 10);
end = clock();
printf("Big integer 1:\n");
PrintBI(big_num1);
printf("\nBig integer 2:\n");
PrintBI(big_num2);
printf("\nThe product is:\n");
PrintBI(big_num_product);
printf("\nExecution time: %f seconds\n",
Timer(begin, end));
}
break;
// Toom-Cook Multiplication
case 4:
while (valid_response == 0)
{
printf("User mode or random mode? (u/r): ");
scanf(" %c", &mode_selection);
mode_selection = tolower(mode_selection);
if (mode_selection == 'u'
|| mode_selection == 'r')
{
valid_response = 1;
}
else
{
printf("Invalid response.",
" Please enter 'u' or 'r'.\n");
}
}
valid_response = 0;
putchar('\n');
// User mode
if (mode_selection == 'u')
{
printf("Enter a big integer:\n");
GetBI(big_num1);
printf("Enter another big integer:\n");
GetBI(big_num2);
big_num_product = ToomMult(big_num1,
big_num2, big_num_product, 10);
printf("The product is:\n");
PrintBI(big_num_product);
}
// Random mode
else
{
Large_Rnd(big_num1, RANDOM_LENGTH);
Large_Rnd(big_num2, RANDOM_LENGTH);
begin = clock();
big_num_product = ToomMult
(big_num1, big_num2, big_num_product, 10);
end = clock();
printf("Big integer 1:\n");
PrintBI(big_num1);
printf("\nBig integer 2:\n");
PrintBI(big_num2);
printf("\nThe product is:\n");
PrintBI(big_num_product);
printf("\nExecution time: %f seconds\n",
Timer(begin, end));
}
break;
// Compare Execution Times
case 5:
break;
// Test the correctness of the algorithms
case 6:
break;
// Print menu
case 7:
print_menu();
break;
// Quit
case 8:
break;
default:
printf("Please enter a valid selection ");
break;
}
}
// Free the memory of the variable.
free(big_num1);
free(big_num2);
free(big_num_sum);
free(big_num_product);
return 0;
}
BigArithmetic.h:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
// define some variable.
#ifndef BIGARITHMETIC_H
#define BIGARITHMETIC_H
#define MAX_LENGTH 2000
// declare the structure.
typedef struct
{
char digits[MAX_LENGTH];
} bigInt;
// function to get the big integer.
void GetBI(bigInt *A)
{
scanf(" %s", A->digits);
}
// function to print the big integer.
void PrintBI(bigInt *A)
{
for (int i = 0; i < strlen(A->digits); i++)
{
putchar(A->digits[i]);
}
putchar('\n');
}
// fucntion to generate the large random number.
void Large_Rnd(bigInt *A, int size)
{
for (int i = 0; i < size; i++)
{
A->digits[i] = (rand() % 10) + 48;
}
A->digits[size] = '\0';
}
// fucntion to find the time of the execution.
double Timer(clock_t begin, clock_t end)
{
return (double)(end - begin) / CLOCKS_PER_SEC;
}
// fucntion to find the max of the number.
int max(int A, int B)
{
if (A > B)
{
return A;
}
else
{
return B;
}
}
// function to padding the big integer value.
void pad_bigInt_head(bigInt *A, int padding)
{
for (int index = strlen(A->digits) + 1; index >= 0; --index)
{
A->digits[index + padding] = A->digits[index];
A->digits[index] = '0';
}
}
// function to padding the big integer value.
void pad_bigInt_tail(bigInt *A, int padding)
{
int old_length = strlen(A->digits);
int new_length = strlen(A->digits) + padding;
A->digits[new_length] = '\0';
for (int i = old_length; i < new_length; ++i)
{
A->digits[i] = '0';
}
}
// fucntion to trim.
void trim_leading_zeroes(bigInt *A)
{
int diff = 0;
int i;
while (A->digits[diff] == '0')
{
++diff;
}
for (i = 0; A->digits[i] != '\0'; ++i)
{
A->digits[i] = A->digits[i + diff];
}
A->digits[i + 1] = '\0';
}
// function to adding the values.
void addition(bigInt *A, bigInt *B, bigInt *C)
{
int carry = 0;
int sizeA = strlen(A->digits);
int sizeB = strlen(B->digits);
int size_diff = abs(sizeA - sizeB);
if (sizeA == sizeB)
{
;
}
else if (sizeA < sizeB)
{
pad_bigInt_head(A, size_diff);
}
else
{
pad_bigInt_head(B, size_diff);
}
int len_of_terms = strlen(A->digits);
for (int i = 0; i <= len_of_terms; ++i)
{
C->digits[i] = '0';
}
C->digits[len_of_terms + 1] = '\0';
for (int index = len_of_terms - 1; index >= 0; --index)
{
C->digits[index + 1] = (((carry + ((A->digits[index]
+ B->digits[index]) - 96)) % 10) + 48);
carry = ((A->digits[index] + B->digits[index]) - 96) / 10;
}
C->digits[0] = (carry + 48);
trim_leading_zeroes(C);
}
// fucntion to multiplication.
bigInt *ClassicalMult(bigInt *A, bigInt *B, bigInt *product, int base)
{
bigInt *temp_bigInt = (bigInt *)malloc(sizeof(bigInt));
int carry = 0;
int sizeA = strlen(A->digits);
int sizeB = strlen(B->digits);
int size_diff = abs(sizeA - sizeB);
if (sizeA == sizeB)
{
;
}
else if (sizeA < sizeB)
{
pad_bigInt_head(A, size_diff);
}
else
{
pad_bigInt_head(B, size_diff);
}
int len_of_terms = strlen(A->digits);
if (len_of_terms == 1)
{
temp_bigInt->digits[2] = '\0';
temp_bigInt->digits[1] = ((((A->digits[0] * B->digits[0]) - 2304)
- (48 * (A->digits[0] + B->digits[0] - 96))) % 10) + 48;
temp_bigInt->digits[0] = ((((A->digits[0] * B->digits[0]) - 2304)
- (48 * (A->digits[0] + B->digits[0] - 96))) / 10) + 48;
trim_leading_zeroes(temp_bigInt);
addition(product, temp_bigInt, product);
return product;
}
else
{
int m = len_of_terms / 2;
bigInt *a = (bigInt *)malloc(sizeof(bigInt));
bigInt *b = (bigInt *)malloc(sizeof(bigInt));
bigInt *c = (bigInt *)malloc(sizeof(bigInt));
bigInt *d = (bigInt *)malloc(sizeof(bigInt));
bigInt *ac = (bigInt *)malloc(sizeof(bigInt));
bigInt *ad = (bigInt *)malloc(sizeof(bigInt));
bigInt *bc = (bigInt *)malloc(sizeof(bigInt));
bigInt *bd = (bigInt *)malloc(sizeof(bigInt));
bigInt *adbc_sum = (bigInt *)malloc(sizeof(bigInt));
for (int i = 0; i < m; ++i)
{
a->digits[i] = A->digits[i];
b->digits[i] = A->digits[m + i];
c->digits[i] = B->digits[i];
d->digits[i] = B->digits[m + i];
}
a->digits[m] = '\0';
b->digits[m] = '\0';
c->digits[m] = '\0';
d->digits[m] = '\0';
ac = ClassicalMult(a, c, product, 10);
ad = ClassicalMult(a, d, product, 10);
bc = ClassicalMult(b, c, product, 10);
bd = ClassicalMult(b, d, product, 10);
addition(ad, bc, adbc_sum);
pad_bigInt_tail(ac, (2 * m));
pad_bigInt_tail(adbc_sum, m);
addition(product, ac, product);
addition(product, adbc_sum, product);
addition(product, bd, product);
return product;
}
}
// function to multiply the numbers.
bigInt *karatsubaMult(bigInt *A, bigInt *B, bigInt *product, int base)
{
return product;
}
// function to multiply the numbers.
bigInt *ToomMult(bigInt *A, bigInt *B, bigInt *product, int base)
{
return product;
}
// function to compare then algorithm.
void CompareAlgorithms(char firstAlgorithm, char secondAlgorithm, int size)
{
}
#endif
Add Answer to:
Big Number Arithmetic C Program
The goal is to perform several multiplication
functions/algorithims using unlimited length...
Using c++.. 1. Write a program to find the sum(), Subtraction(), Multiplication(), Division() operations using Switch...
Using c++.. 1. Write a program to find the sum(), Subtraction(), Multiplication(), Division() operations using Switch statement and functions. 2. Write a program to find the summation of N numbers. Use two functions. One function will take the input from user and the other will perform the summation from 1 to N. 3. Write a program to find the factorial of a number. Use two functions. One function will take the input from user and the other will perform the...
Develop a flowchart and then write a menu-driven C++ program that uses several FUNCTIONS to solve...
Develop a flowchart and then write a menu-driven C++ program that uses several FUNCTIONS to solve the following program. -Use Microsoft Visual C++ .NET 2010 Professional compiler using default compiler settings. -Use Microsoft Visio 2013 for developing your flowchart. -Adherence to the ANSI C++ required -Do not use <stdio.h> and <conio.h>. -Do not use any #define in your program. -No goto statements allowed. Upon execution of the program, the program displays a menu as shown below and the user is prompted to make a selection from the menu....
Matrix Multiplication with Threads - C/C++ **Please read entire question before answering** In this assignment you...
Matrix Multiplication with Threads - C/C++ **Please read entire question before answering** In this assignment you will use the Pthreads library to write a program that multiplies two square arrays and compare the difference between the imperative and parallel implementations of this algorithm. Use the matrix mulltiplication algorithm. Write a program that contains three functions: (1) A function that has an integer as a parameter and returns a pointer to square array of integers (i.e. both dimensions should be equal)....
Please solve the program in C++(Recursive) Write a function called factorialIterative(). This function should take a...
Please solve the program in C++(Recursive) Write a function called factorialIterative(). This function should take a single BIG integer (bigint) as its parameter n, and it will compute the factorial n! of the value and return it as its result (as a bigint). Write this functions using a loop (do not use recursion). 2. Write the factorial function again, but using recursion. Call this function factorialRecursive(). The function takes the same parameters and returns the same result as described in...
PLEASE HELP!!! C PROGRAMMING CODE!!! Please solve these functions using the prototypes provided. At the end...
PLEASE HELP!!! C PROGRAMMING CODE!!!
Please solve these functions using the prototypes provided. At
the end please include a main function that tests the functions
that will go into a separate driver file.
Prototypes int R_get_int (void); int R_pow void R Jarvis int start); void R_fill_array(int arrayll, int len); void R_prt_array (int arrayl, int len) void R-copy-back (int from[], int to [], int len); int R_count_num (int num, int arrayll, int len) (int base, int ex) 3. Build and run...
C Programming Language The operation of multiplication for positive integers can be expressed as: A.B=2...
C Programming
Language
The operation of multiplication for positive integers can be expressed as: A.B=2 1 A for (A+[A.(B-1)] B=1 for B>1 Task 1 (for 1 point) is to write a program that will read and print on the screen the values of two integers (A and B) given by user as command line parameters. Task 2 (for 1 point) is to write a program that will calculate the result of the multiplication of two integers. It should print...
Write a C++ program In this assignment you will complete the definition of two functions that...
Write a C++ program In this assignment you will complete the definition of two functions that implement the repeated squaring algorithm described in the Stamp textbook on pages 98-99. Note that your implementation should not use the pow() function, the powl() functions, or any other built-in exponentiation functions. program4-driver.cpp - This file contains a completed main() function that serves as the driver to parse the command line, pass the values to the powerModN() function, and print the result. Make no...
Practical 5: Write a program that implements several sorting algorithms, and use it to demonstrate the comparative perfo...
Practical 5: Write a program that implements several sorting
algorithms, and use it to demonstrate the comparative performance
of the algorithms for a variety of data sets.
Need Help With this Sorting Algorithm task for C++
Base Code for sorting.cpp is given.
The header file is not included in this. Help would be much
appreciated as I have not started on this due to personal
reasons
#include <cstdlib>
#include <iostream>
#include <getopt.h>
using namespace std;
long compares; // for counting...
Write a C program, containing the following functions. Function int recursive_fibonacci(int n) computes and returns the...
Write a C program, containing the following functions. Function int recursive_fibonacci(int n) computes and returns the nth F(n) using recursive algorithm (i.e., recursive function call). Fibonacci numbers are defined by F(1)=F(2)=1, F(i) = F(i-1)+F(i-2), i=2,… . Function int iterative_fibonacci(int n) computes and returns the nth Fibonacci number F(n) using iterative algorithm (i.e., loop). The main function measures the memory usage and run time of iterative_fibonacci(40) and recursive_fibonacci(40), and does the comparison. To capture the execution time by millisecond, it needs...
Help with programming in C++ Phase 1 is complete, please help with phase 2. Thank you....
 {
// return the new image number
}
// use the constants MIN_NUMBER, MAX_NUMBER, do not use hard coded 1 or 8
string createFileName ( int current_number ) {
// return a filename like pictureX.gif)
Help with programming in C++
Phase 1 is complete, please help with phase 2. Thank you.
Phase 1
You must design 3 algorithms, and provide
both a flow chart and pseudo code for the
algorithms.
Algorithm descriptions:
Given an integer parameter named current_number
and two constant global variables:
const int MIN_NUMBER = 1;
const int MAX_NUMBER = 8;
Create an algorithm named forward, that will
advance ONE value through a sequence of numbers 1,
2, 3 ... MAX_NUMBER. In...
PLEASE HELP!!! C PROGRAMMING CODE!!!
Please solve these functions using the prototypes provided. At
the end please include a main function that tests the functions
that will go into a separate driver file.
Prototypes int R_get_int (void); int R_pow void R Jarvis int start); void R_fill_array(int arrayll, int len); void R_prt_array (int arrayl, int len) void R-copy-back (int from[], int to [], int len); int R_count_num (int num, int arrayll, int len) (int base, int ex) 3. Build and run...
C Programming
Language
The operation of multiplication for positive integers can be expressed as: A.B=2 1 A for (A+[A.(B-1)] B=1 for B>1 Task 1 (for 1 point) is to write a program that will read and print on the screen the values of two integers (A and B) given by user as command line parameters. Task 2 (for 1 point) is to write a program that will calculate the result of the multiplication of two integers. It should print...
Practical 5: Write a program that implements several sorting
algorithms, and use it to demonstrate the comparative performance
of the algorithms for a variety of data sets.
Need Help With this Sorting Algorithm task for C++
Base Code for sorting.cpp is given.
The header file is not included in this. Help would be much
appreciated as I have not started on this due to personal
reasons
#include <cstdlib>
#include <iostream>
#include <getopt.h>
using namespace std;
long compares; // for counting...
 {
// return the new image number
}
// use the constants MIN_NUMBER, MAX_NUMBER, do not use hard coded 1 or 8
string createFileName ( int current_number ) {
// return a filename like pictureX.gif)
Help with programming in C++
Phase 1 is complete, please help with phase 2. Thank you.
Phase 1
You must design 3 algorithms, and provide
both a flow chart and pseudo code for the
algorithms.
Algorithm descriptions:
Given an integer parameter named current_number
and two constant global variables:
const int MIN_NUMBER = 1;
const int MAX_NUMBER = 8;
Create an algorithm named forward, that will
advance ONE value through a sequence of numbers 1,
2, 3 ... MAX_NUMBER. In...
Most questions answered within 3 hours.
-
How do the mechanical features of bone affect its roles as
repositories of phosphate and calcium,...
asked 2 minutes ago -
P agreed to buy 100 barrels of widget oil, which was stored in a
large tank...
asked 3 minutes ago -
The unstable isotope 40K is used for dating rock samples. Its
half-life is 1.28×109y. How many...
asked 5 minutes ago -
Compare and contrast constructed-response items and
selected-response items.
Identify at least one (1) advantage and one...
asked 7 minutes ago -
A) Find the moment of inertia of a 2 meter long stick with a
mass of...
asked 6 minutes ago -
For the code below write a public static main() method
in class Student that:
- creates...
asked 8 minutes ago -
Please show all steps. Thank you
A 1.0-cm-diameter pipe widens to 2.0 cm, then narrows to...
asked 21 minutes ago -
The equilibrium constant for the following reaction Ag+(aq) +
2NH3(aq) Ag(NH3)2+(aq) is K = 1.7 ×...
asked 29 minutes ago -
A carbon heater element has fixed resistance of 28 Ohms. It is
connected to an A/C...
asked 30 minutes ago -
Suppose X∼Exp(λ) for some λ >0. Compute E(X) and Var(X).
asked 44 minutes ago -
Xanth Co. has 8.9% annual coupon bonds with face value of $1,000
and 7 years remaining...
asked 42 minutes ago -
The Bellevue University bookstore purchases sweatshirts with the
school name and logo from a vendor. The...
asked 45 minutes ago