[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/JmAAtn4T    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Apr 5:
(define partition
  (let ((len 1) (pv (vector 1)))
    (define (grow)
      (let* ((new-len (+ len len))
             (new-pv (make-vector new-len #f)))
        (do ((i 0 (+ i 1))) ((= i len))
          (vector-set! new-pv i
            (vector-ref pv i)))
        (set! len new-len)
        (set! pv new-pv)))
    (lambda (n)
      (do () ((< n len)) (grow))
      (cond ((negative? n) 0)
            ((zero? n) 1)
            ((and (< n len) (vector-ref pv n))
              => (lambda (x) x))
            (else (let loop ((k 1) (sum 0))
                    (if (< n k)
                        (begin (vector-set! pv n sum) sum)
                        (loop (+ k 1)
                              (+ sum (* (expt -1 (+ k 1))
                                        (+ (partition (- n (* k (- (* 3 k) 1) 1/2)))
                                           (partition (- n (* k (+ (* 3 k) 1) 1/2))))))))))))))

(time (display (partition 1000)) (newline))


Output:
1
2
24061467864032622473692149727991
cpu time: 440 real time: 2214 gc time: 40


Create a new paste based on this one


Comments: