multiplication of large numbers - fast method

[david_uwi]

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

Code: QB64: [Select]

1.  
2. 'The fourier transform I have translated from Fortran and I got it from IEEE transactions (March 1965).
3.  
4. TT = TIMER
5. DEFSNG A-F, P-Z
6. DEFINT G-O
7. RANDOMIZE TIMER
8. REM N is the number of two digit numbers to be loaded
9. REM so the total number of digits is 2*N
10. N = 256
11. DIM AR(N * 4), AI(N * 4)
12. DIM BR(N * 2 + 1) AS LONG, IC AS LONG
13. M = INT(LOG(N) / LOG(2) + .5)
14. PI = 3.141593
15. FOR I = 1 TO N
16.     AR(N - I + 1) = INT(RND * 100)
17. NEXT I
18. PRINT: PRINT "Number to be squared"
19. FOR I = N TO 1 STEP -1
20.     Q$ = "0" + LTRIM$(STR$(AR(I)))
21.     Q$ = RIGHT$(Q$, 2)
22.     PRINT Q$;
23. NEXT I
24. N = N * 4
25. M = M + 2
26. PRINT
27. GOSUB CooleyTukey
28. FOR I = 1 TO N
29.     AR(I) = AR(I) / N
30.     AI(I) = AI(I) / N
31.     AR(I) = AR(I) * AR(I) - AI(I) * AI(I)
32.     AI(I) = 2 * AR(I) * AI(I)
33. NEXT I
34. GOSUB CooleyTukey
35. FOR J = 1 TO N
36.     AR(J) = AR(J) * N
37. NEXT J
38. BR(1) = AR(1): BR(N / 2 + 1) = AR(N / 2 + 1)
39. FOR I = 2 TO N / 2
40.     K = N - I + 2
41.     BR(I) = AR(I) + AR(K)
42. NEXT I
43. IC = 0
44. FOR I = 1 TO N / 2 + 1
45.     BR(I) = BR(I) + IC
46.     IC = BR(I) \ 100
47.     BR(I) = BR(I) MOD 100
48. NEXT I
49. PRINT "OUTPUT...."
50. FOR I = N / 2 + 1 TO 1 STEP -1
51.     Q$ = "0" + LTRIM$(STR$(BR(I)))
52.     Q$ = RIGHT$(Q$, 2)
53.     PRINT Q$;
54. NEXT I
55. PRINT: PRINT "TIME TAKEN = "; TIMER - TT
56. END
57. CooleyTukey:
58. J = 1
59. FOR I = 1 TO N - 1
60.     IF I < J THEN
61.         SWAP AR(I), AR(J)
62.         SWAP AI(I), AI(J)
63.     END IF
64.     K = N / 2
65.     WHILE K < J
66.         J = J - K
67.         K = K / 2
68.     WEND
69.     J = J + K
70. NEXT I
71. FOR L = 1 TO M
72.     LE = 2 ^ L
73.     LE1 = LE / 2
74.     UR = 1!: UI = 0!
75.     ANG = PI / LE1
76.     WR = COS(ANG): WI = SIN(ANG)
77.     FOR J = 1 TO LE1
78.         FOR I = J TO N STEP LE
79.             IP = I + LE1
80.             TR = AR(IP) * UR - AI(IP) * UI
81.             ti = AR(IP) * UI + AI(IP) * UR
82.             AR(IP) = AR(I) - TR
83.             AI(IP) = AI(I) - ti
84.             AR(I) = AR(I) + TR
85.             AI(I) = AI(I) + ti
86.         NEXT I
87.         URT = UR * WR - UI * WI
88.         UI = UR * WI + UI * WR
89.         UR = URT
90.     NEXT J
91. NEXT L
92. RETURN
93.  

[Sanmayce]

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.