<div dir="ltr">But if you write all 10 cases, aren't the lists constructed anyway before calling `*'?<br><br></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Apr 9, 2013 at 2:00 PM, Pierpaolo Bernardi <span dir="ltr"><<a href="mailto:olopierpa@gmail.com" target="_blank">olopierpa@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>Or, more lispy:</div><div><br></div><div>;; from included; to excluded.</div><div class="im"><div> (define (mult from to)</div> <div> (case (- to from)</div><div> ((0) 1)</div></div><div> ((1) from)</div><div> ((2) (* from (+ from 1)))</div><div> ((3) (* from (+ from 1) (+ from 2)))</div><div class="im"><div> ;; ...</div><div> (else</div><div> (let ((middle (quotient (+ from to) 2)))</div><div> (* (mult from middle) (mult middle to))))))</div> <div><br></div><div>(define (fact n)</div><div> (if (zero? n)</div><div> 1</div></div><div> (mult 2 (add1 n))))</div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote"> On Tue, Apr 9, 2013 at 1:43 PM, Pierpaolo Bernardi <span dir="ltr"><<a href="mailto:olopierpa@gmail.com" target="_blank">olopierpa@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">But why generate lists which are immediately discarded?<div><br></div><div>;; 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"><div><div> 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> </div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr"><div><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><font color="#888888"><br><br>Laurent<br></font></span></div></div> <br></div></div><div>____________________<br> Racket Users list:<br> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br> <br></div></blockquote></div><br></div> </blockquote></div><br></div> </div></div></blockquote></div><br></div>