I need to optimize a code and I don't know how
I have an assignment where I need to use the Karatsuba algorithm
I did code it, but the TA told me that I should use the divide and conquer method and that some parts are not optimal. Can someone help me?
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>// define a function called SWAP to make input a>=b
#define SWAP(a,b) { a ˆ= b; b ˆ= a; a ˆ= b; }
// declare function
unsigned long int mult(unsigned long int a, unsigned long int b);
int main () {
// define variables a and b
unsigned long int a, b;
// condition for a random function related to time
srand(time(NULL));
// if not defining, run Karatsuba algorithm
#ifndef TEST
// create a random number for a and b
a=rand(); b=rand();
// output
printf("%ld*%ld=%ld %ld\n",a,b,mult(a,b), RAND_MAX);
#endif
// if defining, run Karatsuba algorithm and verify if it is true or not
#ifdef TEST
// define i for for loop
int i;
// check 1000000 times
for(i=0; i< 1000000; i++) {
// assign random number for a and b
a=rand(); b=rand();
// if Karatsuba algorithm failes
if(mult(a,b)!=a*b) {
// print the wrong output
fprintf(stderr, "Error (%d): a=%ld, b=%ld, a*b=%ld, k(a,b)=%ld \n”,i,a,b,a*b,mult(a,b));
// exit
exit(-1);
}
}
#endif
}
// function named mult that uses Karatsuba algorithm
unsigned long int mult(unsigned long int a, unsigned long int b) {
// defining variables
int i, n, N;
// small numbers from the long int used in Karatsuba algorithm
unsigned long int x0, y0, z0, z1 = 1;
// if b is larger than a, use SWAP function to switch a and b
if (a < b) SWAP(a, b);
// multiplying any number by 0 is 0
if (b == 0) return 0;
for (n = -1, i = 1; i <= b; i <<= 1, n++); // this part is not optimal
for (N = n; i <= a; i <<= 1, N++)
y0 = b & ((1 << n) - 1);
x0 = a & ((1 << N) - 1);
z0 = mult(x0, y0);
i = N + n;
return ((z1<<i)+(x0<<n)+(y0<<N)+z0);
}
