Faster Standard Multiplication

[danbaron]

I was able to improve the speeds I get using Fortran to implement standard multiplication.

By, "standard multiplication", I mean the way you would multiply 123 times 456, with a pencil and paper.

Below is a test program and its output.

The support modules are not shown.

But, upon request I would post them.

In the program, first two random integers of "n" digits are generated in base 10.

Then, the two base 10 integers are converted to base 10^8.

The multiplication is performed in base 10^8.

And, the product is converted back to base 10.

So, the program multiplies two decimal n digit random integers, for n equals 10,000 to 100,000.

The time (the time includes the base conversions) is shown in the output for each multiplication.

For my computer, the times seem pretty fast.


' code (modules not shown) ----------------------------------------------------------------------------------------------

program cat
use conversions
use random
use reg1001
use reg1008
use time

implicit none

type(reg1001type)::r11,r12,r13
type(reg1008type)::r81,r82,r83
real::et
integer::i,j

call allocateseeds()
call setdefaultseed()

print*
print'(a)','n seconds'

do i=10000,100000,10000
j=i/8+1

call allocatereg01(r11,i)
call allocatereg01(r12,i)
call allocatereg01(r13,2*i)
call allocatereg08(r81,j)
call allocatereg08(r82,j)
call allocatereg08(r83,2*j)
call setrandomreg01(r11)
call setrandomreg01(r12)

call startclock()
call reg1001toreg1008(r11,r81)
call reg1001toreg1008(r12,r82)
call fasterstandardmult08(r81,r82,r83)
call reg1008toreg1001(r83,r13)
call stopclock()
call elapsedtime(et)

print'(i6, f9.3)',i,et

call deallocatereg01(r11)
call deallocatereg01(r12)
call deallocatereg01(r13)
call deallocatereg08(r81)
call deallocatereg08(r82)
call deallocatereg08(r83)

enddo
print*

end program

' output ----------------------------------------------------------------------------------------------------------------

C:\Users\root\Desktop\fortran\cat\bin\Release>cat

n seconds
10000 0.250
20000 0.998
30000 2.231
40000 3.978
50000 6.271
60000 8.939
70000 12.246
80000 16.037
90000 20.202
100000 24.960

C:\Users\root\Desktop\fortran\cat\bin\Release>

[danbaron]

I wanted to see how fast my results were compared to something that I know multiplies fast.

So, I made a comparison to Racket.

Using Racket, I found that 2889^2889 has 9999 digits, and, 2890^2890 has 10002 digits.

So, multiplying them, should take close to as long as multiplying two 10000 digit integers.

In Racket, I multiplied them, and timed the multiplication.

It took 0.004 seconds.

From above, my multiplication of two 10000 digit integers took 0.250 seconds.

So, Racket does the multiplication approximately 62 times as fast.

My guess is that Racket is using the Fast Fourier Transform.

If I can understand it, maybe I can implement multiplication using the FFT.

(Otherwise, most likely I can't.)


' code ----------------------------------------------------------------------------------

#lang racket

(define (num-digits n)
(add1 (order-of-magnitude n)))

(define (time-function f m n)
(let ((t1 (current-milliseconds)))
(f m n)
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
tt))))

' REPL interactions ---------------------------------------------------------------------

Welcome to DrRacket, version 5.2 [3m].
Language: racket.
> (define a (expt 2889 2889))
> (num-digits a)
9999
> (define b (expt 2890 2890))
> (num-digits b)
10002
> (time-function * a b)
0.004
>