Thread: I need to optimize a code and I don't know how

  1. #1
    Registered User
    Join Date
    Nov 2017
    Posts
    2

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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,810
    Perhaps you can make it readable to start with.
    By removing all those colour and font tags which you've managed to copy from your IDE.

    Say by either doing
    - copy text only (in your IDE)
    - paste text only (in your browser)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me to optimize this code
    By Fn00 in forum C Programming
    Replies: 12
    Last Post: 09-27-2015, 04:28 PM
  2. How to optimize C++ code in Linux?
    By MutantJohn in forum Linux Programming
    Replies: 5
    Last Post: 04-01-2014, 11:43 AM
  3. How to optimize C++ code in Linux?
    By MutantJohn in forum C++ Programming
    Replies: 2
    Last Post: 04-01-2014, 05:27 AM
  4. How can i optimize this code
    By ArunS in forum C Programming
    Replies: 15
    Last Post: 08-08-2011, 02:11 PM
  5. Please help me optimize my code
    By lazyme in forum C++ Programming
    Replies: 3
    Last Post: 01-25-2010, 04:05 AM

Tags for this Thread