PasteRack.org Paste # 16085 2014-06-28 06:00:11 Fork as a new paste. Paste viewed 774 times. Tweet Embed:
#lang typed/racket/base (provide partitions reset-partitions-cache) (require math/private/vector/vector          math/private/number-theory/types)  ;;; Partitions are computed using Euler's algorithm:  ;                k            k(3k+1)              k(3k-1) ; p(n) = sum (-1)   [ p( n - --------- ) + p( n - --------- ) ] ;        k>=1                    2                    2  ; http://en.wikipedia.org/wiki/Partition_(number_theory)  (define cache-size 1) (: cache (Vectorof Integer)) (define cache (make-vector cache-size 0)) (vector-set! cache 0 1)  (: reset-partitions-cache : -> Void) (define (reset-partitions-cache)   (set! cache-size 1)   (make-vector cache-size 0)   (set! cache (make-vector cache-size 0))   (vector-set! cache 0 1))  (: grow-cache : Natural -> Void) (define (grow-cache n)   (cond [(> cache-size n) (void)]         [else (define n+1 (+ n 1))               (define new-cache (make-vector n+1 0))               (vector-copy! new-cache 0 cache)               (set! cache-size n+1)               (set! cache new-cache)]))  (: ref! (Integer (-> Integer) -> Integer)) (define (ref! n thnk)   (vector-ref! cache n thnk exact-zero?))  (: partitions : Integer -> Integer) (define (partitions n)   (cond [(< n 0) 0]         [else              (grow-cache n)          (: p : Integer -> Integer)          (define (p n)            (ref! n (λ ()                      (: loop1 : Integer Integer Integer -> Integer)                      (define (loop1 k m s)                        (cond [(< m 0) s]                              [else (loop1 (+ k 1) (- m (+ (* 3 k) 1))                                            (if (odd? k) (+ s (p m)) (- s (p m))))]))                      (: loop2 : Integer Integer Integer -> Integer)                      (define (loop2 k m s)                        (cond [(< m 0) s]                              [else   (loop2 (- k 1)                                              (+ m (* 3 k) -2)                                              (if (odd? k) (+ s (p m)) (- s (p m))))]))                      (+ (loop1  1 (- n 1) 0)                         (loop2 -1 (- n 2) 0)))))          (p n)]))

=>

/home/stchang/racket/pasterack/tmp/16085/16085code.scrbl:5:27: module: identifier already imported for label from: (all-except typed/racket #%mo...   at: cast   in: math/private/number-theory/types   context...:    standard-module-name-resolver    /home/stchang/plt601/pkgs/scribble-pkgs/scribble-lib/scribble/run.rkt:133:24    /home/stchang/plt601/pkgs/scribble-pkgs/scribble-lib/scribble/run.rkt: [running body]

#### partitions2.rkt

```#lang typed/racket/base
(provide partitions reset-partitions-cache)
(require math/private/vector/vector
math/private/number-theory/types)

;;; Partitions are computed using Euler's algorithm:

;                k            k(3k+1)              k(3k-1)
; p(n) = sum (-1)   [ p( n - --------- ) + p( n - --------- ) ]
;        k>=1                    2                    2

; http://en.wikipedia.org/wiki/Partition_(number_theory)

(define cache-size 1)
(: cache (Vectorof Integer))
(define cache (make-vector cache-size 0))
(vector-set! cache 0 1)

(: reset-partitions-cache : -> Void)
(define (reset-partitions-cache)
(set! cache-size 1)
(make-vector cache-size 0)
(set! cache (make-vector cache-size 0))
(vector-set! cache 0 1))

(: grow-cache : Natural -> Void)
(define (grow-cache n)
(cond [(> cache-size n) (void)]
[else (define n+1 (+ n 1))
(define new-cache (make-vector n+1 0))
(vector-copy! new-cache 0 cache)
(set! cache-size n+1)
(set! cache new-cache)]))

(: ref! (Integer (-> Integer) -> Integer))
(define (ref! n thnk)
(vector-ref! cache n thnk exact-zero?))

(: partitions : Integer -> Integer)
(define (partitions n)
(cond [(< n 0) 0]
[else
(grow-cache n)
(: p : Integer -> Integer)
(define (p n)
(ref! n (λ ()
(: loop1 : Integer Integer Integer -> Integer)
(define (loop1 k m s)
(cond [(< m 0) s]
[else (loop1 (+ k 1) (- m (+ (* 3 k) 1))
(if (odd? k) (+ s (p m)) (- s (p m))))]))
(: loop2 : Integer Integer Integer -> Integer)
(define (loop2 k m s)
(cond [(< m 0) s]
[else   (loop2 (- k 1)
(+ m (* 3 k) -2)
(if (odd? k) (+ s (p m)) (- s (p m))))]))
(+ (loop1  1 (- n 1) 0)
(loop2 -1 (- n 2) 0)))))
(p n)]))
```

=>

```/home/stchang/racket/pasterack/tmp/16085/16085code.scrbl:5:27: module: identifier already imported for label from: (all-except typed/racket #%mo...
at: cast
in: math/private/number-theory/types
context...:
standard-module-name-resolver
/home/stchang/plt601/pkgs/scribble-pkgs/scribble-lib/scribble/run.rkt:133:24
/home/stchang/plt601/pkgs/scribble-pkgs/scribble-lib/scribble/run.rkt: [running body]
```