[racket] Math - factorial.rkt, binomial.rkt and memoization

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.orseau at gmail.com> wrote:

>
> On Mon, Apr 8, 2013 at 9:34 PM, Bradley Lucier <lucier at 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130409/4970521a/attachment.html>