Thread: 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);
}