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
