1 // Fast multiplication of large integers using Karatsuba algorithm 2 // https://en.wikipedia.org/wiki/Karatsuba_algorithm 3 // https://www.youtube.com/watch?v=k_j5TAPQf7k 4 // https://www.youtube.com/watch?v=yWI2K4jOjFQ 5 6 #include <iostream> 7 #include <cmath> 8 9 long max(long x, long y) { 10 return (x > y) ? x : y; 11 } 12 13 unsigned int size_base10(long n) { 14 return (abs(n) <= 9) ? 1 : (1 + size_base10(n/10)); 15 } 16 17 long shift_right_by_base10(long n, unsigned int m) { 18 return (long)(n / std::pow(10, m)); 19 } 20 21 long karatsuba(long x, long y) { 22 if((x < 10) || (y < 10)) 23 return x*y; // fall back to traditional multiplicatio 24 25 unsigned int n = max(size_base10(x), size_base10(y)); 26 27 long a = shift_right_by_base10(x, (n/2)); 28 long b = (x % (long)pow(10, n/2)); 29 30 long c = shift_right_by_base10(y, (n/2)); 31 long d = (y % (long)pow(10, n/2)); 32 33 long ac = karatsuba(a, c); 34 long bd = karatsuba(b, d); 35 long ad_plus_bc = (karatsuba(a+b, c+d)-ac-bd); 36 37 return ((ac*pow(10, (n/2)*2)) + (ad_plus_bc*pow(10, n/2)) + bd); 38 } 39 40 int main (void) { 41 std::cout << karatsuba(146123, 352120) << std::endl; 42 return 0; 43 }
