Active Forums => Programs => Topic started by: david_uwi on June 19, 2021, 01:59:27 pm
Title: multiplication of large numbers - fast method
Post by: david_uwi on June 19, 2021, 01:59:27 pm
Dealing with larger numbers without using strings. This time multiplication using a FFT (fast Fourier transform). No idea how it works, but it does. Essentially it reduces multiplication to addition (which is much faster). Here's the program - it squares a number. The key number is the N it specifies number size. Each number in the array is 2 digits ( 0-99 ) and is generated using "randomize timer". N MUST BE a factor of 2 (that's the way FFTs work). Currently N=256 so it will generate a 512 digit number and square it. It does not have to be squaring the two numbers can be different and it works just the same (but they have to both be multiples of 2 -you could zero fill to get round this). Almost forgot to mention - it also uses imaginary numbers (the array AI contain the imaginary part).
Title: Re: multiplication of large numbers - fast method
Post by: Sanmayce on June 20, 2021, 04:39:57 am
Thank you for sharing!
FFT kicks asses all the way, wanna some day grasp at least the basics, AFAIK it quickly groups similar (by what criteria) data.
You are welcome to include my school-method RTHMTC.bas into your code and check whether the results match.
On that note, have you seen or heard of FFT sort? Once a great algorithmist mentioned that it could easily beat Hoare quicksort, sadly never found anything related.