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

 From: Pierpaolo Bernardi (olopierpa at gmail.com) Date: Tue Apr 9 07:43:42 EDT 2013 Previous message: [racket] Math - factorial.rkt, binomial.rkt and memoization Next message: [racket] Math - factorial.rkt, binomial.rkt and memoization Messages sorted by: [date] [thread] [subject] [author]

```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>
```

 Posted on the users mailing list. Previous message: [racket] Math - factorial.rkt, binomial.rkt and memoization Next message: [racket] Math - factorial.rkt, binomial.rkt and memoization Messages sorted by: [date] [thread] [subject] [author]