I have 10 years on you guys and I don't undestand any of that, so congrats.

:)

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

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

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?

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 :surprised:ops:

[quote] I just compiled (a lib for windows) the latest GMP library ant it allows you to play with really big integer numbers[/quote]

Where is it? :-D

Luigi

Where to find the GMP library
 

[quote="ET_"][quote] I just compiled (a lib for windows) the latest GMP library ant it allows you to play with really big integer numbers[/quote]
Where is it? :-D
Luigi[/quote]
Try The GNU MP Home Page at [url]http://www.swox.com/gmp/[/url]

[quote]
Where is it? :-D

Luigi[/quote]

I can upload the compiled lib on my web "site" if someone wants it. It's about 1Mb and works fast on Athlon and Duron.
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.

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

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

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