I have this project for my class that requires to make a .h and .c file associat
ID: 3860567 • Letter: I
Question
I have this project for my class that requires to make a .h and .c file associating with the BIGINT library:
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
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
these functions need to be in the bigInt.h header file:
ClassicalMult (bigInt A, bigInt B, int base)
karatsubaMult (bigInt A, bigInt B, int base)
ToomMult (bigInt A, bigInt B, int base)
CompareAlgorithms (char firstalgorithm, char firstalgorithm, int size)
Large_Rnd (bigInt size)
Timer ()
PrintBI (bigInt A)
GetBI(bigInt A)
I can't get to make the multiplication work for the classical, karatsuba, and toom-cook. and the compare algorithms doesn't work either. please help
Explanation / Answer
#include <stdio.h>
#include <ctype.h> // for tolower()
#include <string.h>
#include "BigArithmetic.h"
#define RANDOM_LENGTH 1000
// printingmenu
void displayMenu() {
printf(" 1. Addition ");
printf("2. Multiplicaiton - Classical ");
printf("3. Multiplicaiton - Karatsuba ");
printf("4. Multiplicaiton - Toom-Cook ");
printf("5. Display menu ");
printf("6. Quit Application ");
}
int main(void) {
// random seed
srand(time(NULL));
// big integers.. memory allocation
bigInt* bigNumber1 = (bigInt*)malloc(sizeof(bigInt));
bigInt* bigNumber2 = (bigInt*)malloc(sizeof(bigInt));
bigInt* _sum = (bigInt*)malloc(sizeof(bigInt));
bigInt* _product = (bigInt*)malloc(sizeof(bigInt));
// variables declaration
int correct_response = 0;
int selectedMenuOption = 7;
char selectedMode;
// timer variables
clock_t begin;
clock_t end;
_product->num_digits[0] = '0';
_product->num_digits[1] = '';
// Print the menu and interact with the user
while (selectedMenuOption != 8) {
displayMenu();
printf("Choose option: ");
scanf(" %d", &selectedMenuOption);
switch (selectedMenuOption) {
// adding
case 1:
while (correct_response == 0) {
printf("User / random mode [u or r] ");
scanf(" %c", &selectedMode);
selectedMode = tolower(selectedMode);
if (selectedMode == 'u' || selectedMode == 'r') {
correct_response = 1;
}
else {
printf("Invalid response. ");
}
}
correct_response = 0;
putchar(' ');
// mode selected if user
if (selectedMode == 'u') {
printf("Enter a big number: ");
readBig1(bigNumber1);
printf("Enter a big number: ");
readBig1(bigNumber2);
addition(bigNumber1, bigNumber2, _sum);
printf("Sum: ");
printBig1(_sum);
}
// mode selected if random
else {
big_rand(bigNumber1, RANDOM_LENGTH);
big_rand(bigNumber2, RANDOM_LENGTH);
begin = clock();
addition(bigNumber1, bigNumber2, _sum);
end = clock();
printf("Big integer 1: ");
printBig1(bigNumber1);
printf(" Big integer 2: ");
printBig1(bigNumber2);
printf(" The sum is: ");
printBig1(_sum);
printf(" Execution takes %f seconds ", startTimer(begin, end));
}
break;
// multiplication
case 2:
while (correct_response == 0) {
printf("User / random mode [u or r] ");
scanf(" %c", &selectedMode);
selectedMode = tolower(selectedMode);
if (selectedMode == 'u' || selectedMode == 'r') {
correct_response = 1;
}
else {
printf("Invalid response ");
}
}
correct_response = 0;
putchar(' ');
// mode selected if user
if (selectedMode == 'u') {
printf("Enter a big number: ");
readBig1(bigNumber1);
printf("Enter a big number: ");
readBig1(bigNumber2);
_product = ClassicalMult(bigNumber1, bigNumber2, _product, 10);
printf("Product result: ");
printBig1(_product);
}
// mode selected if random
else {
big_rand(bigNumber1, RANDOM_LENGTH);
big_rand(bigNumber2, RANDOM_LENGTH);
begin = clock();
_product = ClassicalMult(bigNumber1, bigNumber2, _product, 10);
end = clock();
printf("Number1 : ");
printBig1(bigNumber1);
printf(" Number2 : ");
printBig1(bigNumber2);
printf(" Result: ");
printBig1(_product);
printf(" Execution takes %f seconds ", startTimer(begin, end));
}
break;
// Karatsuba
case 3:
while (correct_response == 0) {
printf("User / random mode [u or r] ");
scanf(" %c", &selectedMode);
selectedMode = tolower(selectedMode);
if (selectedMode == 'u' || selectedMode == 'r') {
correct_response = 1;
}
else {
printf("Invalid response. ");
}
}
correct_response = 0;
putchar(' ');
// mode selected if user
if (selectedMode == 'u') {
printf("Enter a big number: ");
readBig1(bigNumber1);
printf("Enter a big number: ");
readBig1(bigNumber2);
_product = karatsubaMult(bigNumber1, bigNumber2, _product, 10);
printf("Result: ");
printBig1(_product);
}
// mode selected if random
else {
big_rand(bigNumber1, RANDOM_LENGTH);
big_rand(bigNumber2, RANDOM_LENGTH);
begin = clock();
_product = karatsubaMult(bigNumber1, bigNumber2, _product, 10);
end = clock();
printf("Number1: ");
printBig1(bigNumber1);
printf(" Number2 2: ");
printBig1(bigNumber2);
printf(" Result: ");
printBig1(_product);
printf(" Execution takes %f seconds ", startTimer(begin, end));
}
break;
// Toom-Cook
case 4:
while (correct_response == 0) {
printf("User / random mode [u or r] ");
scanf(" %c", &selectedMode);
selectedMode = tolower(selectedMode);
if (selectedMode == 'u' || selectedMode == 'r') {
correct_response = 1;
}
else {
printf("Invalid response. ");
}
}
correct_response = 0;
putchar(' ');
// mode selected if user
if (selectedMode == 'u') {
printf("Enter a big number: ");
readBig1(bigNumber1);
printf("Enter another big number: ");
readBig1(bigNumber2);
_product = ToomMult(bigNumber1, bigNumber2, _product, 10);
printf("Result: ");
printBig1(_product);
}
// mode selected if random
else {
big_rand(bigNumber1, RANDOM_LENGTH);
big_rand(bigNumber2, RANDOM_LENGTH);
begin = clock();
_product = ToomMult(bigNumber1, bigNumber2, _product, 10);
end = clock();
printf("Number 1: ");
printBig1(bigNumber1);
printf(" Number 2: ");
printBig1(bigNumber2);
printf(" Result: ");
printBig1(_product);
printf(" Execution takes %f seconds ", startTimer(begin, end));
}
break;
// Print menu
case 5:
displayMenu();
break;
// Quit
case 6:
break;
default:
printf("Enter valid selection ");
break;
}
}
// memory free variables
free(bigNumber1);
free(bigNumber2);
free(_sum);
free(_product);
return 0;
}
-------------------------------------
bigArithmetic.h
------------------------
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <string.h>
#ifndef BIGARITHMETIC_H
#define BIGARITHMETIC_H
#define MAX_LENGTH 2000
typedef struct {
char num_digits[MAX_LENGTH];
} bigInt;
void readBig1(bigInt* NUM) {
scanf(" %s", NUM->num_digits);
}
void printBig1(bigInt* NUM) {
for (int i = 0; i < strlen(NUM->num_digits); i++) {
putchar(NUM->num_digits[i]);
}
putchar(' ');
}
void big_rand(bigInt* NUM, int size) {
for (int i = 0; i < size; i++) {
NUM->num_digits[i] = (rand() % 10) + 48;
}
NUM->num_digits[size] = '';
}
double startTimer(clock_t begin, clock_t end) {
return (double)(end - begin) / CLOCKS_PER_SEC;
}
int max(int NUM, int NUM2) {
if (NUM > NUM2) {
return NUM;
}
else {
return NUM2;
}
}
void pad_bigInt_head(bigInt* NUM, int _padding) {
for (int index = strlen(NUM->num_digits) + 1; index >= 0; --index) {
NUM->num_digits[index + _padding] = NUM->num_digits[index];
NUM->num_digits[index] = '0';
}
}
void paddingTail(bigInt* NUM, int _padding) {
int len1 = strlen(NUM->num_digits);
int len2 = strlen(NUM->num_digits) + _padding;
NUM->num_digits[len2] = '';
for (int i = len1; i < len2; ++i) {
NUM->num_digits[i] = '0';
}
}
void trimZeros(bigInt* NUM) {
int _diff = 0;
int i;
while (NUM->num_digits[_diff] == '0') {
++_diff;
}
for (i = 0; NUM->num_digits[i] != ''; ++i) {
NUM->num_digits[i] = NUM->num_digits[i + _diff];
}
NUM->num_digits[i + 1] = '';
}
void addition(bigInt* NUM, bigInt* NUM2, bigInt* NUM3) {
int carry = 0;
int size_A = strlen(NUM->num_digits);
int size_B = strlen(NUM2->num_digits);
int _diff = abs(size_A - size_B);
if (size_A == size_B) {
;
}
else if (size_A < size_B) {
pad_bigInt_head(NUM, _diff);
}
else {
pad_bigInt_head(NUM2, _diff);
}
int terms_len = strlen(NUM->num_digits);
for (int i = 0; i <= terms_len; ++i) {
NUM3->num_digits[i] = '0';
}
NUM3->num_digits[terms_len + 1] = '';
for (int index = terms_len - 1; index >= 0; --index) {
NUM3->num_digits[index + 1] = (((carry + ((NUM->num_digits[index] + NUM2->num_digits[index]) - 96)) % 10) + 48);
carry = ((NUM->num_digits[index] + NUM2->num_digits[index]) - 96) / 10;
}
NUM3->num_digits[0] = (carry + 48);
trimZeros(NUM3);
}
bigInt* ClassicalMult(bigInt* NUM, bigInt* NUM2, bigInt* product, int base) {
bigInt* temp_bigInt = (bigInt*)malloc(sizeof(bigInt));
int carry = 0;
int size_A = strlen(NUM->num_digits);
int size_B = strlen(NUM2->num_digits);
int _diff = abs(size_A - size_B);
if (size_A == size_B) {
;
}
else if (size_A < size_B) {
pad_bigInt_head(NUM, _diff);
}
else {
pad_bigInt_head(NUM2, _diff);
}
int terms_len = strlen(NUM->num_digits);
if (terms_len == 1) {
temp_bigInt->num_digits[2] = '';
temp_bigInt->num_digits[1] = ((((NUM->num_digits[0] * NUM2->num_digits[0]) - 2304) - (48 * (NUM->num_digits[0] + NUM2->num_digits[0] - 96))) % 10) + 48;
temp_bigInt->num_digits[0] = ((((NUM->num_digits[0] * NUM2->num_digits[0]) - 2304) - (48 * (NUM->num_digits[0] + NUM2->num_digits[0] - 96))) / 10) + 48;
trimZeros(temp_bigInt);
addition(product, temp_bigInt, product);
return product;
}
else {
int m = terms_len / 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));
for (int i = 0; i < m; ++i) {
a->num_digits[i] = NUM->num_digits[i];
b->num_digits[i] = NUM->num_digits[m + i];
c->num_digits[i] = NUM2->num_digits[i];
d->num_digits[i] = NUM2->num_digits[m + i];
}
a->num_digits[m] = '';
b->num_digits[m] = '';
c->num_digits[m] = '';
d->num_digits[m] = '';
// Recursie
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);
paddingTail(ac, (2*m));
paddingTail(adbc_sum, m);
// Add
addition(product, ac, product);
addition(product, adbc_sum, product);
addition(product, bd, product);
return product;
}
}
bigInt* karatsubaMult(bigInt* NUM, bigInt* NUM2, bigInt* product, int base) {
return product;
}
bigInt* ToomMult(bigInt* NUM, bigInt* NUM2, bigInt* product, int base) {
return product;
}
#endif // #ifndef BIGARITHMETIC_H