MCODE: Fastest way to multiply
04-15-2019, 10:22 PM
Post: #4
 Albert Chan Senior Member Posts: 2,349 Joined: Jul 2018
RE: MCODE: Fastest way to multiply
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.
 « Next Oldest | Next Newest »

 Messages In This Thread MCODE: Fastest way to multiply - PeterP - 04-15-2019, 03:58 PM RE: MCODE: Fastest way to multiply - Albert Chan - 04-15-2019, 05:07 PM RE: MCODE: Fastest way to multiply - PeterP - 04-16-2019, 07:07 PM RE: MCODE: Fastest way to multiply - Valentin Albillo - 04-15-2019, 07:50 PM RE: MCODE: Fastest way to multiply - Gerson W. Barbosa - 04-16-2019, 01:59 AM RE: MCODE: Fastest way to multiply - Valentin Albillo - 04-17-2019, 11:24 PM RE: MCODE: Fastest way to multiply - Albert Chan - 04-15-2019 10:22 PM RE: MCODE: Fastest way to multiply - Leviset - 04-16-2019, 03:09 PM RE: MCODE: Fastest way to multiply - ijabbott - 04-16-2019, 07:34 PM RE: MCODE: Fastest way to multiply - Leviset - 04-16-2019, 10:29 PM RE: MCODE: Fastest way to multiply - Albert Chan - 04-16-2019, 11:04 PM

User(s) browsing this thread: 1 Guest(s)