But if you write all 10 cases, aren't the lists constructed anyway before calling `*'?
On Tue, Apr 9, 2013 at 2:00 PM, Pierpaolo Bernardi <olopie...@gmail.com>wrote: > Or, more lispy: > > ;; from included; to excluded. > (define (mult from to) > (case (- to from) > ((0) 1) > ((1) from) > ((2) (* from (+ from 1))) > ((3) (* from (+ from 1) (+ from 2))) > ;; ... > (else > (let ((middle (quotient (+ from to) 2))) > (* (mult from middle) (mult middle to)))))) > > (define (fact n) > (if (zero? n) > 1 > (mult 2 (add1 n)))) > > > > On Tue, Apr 9, 2013 at 1:43 PM, Pierpaolo Bernardi <olopie...@gmail.com>wrote: > >> But why generate lists which are immediately discarded? >> >> ;; from excluded; to included >> (define (mult from to) >> (case (- to from) >> ((0) 1) >> ((1) to) >> ((2) (* (- to 1) to)) >> ((3) (* (- to 2) (- to 1) to)) >> ;; ... >> (else >> (let ((middle (quotient (+ from to) 2))) >> (* (mult from middle) (mult middle to)))))) >> >> (define (fact n) >> (if (zero? n) >> 1 >> (mult 1 n))) >> >> >> >> On Tue, Apr 9, 2013 at 12:05 PM, Laurent <laurent.ors...@gmail.com>wrote: >> >>> >>> On Mon, Apr 8, 2013 at 9:34 PM, Bradley Lucier >>> <luc...@math.purdue.edu>wrote: >>> >>>> (define (iota m n) >>>> (let loop ((result '()) >>>> (n (- n 1))) >>>> (if (<= m n) >>>> (loop (cons n result) >>>> (- n 1)) >>>> result))) >>>> >>>> (define (partial-factorial m n) >>>> ;; computes the product (m+1) * ... * (n-1) * n >>>> (if (< (- n m) 10) >>>> (apply * (iota (+ m 1) (+ n 1))) >>>> (* (partial-factorial m (quotient (+ m n) 2)) >>>> (partial-factorial (quotient (+ m n) 2) n)))) >>>> >>>> (define (factorial n) >>>> (partial-factorial 0 n)) >>>> >>>> In Gambit, even in the interpreter, this is pretty fast: >>>> >>>> (define a (time (factorial 1000000))) >>>> (time (factorial 1000000)) >>>> >>> >>> >>> Indeed, it's impressively fast! >>> % racket fast-factorial.rkt >>> cpu time: 5760 real time: 5771 gc time: 28 >>> >>> Probably this should replace the default factorial version then. >>> >>> Laurent >>> >>> ____________________ >>> Racket Users list: >>> http://lists.racket-lang.org/users >>> >>> >> >
____________________ Racket Users list: http://lists.racket-lang.org/users
