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
