Results 1 to 2 of 2

Thread: Faster Standard Multiplication

  1. #1
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152

    Faster Standard Multiplication

    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>
    
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  2. #2
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    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
    >
    
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Similar Threads

  1. Faster than light
    By zak in forum Shout Box Area
    Replies: 42
    Last Post: 24-02-2012, 22:33
  2. Toom-Cook Multiplication
    By danbaron in forum Math: all about
    Replies: 9
    Last Post: 09-12-2011, 00:25
  3. Is it possible to draw this simple map faster?
    By Michael Hartlef in forum TBGL General
    Replies: 22
    Last Post: 02-12-2007, 09:59

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •