Interesting. This is the timing on Mac. Comparing to Alex's result, the numbers roughly match "< 7s" v.s. "> 13s" while fact-1 is close.
$ racket Welcome to Racket v7.2.0.3. > (enter! "factorial.rkt") "factorial.rkt"> (equal? (fact 100000) (fact-1 100000)) #t "factorial.rkt"> (time (void (fact-1 100000))) cpu time: 313 real time: 314 gc time: 2 "factorial.rkt"> (time (void (fact 100000))) cpu time: 6185 real time: 6265 gc time: 974 The GC time of fact differs a lot. On Sun, Mar 24, 2019 at 9:26 PM Alex Harsanyi <alexharsa...@gmail.com> wrote: > > You can check if the big number multiplication is the problem, by using a > factorial version which does not need so many big number multiplications: > > #lang racket/base > (require racket/math) > (define (fact n) > (if (zero? n) 1 (* n (fact (- n 1))))) > > (define (fact-1 n) > (define nslots (exact-truncate (sqrt n))) > (if (<= nslots 1) > (fact n) ;; use simple implementation for small numbers > (let ((slot (make-vector nslots 1))) > (for ([x (in-range 1 (add1 n))]) > (define index (modulo x nslots)) > (vector-set! slot index (* (vector-ref slot index) x))) > (for/fold ([result 1]) > ([n (in-vector slot)]) > (* result n))))) > > On my Windows machine, the difference between the two is huge: 16.7 seconds > for `fact` (your original implementation) and only 0.5 seconds for `fact-1` > > > (equal? (fact 100000) (fact-1 100000)) > #t > > (time (void (fact-1 100000))) > cpu time: 469 real time: 468 gc time: 111 > > (time (void (fact 100000))) > cpu time: 16797 real time: 16782 gc time: 7082 > > > > > > On Monday, March 25, 2019 at 1:20:33 AM UTC+8, Phil Nguyen wrote: >> >> With Racket 7.2, the following program takes >13 seconds to run on Windows, >> and <7 seconds on Linux either on Virtualbox on the same machine, or native >> Linux on another machine with slightly lower-powered processor: >> >> #lang racket/base >> (define (fact n) >> (if (zero? n) 1 (* n (fact (- n 1))))) >> (time (void (fact 100000))) >> >> ; Windows native, i7-7660U >> ; cpu time: 13610 real time: 13633 gc time: 4459 >> ; Linux on Virtualbox, i7-7660U >> ; cpu time: 6691 real time: 6706 gc time: 1298 >> ; Linux native, i7-8500Y: >> ; cpu time: 6894 real time: 6882 gc time: 1129 >> >> >> >> While the difference is unlikely to matter in practice, given `fact 100000` >> is a very large number, I'm curious what accounts for this difference? Is it >> some big-integer library that Racket relies on? > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
