20021106, 20:40  #12 
Sep 2002
2^{2} Posts 
I have 10 years on you guys and I don't undestand any of that, so congrats.
:) 
20021106, 21:54  #13 
Sep 2002
3^{2}×13 Posts 
lol... it's mostly experience. The longer you've been playing with numbers (especially primes and how to use mods to test for primes) the better you'll get it. My (now retired) physics prof is around 85, and he's amazing at some of this stuff even though he can't multiply in his head any more (due to a form of Parkinsen's I think).

20021109, 01:00  #14 
Aug 2002
Dawn of the Dead
5×47 Posts 
ahhh, experience ....
About two years ago I programmed a PLC to perform a linear regression. I needed a sturdy tool, able to withstand life on the mill floor, so I could process data while recording it. So, I wrote this crazy algorithm to do the regression without overflowing (Allen Bradley cpu instruction set is pretty weak) and brought it to the instrumentation shop and told them to insert is as one of the final rungs. The electrical engineer in charge of the shop nearly threw a rod when he realized what I was doing with the PLC 
20021110, 18:40  #15 
11054_{8} Posts 
Tnx for the info!
I've really searched a lot for some nice information like this but it was always with difficult formulas i didn't understand or some 100kB source code files. I'm going to give it a try now to implement a fft. The only thing i need now is some test case bignumbers to test with. I can multiply some 100 digit numbers myself with just to 'normal' multiply in a little program, but where can i find some test cases with 10.000 digits numbers or much bigger? 
20030210, 22:39  #16 
Feb 2003
2×59 Posts 
So you want to multiply big numbers? If you have a windows based system you might be lucky. I just compiled (a lib for windows) the latest GMP library ant it allows you to play with really big integer numbers (I tested it over 10M digits). It comes with a nice header (for C). Another thing, I compiled it for Athlon (the blended one is slower) so I have no ideea if it works on other CPU's....
BTW, I wanted to see how fast is the integer FFT code in GMP so I wrote a LL and ... it's 6X slower than Prime95 ops: 
20030211, 16:24  #17  
Banned
"Luigi"
Aug 2002
Team Italia
4827_{10} Posts 
Quote:
Luigi 

20030211, 19:04  #18  
"Richard B. Woods"
Aug 2002
Wisconsin USA
1111000001100_{2} Posts 
Where to find the GMP library
Quote:


20030211, 21:42  #19  
Feb 2003
2·59 Posts 
Quote:
The source code can be found at http://www.swox.com/gmp/ but yo will need a Unix emulator and a bit of patience to compile it on Windows. 

20030215, 00:20  #20 
Feb 2003
Norway
2^{3}×7 Posts 
Thanks to ewmayer for a readable intro to Fourier/DFT/FFT  I've also looked for that, and failed.
I have a Master in AI/pattern recognition, and I've actually used Fourier. I never understood the math, though, and I couldn't really see any natural connection between "split up a signal to its constutients, and use the resulting distribution to compress and/or do pattern recognition on the original signal" and the "find large primes" problem. I have too little math, of course  even six years at university didn't give me enough math to understand the Fourier transform. Shame on me, perhaps, but it's not just "barely 14's" who benefit from a readable explanation of "what's happening here?". I'm happy to finally understand what I did at university :) 
20040702, 04:46  #21 
Jun 2003
11000101110_{2} Posts 
ewmayer,
A quick question. If I wanted to multiply two, 3 digit numbers then how do I do the transform? What is the general forumula to do transforms for two n digit numbers? Also what about the inverse?What is the general formula for this? Also as I understand that after multiplying the numbers, you have to take the mod. How does one achieve this real fast. Is there a faster algorithm than dividing and then looking at the remainder? Also, let me tell you that your explanation is really good, the best I can find on the web. Thanks, Citrix 
20040702, 05:12  #22 
Jun 2003
2·7·113 Posts 
I am also curious, that if someone found a faster algorithm to multiply numbers, then will it have any applications in any other fields like FFT, or will it only help mathematics (number theory).
Citrix 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any technology you guys are excited about?  jasong  Lounge  31  20151009 20:55 
These dell guys can't possibly be serious...  Unregistered  Hardware  12  20061103 03:53 
You guys are famous  jasong  Sierpinski/Riesel Base 5  1  20060322 01:06 
Hi guys !  Crystallize  Lounge  6  20030927 13:08 
How do you guys do this?  ThomRuley  Lone Mersenne Hunters  1  20030529 18:17 