Results 1 to 3 of 3

Thread: Fortran --> timing factorials

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

    Fortran --> timing factorials

    I made a program to calculate factorials using Fortran.

    Fortran doesn't have a big integer type, so, I had to do everything myself.

    First the program calculates and prints 1000!, as a check. I'm pretty sure it is correct.

    Then it calculates and times factorials up to 200,000.

    The calculations are done using base 10^8. Then, the answers are converted back to base 10 (base 10^1). The conversion is included in each time.

    The speeds are good compared to my earlier attempts, but bad compared to, for instance, Python.

    http://www.thinbasic.com/community/s...5675#post85675

    Whether I can do better, remains to be seen.

    Only the code for the main program is shown, not the module files.

    But, if anyone doubts the results, or wants to see, I will post all.

    ' code (modules not shown) ----------------------------------------------------------------------------------
    
    program fact
    use reg1001
    use reg1008
    use conversions
    use utility
    use time
    
    implicit none
    character(len=5000)::s
    type(reg1001type)::r11
    type(reg1008type)::r81
    integer::i,j
    real::tt
    
    ! First, calculate and print 1000!.
    
    call allocatereg01(r11,numfactorialdigits01(1000))
    call allocatereg08(r81,numfactorialdigits08(1000))
    
    call startclock()
    call factorial08(r81,1000)
    call reg1008toreg1001(r81,r11)
    call stopclock()
    call elapsedtime(tt)
    
    call reversecopyregtostring01(r11,s)
    
    print*
    print'(a)',"1000! = "
    print*
    call printstring(s)
    print*
    
    call deallocatereg01(r11)
    call deallocatereg08(r81)
    
    ! Now, time and print some big factorials.
    
    print'(a)',"n!           t (seconds)"
    
    do i=1,20
    j=i*10000
    
    call allocatereg01(r11,numfactorialdigits01(j))
    call allocatereg08(r81,numfactorialdigits08(j))
    
    call startclock()
    call factorial08(r81,j)
    call reg1008toreg1001(r81,r11)
    call stopclock()
    call elapsedtime(tt)
    
    print'(i6.6,a,f9.3)',j,"      ",tt
    
    call deallocatereg01(r11)
    call deallocatereg08(r81)
    enddo
    
    print*
    
    end program
    
    ' output ----------------------------------------------------------------------------------------------------
    
    C:\Users\root\Desktop\fortran\cat\bin\Release>fact
    
    1000! =
    
    40238726007709377354370243392300398571937486421071463254379991042993851239862902
    05920442084869694048004799886101971960586316668729948085589013238296699445909974
    24504087073759918823627727188732519779505950995276120874975462497043601418278094
    64649629105639388743788648733711918104582578364784997701247663288983595573543251
    31853239584630755574091142624174743493475534286465766116677973966688202912073791
    43853719588249808126867838374559731746136085379534524221586593201928090878297308
    43139284440328123155861103697680135730421616874760967587134831202547858932076716
    91324484262361314125087802080002616831510273418279777047846358681701643650241536
    91398281264810213092761244896359928705114964975419909342221566832572080821333186
    11681155361583654698404670897560290095053761647584772842188967964624494516076535
    34081989013854424879849599533191017233555566021394503997362807501378376153071277
    61926849034352625200015888535147331611702103968175921510907788019393178114194545
    25722386554146106289218796022383897147608850627686296714667469756291123408243920
    81601537808898939645182632436716167621791689097799119037540312746222899880051954
    44414282012187361745992642956581746628302955570299024324153181617210465832036786
    90611726015878352075151628422554026517048330422614397428693306169089796848259012
    54583271682264580665267699586526822728070757813918581788896522081643483448259932
    66043367660176999612831860788386150279465955131156552036093988180612138558600301
    43569452722420634463179746059468257310379008402443243846565724501440282188525247
    09351906209290231364932734975655139587205596542287497740114133469627154228458623
    77387538230483865688976461927383814900140767310446640259899490222221765904339901
    88601856652648506179970235619389701786004081188972991831102117122984590164192106
    88843871218556461249607987229085192968193723886426148396573822911231250241866493
    53143970137428531926649875337218940694281434118520158014123344828015051399694290
    15348307764456909907315243327828826986460278986432113908350621709500259738986355
    42771967428222487575867657523442202075736305694988250879689281627538488633969099
    59826280956121450994871701244516461260379029309120889086942028510640182154399457
    15680594187274899809425474217358240106367740459574178516082923013535808184009699
    63725242305608559037006242712434169090041536901059339838357779394109700277534720
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000000000000000000000000000000000
    00000000
    
    n!           t (seconds)
    010000          1.591
    020000          7.410
    030000         17.503
    040000         32.339
    050000         51.824
    060000         76.269
    070000        105.628
    080000        140.541
    090000        180.259
    100000        224.517
    110000        275.092
    120000        332.095
    130000        393.622
    140000        460.437
    150000        533.118
    160000        610.806
    170000        694.423
    180000        784.186
    190000        876.164
    200000        971.309
    
    C:\Users\root\Desktop\fortran\cat\bin\Release>
    
    Last edited by danbaron; 26-12-2011 at 22:06.
    "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
    Just for something to do, I calculated 300,000 factorial.

    ' code (modules not shown) ----------------------------------------------------------------------------------
    
    program fact
    use reg1001
    use reg1008
    use conversions
    use time
    
    implicit none
    type(reg1001type)::r1
    type(reg1008type)::r8
    integer::n
    real::et
    
    n=300000
    print*
    
    call allocatereg01(r1,numfactorialdigits01(n))
    call allocatereg08(r8,numfactorialdigits08(n))
    
    call startclock()
    call factorial08(r8,n)
    call reg1008toreg1001(r8,r1)
    call stopclock()
    call elapsedtime(et)
    
    print*
    print'(a,f9.3,a)',"calculation time = ",et," seconds"
    print*
    print'(a,i7,a)',"300,000! has ",r1%maxpower+1," decimal digits."
    print*
    
    call deallocatereg01(r1)
    call deallocatereg08(r8)
    
    end program
    
    ' output ----------------------------------------------------------------------------------------------------
    
    C:\Users\root\Desktop\fortran\cat\bin\Release>cat
    
    n!           t (seconds)
    010000          1.669
    020000          7.410
    030000         17.425
    040000         32.261
    050000         51.933
    060000         76.596
    070000        106.549
    080000        141.462
    090000        181.538
    100000        226.903
    110000        277.729
    120000        334.373
    130000        396.399
    140000        463.557
    150000        536.378
    160000        615.112
    170000        699.602
    180000        789.443
    190000        885.243
    200000        986.550
    210000       1093.614
    220000       1206.590
    230000       1325.260
    240000       1449.795
    250000       1579.822
    260000       1715.808
    270000       1857.863
    280000       2005.190
    290000       2158.305
    300000       2316.662
    
    calculation time =  2316.802 seconds
    
    300,000! has 1512852 decimal digits.
    
    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

  3. #3
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    I calculated 300,000 factorial using Racket.

    It took 1385.916 seconds.

    My calculation using Fortran (above), took 2316.802 seconds.

    So, Racket was approximately 2317 / 1386 = 1.67 times as fast.

    But, when I compared my results using Fortran, to Racket's, for multiplying two 10,000 digit integers, Racket was approximately 62 times as as fast.

    http://www.thinbasic.com/community/s...5752#post85752

    Why the discrepancy in time ratios?

    Of course, I don't know what's going on inside Racket, but, my guess is that, it's harder to get a speed improvement using mathematical tricks when multiplying one relatively big integer by one relatively small integer, which is what happens repeatedly in a big factorial calculation, than it is when just multiplying two big integers of the same size.

    ' code -----------------------------------------------------------------------------------------------------------------
    
    #lang racket
    
    (define value 0)
    
    (define (num-digits n)
      (add1 (order-of-magnitude n)))
    
    (define (time-function f n)
      (let ((t1 (current-milliseconds)))
        (set! value (f n))
        (let ((t2 (current-milliseconds)))
          (let ((tt (/ (- t2 t1) 1000.0)))
            tt))))
    
    (define (fact n)
      (define prod 1)
      (define (loop m)
        (cond
          ((> m n) prod)
          (else
           (set! prod (* prod m))
           (loop (+ m 1)))))
      (loop 1))
    
    ' REPL interactions ----------------------------------------------------------------------------------------------------
    
    Welcome to DrRacket, version 5.2 [3m].
    Language: racket.
    > (time-function fact 300000)
    1385.966
    > (num-digits value)
    1512852
    >
    
    "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. Java --> timing factorials
    By danbaron in forum Scripting
    Replies: 1
    Last Post: 22-12-2011, 13:56
  2. Python 3 --> Timing factorials.
    By danbaron in forum Scripting
    Replies: 4
    Last Post: 19-12-2011, 11:26
  3. a fortran environment
    By danbaron in forum Other languages
    Replies: 21
    Last Post: 27-11-2011, 06:50
  4. Lisp: Timing Recursive Factorials
    By danbaron in forum Other languages
    Replies: 0
    Last Post: 18-03-2011, 06:29
  5. C --> Timing a Matrix Inversion
    By danbaron in forum C / C++
    Replies: 16
    Last Post: 05-08-2010, 10:30

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
  •