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

Or, more lispy:

;; from included; to excluded.
(define (mult from to)
  (case (- to from)
    ((0) 1)
    ((1) from)
    ((2) (* from (+ from 1)))
    ((3) (* from (+ from 1) (+ from 2)))
    ;; ...
    (else
     (let ((middle (quotient (+ from to) 2)))
       (* (mult from middle) (mult middle to))))))

(define (fact n)
  (if (zero? n)
    1
    (mult 2 (add1 n))))



On Tue, Apr 9, 2013 at 1:43 PM, Pierpaolo Bernardi <olopierpa at gmail.com>wrote:

> 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/09aa75c6/attachment-0001.html>