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

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

while the for version should be almost all big x big.
>

oops, no.  The for version should be almost all fix x big.

Here's a count considering also the type of the result of the
multiplication:

> (fact 1000000)
#hash(((fix fix -> fix) . 437071)
      ((big big -> big) . 209717)
      ((fix big -> big) . 46338)
      ((fix fix fix -> fix) . 48577)
      ((fix fix -> big) . 209718))

====


(define x*-counter 'not-initialized)

(define (x* . args)
  (define (classify x)
    (if (fixnum? x)
      'fix
      'big))
  (define res (apply * args))
  (hash-update! x*-counter
                (append (map classify args)
                       '(->)
                       (list (classify res)))
                add1
                0)
  (apply * args))

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

(define (fact n)
  (set! x*-counter (make-hash))
  (define f (if (zero? n)
              1
              (mult 2 (add1 n))))
  (values ;f
   x*-counter))
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130409/4b1c59c1/attachment.html>