Author Topic: multiplication of large numbers - fast method  (Read 3281 times)

0 Members and 1 Guest are viewing this topic.

Offline david_uwi

  • Newbie
  • Posts: 71
    • View Profile
multiplication of large numbers - fast method
« 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).
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. REM N is the number of two digit numbers to be loaded
  8. REM so the total number of digits is 2*N
  9. N = 256
  10. DIM AR(N * 4), AI(N * 4)
  11. DIM BR(N * 2 + 1) AS LONG, IC AS LONG
  12. M = INT(LOG(N) / LOG(2) + .5)
  13. PI = 3.141593
  14. FOR I = 1 TO N
  15.     AR(N - I + 1) = INT(RND * 100)
  16. PRINT: PRINT "Number to be squared"
  17. FOR I = N TO 1 STEP -1
  18.     Q$ = "0" + LTRIM$(STR$(AR(I)))
  19.     Q$ = RIGHT$(Q$, 2)
  20.     PRINT Q$;
  21. N = N * 4
  22. M = M + 2
  23. GOSUB CooleyTukey
  24. FOR I = 1 TO N
  25.     AR(I) = AR(I) / N
  26.     AI(I) = AI(I) / N
  27.     AR(I) = AR(I) * AR(I) - AI(I) * AI(I)
  28.     AI(I) = 2 * AR(I) * AI(I)
  29. GOSUB CooleyTukey
  30. FOR J = 1 TO N
  31.     AR(J) = AR(J) * N
  32. BR(1) = AR(1): BR(N / 2 + 1) = AR(N / 2 + 1)
  33. FOR I = 2 TO N / 2
  34.     K = N - I + 2
  35.     BR(I) = AR(I) + AR(K)
  36. IC = 0
  37. FOR I = 1 TO N / 2 + 1
  38.     BR(I) = BR(I) + IC
  39.     IC = BR(I) \ 100
  40.     BR(I) = BR(I) MOD 100
  41. PRINT "OUTPUT...."
  42. FOR I = N / 2 + 1 TO 1 STEP -1
  43.     Q$ = "0" + LTRIM$(STR$(BR(I)))
  44.     Q$ = RIGHT$(Q$, 2)
  45.     PRINT Q$;
  46. PRINT: PRINT "TIME TAKEN = "; TIMER - TT
  47. CooleyTukey:
  48. J = 1
  49. FOR I = 1 TO N - 1
  50.     IF I < J THEN
  51.         SWAP AR(I), AR(J)
  52.         SWAP AI(I), AI(J)
  53.     END IF
  54.     K = N / 2
  55.     WHILE K < J
  56.         J = J - K
  57.         K = K / 2
  58.     WEND
  59.     J = J + K
  60. FOR L = 1 TO M
  61.     LE = 2 ^ L
  62.     LE1 = LE / 2
  63.     UR = 1!: UI = 0!
  64.     ANG = PI / LE1
  65.     WR = COS(ANG): WI = SIN(ANG)
  66.     FOR J = 1 TO LE1
  67.         FOR I = J TO N STEP LE
  68.             IP = I + LE1
  69.             TR = AR(IP) * UR - AI(IP) * UI
  70.             ti = AR(IP) * UI + AI(IP) * UR
  71.             AR(IP) = AR(I) - TR
  72.             AI(IP) = AI(I) - ti
  73.             AR(I) = AR(I) + TR
  74.             AI(I) = AI(I) + ti
  75.         NEXT I
  76.         URT = UR * WR - UI * WI
  77.         UI = UR * WI + UI * WR
  78.         UR = URT
  79.     NEXT J
  80.  
« Last Edit: June 19, 2021, 02:03:01 pm by david_uwi »

Offline Sanmayce

  • Newbie
  • Posts: 63
  • Where is that English Text Sidekick?
    • View Profile
    • Sanmayce's home
Re: multiplication of large numbers - fast method
« Reply #1 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.
He learns not to learn and reverts to what all men pass by.