<div dir="ltr">But why generate lists which are immediately discarded?<div><br></div><div style>;; from excluded; to included</div><div><div>(define (mult from to)</div><div> (case (- to from)</div><div> ((0) 1)</div><div>
((1) to)</div><div> ((2) (* (- to 1) to))</div><div> ((3) (* (- to 2) (- to 1) to))</div><div> ;; ...</div><div> (else</div><div> (let ((middle (quotient (+ from to) 2)))</div><div> (* (mult from middle) (mult middle to))))))</div>
</div><div><br></div><div><div>(define (fact n)</div><div> (if (zero? n)</div><div> 1</div><div> (mult 1 n)))</div></div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Apr 9, 2013 at 12:05 PM, Laurent <span dir="ltr"><<a href="mailto:laurent.orseau@gmail.com" target="_blank">laurent.orseau@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="im"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Apr 8, 2013 at 9:34 PM, Bradley Lucier <span dir="ltr"><<a href="mailto:lucier@math.purdue.edu" target="_blank">lucier@math.purdue.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>(define (iota m n)<br>
(let loop ((result '())<br>
(n (- n 1)))<br>
(if (<= m n)<br>
(loop (cons n result)<br>
(- n 1))<br>
result)))<br>
<br>
(define (partial-factorial m n)<br>
;; computes the product (m+1) * ... * (n-1) * n<br>
(if (< (- n m) 10)<br>
(apply * (iota (+ m 1) (+ n 1)))<br>
(* (partial-factorial m (quotient (+ m n) 2))<br>
(partial-factorial (quotient (+ m n) 2) n))))<br>
<br>
(define (factorial n)<br>
(partial-factorial 0 n))<br>
<br>
In Gambit, even in the interpreter, this is pretty fast:<br>
<br>
(define a (time (factorial 1000000)))<br>
(time (factorial 1000000))</div></blockquote></div><br><br></div></div><div class="gmail_extra">Indeed, it's impressively fast!<br>% racket fast-factorial.rkt <br>cpu time: 5760 real time: 5771 gc time: 28<br><br></div>
<div class="gmail_extra">
Probably this should replace the default factorial version then.<span class="HOEnZb"><font color="#888888"><br><br>Laurent<br></font></span></div></div>
<br>____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
<br></blockquote></div><br></div>