[racket] q about code for partitions

From: Jos Koot (jos.koot at gmail.com)
Date: Wed Jun 4 14:36:05 EDT 2014

Hi

In share/pkgs/math-lib/math/private/number-theory I find the following two
pieces of code:

line 34: (define m (/ (+ 1.0 (flsqrt (+ 1.0 (* 24.0 n)))) 6.0))
line 39: (exact-floor m)

Obviously for finding the positive root of the equation n-k(3k-1)/2=0 for k
in terms of n.
(from wikipedia: http://en.wikipedia.org/wiki/Partition_(number_theory) )

How can we be sure that (exact-floor m) never is too small?
Because of the inexact operations, might line 34 not produce a value off by
more than 1 for very large values of n?
No criticism here, just wondering.

Best wishes, Jos

PS I have a function that computes (partitions n) (with about the same speed
I think) and with exact operations only, but its memoizing (necessary for
efficiency) takes much more memory for big n, I think.
Jos

 



Posted on the users mailing list.