20120104, 06:53  #1 
3×23^{2} Posts 
some FFT Mul questions
as I like programming, and I like math, the mersenne prime search is really interesting for me.
I've implemented my little math lib and I try to improve it, now I'm at the point where I want to optimze my toomcook mul by the schoenhageâ€“strassen algorithm (I mean, I'll use it for numbers beyond some value), and as a first step I try to grasp the integer multiply (I think the schoenhageâ€“strassen algorithm is just a specialized case of the FFT mul(?)). so, I've got most of it, but I've some open questions I can't find any answer for (feel free to save your time by just posting related links). I've implemented my first version based on the summary of this svg: http://en.wikipedia.org/wiki/File:In...ion_by_FFT.svg first question is rather to satisfy my theoretical understanding: PowerMod[Length[x], 1, b]; is actually a call to find the multiplicative inverse in the ring of b(337), using the euclid algorithm is the proper way I guess? and if the result is <0, I guess it's correct to bring it within the bounds of the ring, but modulo of something negative is (in this case 42 >295) will result in 42, is there a proper name for this operation? 2. how to choose b? I found that not all primes >324 work, actually, most don't work, at least the result seem to be wrong. I think my implementation is correct, is it expected that most primes don't work? is there a smarter way than try&error to find working primes? 3. r is 85, as it's the 8th root of unit in 337, but how do I calculate this? atm, I've just a lame loop trying all possible numbers to find the 8th root, is there an algorithm? I can find some info about nthroot calculation and about the root of unity calculation, but the nth root? (not just for power of 2, or is the NTT transform just working on PO2 sizes, like FFT?) ( 4. the NTT transform in the summary is O(n*n), I shall be able to convert it to a fast O(n*log(n)) version, just like FT>FFT? any concerns?) 5. not really a question, but, if you have any links with good informations on this topic, I'd appreciate if you'd share them with me. I do that all because of my joy of math and I want to fully understand this topic. 
20120104, 14:46  #2 
(loop (#_fork))
Feb 2006
Cambridge, England
13·491 Posts 
I don't know a name for the operation 'add p until not negative then reduce mod p', but it's the one you need.
To do an NTT on X terms, there has to be an Xth root of unity mod p, which means that (by Lagrange's theorem) p must be ==1 mod X. To find the Xth root of unity, start with a primitive root mod p, and take the (p1)/X th power of it ... to check whether some q is a primitive root mod p, check that q^R is not =1 mod p whenever R is a factor of (p1). 
20120104, 15:40  #3  
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
Quote:
Anyone care to suggest a name for it? How about "Division"? David Last fiddled with by davieddy on 20120104 at 15:44 

20120104, 16:20  #4 
"Forget I exist"
Jul 2009
Dumbassville
10000011000000_{2} Posts 

20120105, 01:50  #5 
Tribal Bullet
Oct 2004
2^{4}×13×17 Posts 
I've usually seen it referred to as 'normalization', or 'modular reduction' sometimes. Allowing negative numbers when they aren't strictly necessary, i.e. p < x < p, is a redundant representation, and removing the redundancy so that p/2 <= x < p/2 is called balanced representation by Crandall.

20120126, 14:50  #6  
Nov 2011
14_{8} Posts 
Quote:
Example: 8/2=4. 337=2^{4}*21. Take a number, let it be 2. Calculate 2^{4*21} mod 337 = 1. But must be 1. So 2 is not eligible. Let take 3. 3^{4*21} mod 337 = 336 = 1. 3 is eligible. Calculate r=3^{21} mod 337 = 252. So r^{4} mod 337 = 336 = 1. (And r^{8} mod 337 = 1). So r is 8th root of unity in 337. Other roots of unity are: r^{3} mod 337 = 252^{3} mod 337 = 226; r^{5} mod 337 = 252^{5} mod 337 = 85; r^{7} mod 337 = 252^{7} mod 337 = 111. Quote:
Fast NTT is similar to FFT, but uses modular arithmetics instead of complex number arithmetics. 

20120126, 16:36  #7 
Tribal Bullet
Oct 2004
110111010000_{2} Posts 
The typical method for calculating a root of unity is to start with numbers modulo p, a prime of the form k*2^n+1 where n is large. Pick a number g < p and then for each unique prime factor q of k*2^n verify that g^((p1)/q) != 1 mod p. Any g for which you can show this is then a primitive root of order k*2^n, i.e. a root of unity that allows a Fourierlike transform of size k*2^n.
For a transform size smaller than that, say size N, just make g^((p  1)/N) mod p the root of unity. For poweroftwo sizes a numbertheoretic FFT looks a lot like an FFT over the complex numbers, but it doesn't use complex arithmetic. For nonpoweroftwo sizes I think that it's more complicated, you cannot just take a floatingpoint FFT and replace the arithmetic operations. 
20120126, 18:59  #8  
Nov 2011
2^{2}·3 Posts 
some corrections
Quote:
I mean one step; one iteration takes O(SIZE*pi) of time. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Two questions:  Dubslow  GPU Computing  1  20110805 18:22 
Questions about the QS  Carmichael  Factoring  8  20070410 11:30 
Questions  OmbooHankvald  Prime Sierpinski Project  2  20050801 20:18 
LLR questions  OmbooHankvald  Math  6  20050623 11:42 
A few questions :)  xtreme2k  Lounge  59  20021031 06:20 