The binary multiply convolution approach

Dresdenboy · 2003-05-30, 08:50

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

Axel Fox · 2003-05-30, 09:08

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.

Dresdenboy · 2003-05-30, 09:16

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 :)

Axel Fox · 2003-05-30, 09:45

Hmm, I think I'll leave it up to the math guys, I don't know that much about FFT's. Sorry.

Axel Fox.

Dresdenboy · 2003-06-02, 17:23

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

2003-05-30, 08:50	#1
Dresdenboy Apr 2003 Berlin, Germany 19² 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 xx 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

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

2003-05-30, 09:08	#2
Axel Fox May 2003 2⁵×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
Dresdenboy Apr 2003 Berlin, Germany 19² 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 2⁵×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 19² 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