[HN Gopher] Multiplying Integers Using Fourier Transforms [pdf]
___________________________________________________________________
Multiplying Integers Using Fourier Transforms [pdf]
Author : nceqs3
Score : 50 points
Date : 2021-05-15 13:41 UTC (9 hours ago)
(HTM) web link (www.cs.rug.nl)
(TXT) w3m dump (www.cs.rug.nl)
| PicassoCTs wrote:
| This is great. One way closer to a computation platform, were the
| data just streams continuously through operative "channels" and
| the execution is mostly encoded into the layout of the data in
| memory. There is just no "program" to load, just a river of data,
| squeezing through cores which endlessly in parallel perform the
| same operations (until some other driftwood in the data instructs
| them to change that in this case for example a addition
| operation).
|
| The complexity of such a program would be mostly done at compile
| time, layouting the instructionflow into the memory. Data would
| have physics, as in the parallel nature of this "simulation"
| pumping data through would add something roughly similar to our
| physics to the behaviour. Interaction between parallel processed
| elements has a scope, like a lightcone in our physics.
| (SumOf(NrOfCores*LargestChunkOfData))
|
| If you want to safely remove or place new data into the whole
| affair, one just leaves large enough "gaps" in the datastream
| that can be assumed to firewall.
|
| In my undergrad time i build a little comp science experiment.
| Nothing fenzy, just a idealized, parallel "Engine", copying
| datachunks of size from Buffer A to Buffer B.
|
| https://github.com/PicassoCT/CompScienceExperiments/tree/mas...
|
| Even just this has interesting interaction behaviour. Like sand
| at the beach, the data get sorted by size after intervals. One
| also insert "dark matter" aka dead chunks into the buffers, which
| has the effect of "accelerating" large chunks of data, while the
| small chunks stay put. All of this is from the point of view of
| the buffer of course, in which time is one "total copying from a
| to b".
|
| Sorry i found this fascinating, even though it might be of no
| value besides distraction at all.
| mpreda wrote:
| An excellent paper in the field is the one introducing the IBDWT,
| Irrational Base Discrete Weighted Transform [1]
|
| 1.
| http://www.faginfamily.net/barry/Papers/Discrete%20Weighted%...
| iratic0 wrote:
| Faster than Shakuntala Devi?
| nynx wrote:
| The paper seems to lack a comparison between regular
| multiplication of large integers and FFT multiplication in base
| 2.
| davesque wrote:
| I only skimmed the paper but is this essentially the same thing
| as Karatsuba multiplication (which I believe also has O(n log n)
| performance)?
| curtisf wrote:
| No, Karatsuba multiplication is not linearithmic. Karatsuba
| multiplication takes time about n^1.58 (as opposed to n^2 in
| naive multiplication)
| ramshanker wrote:
| GIMPS (Great Internet Mersenne Prime Search) has been using the
| trick for decades. And it works wonder for finding the largest
| (i.e mersenne) prime.
|
| https://www.mersenne.org/various/math.php
| robertelder wrote:
| Neat. I wrote a tool that shows interactive examples of how you
| can actually do the calculations for multiplications with Fourier
| transforms:
|
| https://blog.robertelder.org/fast-multiplication-using-fouri...
|
| The trick is really just about realizing that you can re-write a
| number like 1234 as a polynomial like 1 * 10^3 + 2 * 10^2 + 3 *
| 10^1 + 4 * 10^0.
| nceqs3 wrote:
| That is really cool and useful. Visualization of the FFT can be
| hard sometimes. Thanks for making that.
| Igorvelky wrote:
| this is exactly what AVX512 instructions are made for.
|
| you can treat one number as multiple data.
| kingsuper20 wrote:
| Jeesh, that's clever.
|
| I'd probably just do a giant shift and add loop.
| nayuki wrote:
| There's a great video on this topic:
| https://www.youtube.com/watch?v=h7apO7q16V0
___________________________________________________________________
(page generated 2021-05-15 23:01 UTC)