/multiplication

Karatsuba multiplication for big integers

Primary LanguageC++

Multiplication for big integers

Here is very basic implementation of naive multiplication (which takes BigO^2) and Karatsuba algorithm (which takes BigO^log).

  1. Standard sequence for both algorithms:

    // Getting number from the input (stdin, file, etc.)
    vector<int> first = get_number(cin);
    vector<int> second = get_number(cin);
    
    // Select the biggest length of two numbers
    int n = max(first.size(), second.size());
    
    // Extend two vectors to the nearest square of 2
    extend_vec(first, n);
    extend_vec(second, n);   
  2. Then you should select prefered multiplication algorithm.

    • For using naive multiplication:
    vector<int> res = naive_mul(first, second);
    • For using Karatsuba multiplication:
    vector<int> res = karatsuba_mul(first, second);
  3. And finalize your result by usingfinalize(res);

  4. Call print_res() function for getting the result:

    // Pass the result vector to it
    print_res(res);
  5. Enjoy the vast output.

Now, it is using vectors for storing numbers with base 10. Further improvments should be to change base of all numbers which are stored in input vectors.