Everyone knows how to multiply large numbers. But there is a faster way. What’s interesting is that it was only discovered as recently as the 1960s, by Karatsuba. It makes me wonder how many other things are right under our noses that millions(billions?) of people know about over the course of centuries but nobody has thought of a better way… yet.
I implemented the algorithm bellow in C. The key idea is that it’s possible to save a multiplication by doing arithmetic.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
int bit_length(uint64_t a) {
int bl = 0;
while( a != 0 ) {
a = (a>>1);
bl++;
}
return bl;
}
uint64_t mult(uint64_t x, uint64_t y) {
int xc = bit_length(x);
int yc = bit_length(y);
if( xc < 8 || yc < 8) return x*y;
int m2 = MAX(xc,yc);
int m = (m2 / 2) + (m2 % 2);
uint64_t x1 = x >> m;
uint64_t x0 = x - (x1 << m);
uint64_t y1 = y >> m;
uint64_t y0 = y - (y1 << m);
uint64_t z2 = mult(x1,y1);
uint64_t z0 = mult(x0,y0);
uint64_t z1 = mult((x1+x0),(y1+y0)) - z2 - z0;
return (z2 << (m*2)) + (z1 << m) + z0;
}