20030320, 22:13  #23  
Aug 2002
3×83 Posts 
Re: Prime95 secret
Quote:


20030321, 01:17  #24 
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
Re: Prime95 secret
Edited  Well, it seems I made several mistakes in what I posted here, so I've erased it all to avoid misleading anyone.

20030321, 02:02  #25  
∂^{2}ω=0
Sep 2002
República de California
3^{2}·1,297 Posts 
Re: Prime95 secret
Quote:
Quote:


20030321, 02:23  #26  
∂^{2}ω=0
Sep 2002
República de California
3^{2}·1,297 Posts 
Re: IBWDT
Quote:
1) The term "irrational base" is somewhat misleading, since one isn't actually using fractional bases; rather, one is using a mixture of two wholenumber bases, which together have an effect equivalent to the use of a fractional base. In your base10 example, if we were using IBDWT we might be using a mixture of bases 10 and 100, for example. 2) If you read my post in the thread "FFT explanation for nonmath guys," you'll see the example where by simply doing a lengthN DFTbased squaring with a fixed base X, we automatically get a square modulo X^N  1. This is what I refer to as the "folding" property of DFTbased squaring: it has the same effect as if you wrote out your two input vectors as polynomials over X (i.e. the elements of the vectors would be the coefficients of the various powers of X, from 0 to N1), calculated the full polynomial product (which would have powers of X ranging from 0 to 2*N1, with the topmst coefficient, the one multiplying X^(2*N1) being zero), then "folded" the upper N1 coefficients in with the lower N1 ones. What the IBDWT allows one to do is to use a DFT to accomplish this folding, EVEN WHEN THE POWER N DOES NOT DIVIDE THE DFT LENGTH. For Mersenne numbers, the exponents p are primes, so no possible DFT length < p could divide p, yet we can still proceed as if it did, with a little bit of extra work (the preandpostmultpilication by the DWT weight factors, which needs just O(N) operations, i.e. is asymptotically cheaper than the DFT itself.) 

20030321, 03:31  #27 
Oct 2002
43 Posts 
It's worth noting that the "rightangle" FFT for multiplying two N bit integers over Z is exactly the same as multiplying modulo 2^N+(1)i using the DWT I describe in my paper.

20030321, 16:26  #28  
Mar 2003
81_{10} Posts 
Quote:
I have ment "schoolboymultiplication", in other words, "long multiplication" 

20030321, 17:36  #29  
Mar 2003
121_{8} Posts 
Quote:
It DOES really work!!! Quote:
but that is trivial and not pure the light about "additional clever tricks" you wrote about. Please, listen to me. I'm quite stupid poor guy, even not American :( Would you give me a short NUMERICAL example, for two digits or three, module 13 or 127, or nonprime module at all? I have the FFT procedure, and I can multiply by means of it, but cannot multiply modularly. I dont want touch my FFT procedure and build something in! I only want to call it without zeropadding to achieve modular multiplication. Is it possible? Sure... The gramm of practice is better than the tone of theory ;) It wouldn't take you a lot of time to give a short numerical example, would it? You needn't explain me what is FFT and you may write: "convolution goes here". In principle, one can make i,jstupid convolution and summing two halves. The result will be the same as it were FFTiFFT. The most interesting example probably is how to calculate 123*876 (mod 1000) . The FFT contains four digits (with one leading zero), and the virtual base is 1001^(1/4), about 5.6................ Plzzz, give me this example. 

20030323, 14:29  #30 
Mar 2003
3^{4} Posts 
*** 2 awmayer
There is no answer... You probably is very busy, sorry. I have downloaded "Rapid Multiplication Modulo..." and I'm reading this article now. It's not very difficult to understand how vectors are weighted. But what do upperangular brackets mean? ._ _.  j/N  j/N Thank you in advancе. 
20030323, 18:04  #31 
Mar 2003
3^{4} Posts 
Probably, it means []  integer part.
But if so, this DWT is useful for mersenne numbers, and useless for other modulo. For instance, I want multiply modulo 101, but for two digits [0/2]=0 and [1/2]=0. How can I build the polynomial? How can I use *truly irrational base* that is not drawback since we use floating point? 
20030324, 06:31  #32 
Mar 2003
3^{4} Posts 
I want to say modulo (101  1)...

20030324, 10:56  #33 
Mar 2003
3^{4} Posts 
At the end of all ends I have understood how
to perform IBWDT. Let's multiply modulo 100 by 2element FFT, 12 by 97 mod 100. For instance, 100 = 128  28 = 2^7  2^2*7. Radix is ( 1 2^3*2^(1) ) Weight is ( 1 2^(0.5)*7^0.5 ) Our numbers in radixform are (0 3) and (1 24) Convolution gives (252 3), that is indeed 64 mod 100 But it seems WDT is a piecegoods and it needs a quite difficult tuning for each particular modulo. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
why is http://www.mersenne.org/ so slow  Unregistered  Information & Answers  19  20120417 03:12 
Slow Down?  R.D. Silverman  GMPECM  55  20111016 17:28 
How hot is too hot? Slow is too slow?  petrw1  Hardware  13  20081110 23:25 
Slow computer  Housemouse  Hardware  7  20080215 18:18 
Really slow machines?  Doorbasher  Hardware  5  20040823 22:18 