<div dir="ltr"><div style>Or, more lispy:</div><div style><br></div><div>;; from included; to excluded.</div><div>(define (mult from to)</div><div>  (case (- to from)</div><div>    ((0) 1)</div><div>    ((1) from)</div><div>
    ((2) (* from (+ from 1)))</div><div>    ((3) (* from (+ from 1) (+ from 2)))</div><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>    (mult 2 (add1 n))))</div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Tue, Apr 9, 2013 at 1:43 PM, Pierpaolo Bernardi <span dir="ltr">&lt;<a href="mailto:olopierpa@gmail.com" target="_blank">olopierpa@gmail.com</a>&gt;</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 class="h5">
On Tue, Apr 9, 2013 at 12:05 PM, Laurent <span dir="ltr">&lt;<a href="mailto:laurent.orseau@gmail.com" target="_blank">laurent.orseau@gmail.com</a>&gt;</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 class="h5"><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">&lt;<a href="mailto:lucier@math.purdue.edu" target="_blank">lucier@math.purdue.edu</a>&gt;</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 &#39;())<br>
             (n (- n 1)))<br>
   (if (&lt;= 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 (&lt; (- 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&#39;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 class="im">____________________<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>