mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-05-30, 08:50   #1
Dresdenboy
 
Dresdenboy's Avatar
 
Apr 2003
Berlin, Germany

192 Posts
Default 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
Dresdenboy is offline   Reply With Quote
Old 2003-05-30, 09:08   #2
Axel Fox
 
Axel Fox's Avatar
 
May 2003

6016 Posts
Default

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.
Axel Fox is offline   Reply With Quote
Old 2003-05-30, 09:16   #3
Dresdenboy
 
Dresdenboy's Avatar
 
Apr 2003
Berlin, Germany

192 Posts
Default

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 :)
Dresdenboy is offline   Reply With Quote
Old 2003-05-30, 09:45   #4
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25×3 Posts
Default

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

Axel Fox.
Axel Fox is offline   Reply With Quote
Old 2003-06-02, 17:23   #5
Dresdenboy
 
Dresdenboy's Avatar
 
Apr 2003
Berlin, Germany

36110 Posts
Default

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
Dresdenboy is offline   Reply With Quote
Reply

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.