BIGINT LIBRARY make a menu introducing these options: Introducing the library Menu (Big integer arithmetic)

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 of multiplication algorithms (two options: user mode, random mode)

6- Testing the correctness of algorithms

7- Continue or quit

Here is the code I have now can someone tell me how to fix it?

// main.c

#include #include // for tolower() #include #include "BigArithmetic.h" // Our custom header file

#define RANDOM_LENGTH 1000

/* This function will print our menu for the user. * Arguments taken: none * Return value: none */ void print_menu(void) { putchar(' '); printf("1. Addition of two big integers "); printf("2. Multiplicaiton of two big integers (Classical) "); printf("3. Multiplicaiton of two big integers (Karatsuba) "); printf("4. Multiplicaiton of two big integers (Toom-Cook) "); printf("5. Compare the execution time of multiplication algorithms "); printf("6. Test the correctness of algorithms "); printf("7. Print menu "); printf("8. Quit "); putchar(' '); } // Main int main(void) { // Seed the random generator srand(time(NULL)); // Allocate memory for our big integer variables 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)); // Some variables for the menu int valid_response = 0; int menu_selection = 7; char mode_selection; // Variables for our timer function clock_t begin; clock_t end; // Initialize the product to zero big_num_product->digits[0] = '0'; big_num_product->digits[1] = '\0';

// Print the menu and interact with the user while (menu_selection != 8) { print_menu(); printf("Please make a selection: "); scanf(" %d", &menu_selection);

switch (menu_selection) {

// Addition of two integers case 1: // Make sure we're getting only the correct 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'. "); } } // Reset to 0 so the validation will work subsequent times valid_response = 0; putchar(' '); // User mode if (mode_selection == 'u') { printf("Enter a big integer: "); GetBI(big_num1); printf("Enter another big integer: "); GetBI(big_num2); addition(big_num1, big_num2, big_num_sum); printf("The sum is: "); PrintBI(big_num_sum); } // Random mode 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: "); PrintBI(big_num1); printf(" Big integer 2: "); PrintBI(big_num2); printf(" The sum is: "); PrintBI(big_num_sum); printf(" Execution time: %f seconds ", Timer(begin, end)); } break;

// Classical multiplicaiton case 2: // Make sure we're getting only the correct 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'. "); } } // Reset to 0 so the validation will work subsequent times valid_response = 0; putchar(' '); // User mode if (mode_selection == 'u') { printf("Enter a big integer: "); GetBI(big_num1); printf("Enter another big integer: "); GetBI(big_num2); big_num_product = ClassicalMult(big_num1, big_num2, big_num_product, 10); printf("The product is: "); PrintBI(big_num_product); } // 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: "); PrintBI(big_num1); printf(" Big integer 2: "); PrintBI(big_num2); printf(" The product is: "); PrintBI(big_num_product); printf(" Execution time: %f seconds ", Timer(begin, end)); } break;

// Karatsuba Multiplication case 3: // Make sure we're getting only the correct 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'. "); } } // Reset to 0 so the validation will work subsequent times valid_response = 0; putchar(' '); // User mode if (mode_selection == 'u') { printf("Enter a big integer: "); GetBI(big_num1); printf("Enter another big integer: "); GetBI(big_num2); big_num_product = karatsubaMult(big_num1, big_num2, big_num_product, 10); printf("The product is: "); 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: "); PrintBI(big_num1); printf(" Big integer 2: "); PrintBI(big_num2); printf(" The product is: "); PrintBI(big_num_product); printf(" Execution time: %f seconds ", Timer(begin, end)); } break;

// Toom-Cook Multiplication case 4: // Make sure we're getting only the correct 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'. "); } } // Reset to 0 so the validation will work subsequent times valid_response = 0; putchar(' '); // User mode if (mode_selection == 'u') { printf("Enter a big integer: "); GetBI(big_num1); printf("Enter another big integer: "); GetBI(big_num2); big_num_product = ToomMult(big_num1, big_num2, big_num_product, 10); printf("The product is: "); 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: "); PrintBI(big_num1); printf(" Big integer 2: "); PrintBI(big_num2); printf(" The product is: "); PrintBI(big_num_product); printf(" Execution time: %f seconds ", 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 from our variables free(big_num1); free(big_num2); free(big_num_sum); free(big_num_product); return 0; }

//BigArithmetic.h

#include #include // for srand(), rand() #include // for time(), clock(), CLOCKS_PER_SEC #include // for abs() #include

// Make sure the header isn't defined somewhere else #ifndef BIGARITHMETIC_H #define BIGARITHMETIC_H /* Maximum length of our big integers. If we multiply two * 1000-digit numbers, we should end up with a 2000-digit * product, so we want the max length to be large enough to * accomodate a product of that size. */ #define MAX_LENGTH 2000 // Here we define our bigInt type with an array of characters typedef struct { char digits[MAX_LENGTH]; } bigInt; /* This function will get a big integer from stdin. * Arguments taken: Reference to a bigInt * Return value: none */ void GetBI(bigInt* A) { scanf(" %s", A->digits); } /* This function will print out our big integer. * Arguements taken: Reference to a big integer variable * Return value: none */ void PrintBI(bigInt* A) { for (int i = 0; i < strlen(A->digits); i++) { putchar(A->digits[i]); } putchar(' '); } /* This function will generate a random big integer. * Arguments taken: Reference to a bigInt and the number of digits needed * Return value: none */ void Large_Rnd(bigInt* A, int size) { for (int i = 0; i < size; i++) { A->digits[i] = (rand() % 10) + 48; } // Terminate the string A->digits[size] = '\0'; } /* This function will time the execution of a particular block of code. * Arguments taken: The beginning and end times of the code * Return value: A double representing the difference between the beginning * and end */ double Timer(clock_t begin, clock_t end) { return (double)(end - begin) / CLOCKS_PER_SEC; } /* This function will find the maximum of two integers. * Arguments taken: Two integers * Return value: the largest of the two */ int max(int A, int B) { if (A > B) { return A; } else { return B; } } /* This funcion will take a big int and shift the digits to the right * in order to prepend however many zeros on the front we need. * Arguments taken: Reference to a bigInt, and the number of zeroes to pad * Return value: none */ void pad_bigInt_head(bigInt* A, int padding) { /* We need to move the null zero at the end of the string as well, so * we'll add one to the last index (our starting position) so we can * move it as well. */ for (int index = strlen(A->digits) + 1; index >= 0; --index) { A->digits[index + padding] = A->digits[index]; A->digits[index] = '0'; } } /* This funcion will take a big int and pad the tail with as many * extra zeroes as we need. * Arguments taken: Reference to a bigInt, and the number of zeroes to pad * Return value: none */ void pad_bigInt_tail(bigInt* A, int padding) { int old_length = strlen(A->digits); int new_length = strlen(A->digits) + padding; // Terminate the string at the new length A->digits[new_length] = '\0'; // Fill in the space between with zeroes for (int i = old_length; i < new_length; ++i) { A->digits[i] = '0'; } } /* This function will trim any leading zeroes from a big integer. We do * this by shifting everything in the array to the left. * Arguments taken: Reference to a bigInt * Return value: none */ void trim_leading_zeroes(bigInt* A) { int diff = 0; int i; // First, we find where the zeros stop while (A->digits[diff] == '0') { ++diff; } // Then we start shifting everything to the left for (i = 0; A->digits[i] != '\0'; ++i) { A->digits[i] = A->digits[i + diff]; } // Now terminate the string A->digits[i + 1] = '\0'; } /* This function will add two big integers. * Arguments taken: References to the two bigInts to add, and a * reference to the sum for the bigInts * Return value: none */ 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); /* We want to make sure A and B are strings of the same length. But if * one is shorter, we need to pad zeroes at the head. */ if (sizeA == sizeB) { ; } else if (sizeA < sizeB) { pad_bigInt_head(A, size_diff); } else { pad_bigInt_head(B, size_diff); } // Since the two terms should now be equal length, we'll use this for indexing int len_of_terms = strlen(A->digits); /* Initialize C to all zeros with a null zero at the end to terminate the * string. We will make C one digit longer than the max length of A and B. */ for (int i = 0; i <= len_of_terms; ++i) { C->digits[i] = '0'; } C->digits[len_of_terms + 1] = '\0'; /* We start our additon from right to left, so our starting index for the * terms is the length of the terms minus one. But since the sum is * one digit longer, the sum will start at the length of the terms. * * To make sure we're doing addition that makes sense, we need to assess * the ascii values for the characters. So, for example, if A and B are * 1 and 2 respectively, adding them will give us 99, the ascii value for * 3. So we have to subtract 48 to give us the integer value. We then mod * with 10 to get the value in case the added integer value is greater * ten so we can assess the carry. We then add 48 back to that integer * value to get the character value. * * To get the carry value, we simple divide the integer values of the two * characters by 10. Since it's an integer, it will truncate the decimal * portion, giving us the value of the 10's place. */ 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; } // Make sure we account for the carry on the last addition C->digits[0] = (carry + 48); trim_leading_zeroes(C); } /* This fucntion will perform multiplication on two big integers by the * classical algorithm. This is the recursive implementation. * Arguments taken: Two big integers to multiply, a big integer for the * product of the two, and the base of the big integers * Return value: the big integer product * * NOTE: Currently, this is working perfectly for single digit multiplication, * but not for anything greater than single digits. I'm getting bogged down in * the recursive part of this algorithm and I'm not sure what I'm doing wrong. */ 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); /* As with the addition function, we want to make sure the two terms * are the same length. */ if (sizeA == sizeB) { ; } else if (sizeA < sizeB) { pad_bigInt_head(A, size_diff); } else { pad_bigInt_head(B, size_diff); } /* Since the two terms should now be equal length, we'll use this * for indexing. */ int len_of_terms = strlen(A->digits);

/* This is our end condtion: if the length of the terms is 1. We have to * make sure we're multiplying them as integers, then converting them back * to characters. */ 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; } // Here's the recursive part else { int m = len_of_terms / 2; // Set up our variables 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)); // Break the A and B big integers in half 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]; } // Terminate the strings a->digits[m] = '\0'; b->digits[m] = '\0'; c->digits[m] = '\0'; d->digits[m] = '\0'; // Recurse ac = ClassicalMult(a, c, product, 10); ad = ClassicalMult(a, d, product, 10); bc = ClassicalMult(b, c, product, 10); bd = ClassicalMult(b, d, product, 10); /* --------------------------- * This is the pat where everything seems to go off the rails. I'm not * sure what it is that's going wrong here. Somehow I'm not looking at * this correctly. * --------------------------- */ // Perform the addition for the middle term addition(ad, bc, adbc_sum); /* Instead of multiplying the numbers by a power of 10, we simply pad * the tail of the number with the appropriate amount of zeroes */ pad_bigInt_tail(ac, (2*m)); pad_bigInt_tail(adbc_sum, m); // Add everything up addition(product, ac, product); addition(product, adbc_sum, product); addition(product, bd, product); return product; } } /* This fucntion will perform multiplication on two big integers by the * Karatsuba algorithm. * Arguments taken: Two big integers to multiply, a big integer for the * product of the two, and the base of the big integers * Return value: the big integer product */ bigInt* karatsubaMult(bigInt* A, bigInt* B, bigInt* product, int base) {

return product; } /* This fucntion will perform multiplication on two big integers by the * Toom Cook algorithm. * Arguments taken: Two big integers to multiply, a big integer for the * product of the two, and the base of the big integers * Return value: the big integer product */ bigInt* ToomMult(bigInt* A, bigInt* B, bigInt* product, int base) { return product; } /* This function will compare the execution time between two algorithms, * with randomly generated big integers. * Arguments taken: two characters representing the two algorithms to * compare, and the number of digits to use in the integers that are being * multiplied. * Return value: none */ void CompareAlgorithms(char firstAlgorithm, char secondAlgorithm, int size) {

} #endif // #ifndef BIGARITHMETIC_H