2003-05-30, 08:50 | #1 |
Apr 2003
Berlin, Germany
19^{2} 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 |
May 2003
2^{5}×3 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 |
Apr 2003
Berlin, Germany
101101001_{2} 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 |
May 2003
2^{5}·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 |
Apr 2003
Berlin, Germany
19^{2} 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 | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Modulus function on a linear convolution | lukerichards | Number Theory Discussion Group | 4 | 2018-04-06 12:57 |
Best approach for P-1? | Mark Rose | PrimeNet | 6 | 2017-05-23 23:58 |
Length-4 autonegacyclic convolution in 5 multiplies, how? | preda | Computer Science & Computational Number Theory | 8 | 2017-05-10 22:11 |
Multiply Pandigital | davar55 | Puzzles | 18 | 2010-12-22 22:07 |
Multiply | mgb | Lounge | 0 | 2008-07-28 12:54 |