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

But if you write all 10 cases, aren't the lists constructed anyway before
calling `*'?



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

> 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/7087b68e/attachment.html>