MCODE: Fastest way to multiply

[Albert Chan]

Knowing how multiplication is done internally, we can design better algorithm.
Example, doing factorial by multiply 1 number at a time is bad.

Assuming FFT multiply available, shell method is a fast way to do factorial.

Code:

def fac(n): return 1 if n<2 else m(n%2+1, n, (n//2)-1)

def m(a, b, n):
    'return (a b) * (a+1)(b-1) *  ... (a+n)(b-n), n >= 0'
    if n==0: return a*b
    k = n//2 + 1
    return m(a, b, k-1) * m(a+k, b-k, n-k)

fac(100) = m(1, 100, 49)

m(1,100,49) = m(1,100,24) * m(26,75,24)
m(1,100,24) = 58349563223699444377128670554435213870263955676382762341761024 * 10^12
m(26,75,24) = 1599432974093600067896009239156107676288209506371901842134782334820417536 * 10^12

m(1,100,24) = m(1,100,12) * m(14,87,11)
m(1,100,12) = 275716888847455562868038565888 * 10^6
m(14,87,11) = 211628542116555657261011122126848 * 10^6

m(26,75,24) = m(26,75,12) * m(39,62,11)
m(26,75,12) = 26582152251962634809969206238386323456 * 10^6
m(39,62,11) = 60169430937463291680684196401709056 * 10^6
...

Factor pairs are about the same size, even the recursive ones.