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).
'The fourier transform I have translated from Fortran and I got it from IEEE transactions (March 1965).
REM N
is the number of two digit numbers
to be loaded
REM so the total number of digits
is 2*N
N = 256
PI = 3.141593
AR
(N
- I
+ 1) = INT(RND * 100)N = N * 4
M = M + 2
AR(I) = AR(I) / N
AI(I) = AI(I) / N
AR(I) = AR(I) * AR(I) - AI(I) * AI(I)
AI(I) = 2 * AR(I) * AI(I)
AR(J) = AR(J) * N
BR(1) = AR(1): BR(N / 2 + 1) = AR(N / 2 + 1)
K = N - I + 2
BR(I) = AR(I) + AR(K)
IC = 0
BR(I) = BR(I) + IC
IC = BR(I) \ 100
CooleyTukey:
J = 1
K = N / 2
J = J - K
K = K / 2
J = J + K
LE = 2 ^ L
LE1 = LE / 2
UR = 1!: UI = 0!
ANG = PI / LE1
IP = I + LE1
TR = AR(IP) * UR - AI(IP) * UI
ti = AR(IP) * UI + AI(IP) * UR
AR(IP) = AR(I) - TR
AI(IP) = AI(I) - ti
AR(I) = AR(I) + TR
AI(I) = AI(I) + ti
URT = UR * WR - UI * WI
UI = UR * WI + UI * WR
UR = URT