[racket] q about code for partitions
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