JavaScript Hardy-Ramanujan-Rademacher
This depends on a BigNumber implementation which supports the following functions: plus
, minus
, times
, div
, sqrt
, isZero
, lt
, gt
, round
). It also uses config
to control the precision used in divisions and to set the rounding mode.
var partition = function(n) {
// Hardy-Ramanujan estimate to set the precision with appropriate margin
BigNumber.config((5 + 1.115 * Math.sqrt(n) + Math.log(n) / Math.log(100))|0, 6);
// Hardy-Ramanujan-Rademacher
var zero = new BigNumber(0),
one = new BigNumber(1),
// \sum_{i=0}^\infty 2^{i+1} i!^2 / {2i+1}!
PI = function(){ var t = new BigNumber(2), s=t, i=1; while (!t.isZero()) s = s.plus(t = t.times(i).div((i+ ++i))); return s }(),
A = new BigNumber(n).minus(one.div(24)),
B = A.times(2).div(3).sqrt().times(PI),
ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
gcd = function(x, y) { return y ? gcd(y, x % y) : x },
genexp = function(x, a, b, c, d) {
// \sum_{i=0}^\infty ax^{4i}/(4i)! + bx^{4i+1}/(4i+1)! + cx^{4i+2}/(4i+2)! + dx^{4i+3}/(4i+3)!
var res = zero, z = one, i;
for (i=0; !z.isZero(); i+=4) {
res = res.plus(z.times(a)); z = z.times(x).div(i+1);
res = res.plus(z.times(b)); z = z.times(x).div(i+2);
res = res.plus(z.times(c)); z = z.times(x).div(i+3);
res = res.plus(z.times(d)); z = z.times(x).div(i+4);
}
return res;
},
p = zero, q = 0, C, L, Psi_, h, k, s, max_L = zero;
for (;;) {
// Adaptive precision calculation for performance
if (++q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);
L = zero;
for (h = 0; h < q; h++) {
if (gcd(h,q) > 1) continue;
for (k=s=0; k < q; k++) s+= (2*(h*k %q) - q) * k - 4*h*n;
// NB The %(4*q*q) is critical for performance
L = L.plus(genexp(new BigNumber(s % (4*q*q)).div(2*q*q).times(PI),1,0,-1,0));
}
if (L.gt(max_L)) max_L = L;
C = B.div(q);
Psi_ = genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt());
p = p.plus(L.times(Psi_));
if (Psi_.times(max_L).abs().lt(ABsqrt12)) break;
}
return p.div(ABsqrt12).round();
};
It computes partition(10000)
in about 0.67 seconds using Node on a 3.5GHz PC.