 mersenneforum.org > Math The binary multiply convolution approach
 Register FAQ Search Today's Posts Mark Forums Read 2003-05-30, 08:50 #1 Dresdenboy   Apr 2003 Berlin, Germany 192 Posts The binary multiply convolution approach In Crandall & Fagin's DWT paper (and also in the book "Prime numbers") I found an interesting mention: (And I hope my assumptions are correct ;)) If we want to do multiplication x*x mod p with p=2^q-1, that is possible using a FFT with length q, binary multiplication and cyclic convolution. This idea is discarded because of poor support for binary multiplication in current CPUs. But one advantage would be that the binary multiplication is'n necessary since binary mul of x and y would be x AND y. And since y=x for squaring we would get x=x AND x. How fast could such a length-q FFT be to create signals consisting of binary digits? So we'd only have to do a cyclic convolution of the bits which can be done with smart shifting/masking and logical operations to get the sums of two bits. The inverse order bits for the convolution could be created during the FFT. How fast could be this approach? And where do the problems lie? Regards, Matthias   2003-05-30, 09:08 #2 Axel Fox   May 2003 6016 Posts One problem I see is that the FFT Length would have to be much greater. For ranges in the 20M, the FFT Length would have to be in the 20M range as well, while we now only use a 1024K FFT Length for those ranges. This would make FFT and IFFT permutations much slower than they are now and the gain from the binary computations should be A LOT to compensate for this loss in FFT Conversion. Axel Fox.   2003-05-30, 09:16 #3 Dresdenboy   Apr 2003 Berlin, Germany 192 Posts That's right, but we speak about 20M bits and a 1024k FFT means 1024k doubles (53bit mantissa) which makes even 55M bits. As I see it, it would be necessary to do the FFT also bitwise inside the data words of your preferred size (32bit on 32bit integer, 64bit or 128bit using SIMD or 64bit CPUs). Currently I just don't have an imagination how the FFT matrix would look like. Maybe the math guys could give me some impression of this :)   2003-05-30, 09:45 #4 Axel Fox   May 2003 25×3 Posts Hmm, I think I'll leave it up to the math guys, I don't know that much about FFT's. Sorry. Axel Fox.   2003-06-02, 17:23 #5 Dresdenboy   Apr 2003 Berlin, Germany 36110 Posts Can someone please explain me how the bitwise multiplies were thought to be in the Crandall/Fagin paper? Maybe with some small example? Actually I'd think of digits in the form 0, 1, 0, 0, 1, 1, ... but how are they derived from the FFT'ed input numbers? Regards, Matthias  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Number Theory Discussion Group 4 2018-04-06 12:57 Mark Rose PrimeNet 6 2017-05-23 23:58 preda Computer Science & Computational Number Theory 8 2017-05-10 22:11 davar55 Puzzles 18 2010-12-22 22:07 mgb Lounge 0 2008-07-28 12:54

All times are UTC. The time now is 22:12.

Tue Oct 27 22:12:32 UTC 2020 up 47 days, 19:23, 2 users, load averages: 1.89, 1.92, 1.91