MCODE: Fastest way to multiply
|
04-15-2019, 10:22 PM
Post: #4
|
|||
|
|||
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) 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: 2 Guest(s)