3 added 103 characters in body
source | link

This depends on a BigNumber implementation which supports the following functions: plus, but doesn't demand much of itminus, 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, /* ROUND_EVEN */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(new BigNumber(1)one.div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        sum = function(min, max, fn) { return min > max ? zero : fn(min).plus(sum(min + 1, max, fn)) },
        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 = new BigNumber(0)zero, z = new BigNumber(1)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;
        },
        Psi_p = function(zero, q) {= var0, C, L, Psi_, h, k, s, max_L = B.divzero;
    for (q;;); return{
 genexp       // Adaptive precision calculation for performance
        if (C,C,-1,C,-++q > 1) BigNumber.timesconfig(new(5 BigNumber+ 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.sqrtlog(100)) },|0);

        //L NB= Thezero;
 .mod(4*q*q) is critical     for performance(h = 0; h < q; h++) {
        s_ = function  if (gcd(h, q) {> return1) sum(0,continue;
 q-1, function          for (k=s=0; k) {< returnq; newk++) BigNumber(s+= (2*(h*k %q) - q) * k - 4*h*n)4*h*n;
 }).mod(4*q*q) },
        L = function// NB The %(q4*q*q) {is returncritical sum(0,for q-1,performance
 function(h) { return gcd(h,q)>1 ? zero :     L = L.plus(genexp(s_new BigNumber(h,qs % (4*q*q)).div(2*q*q).times(PI),1,0,-1,0) });
        };
    return sum(1, Math.max(5, Math if (L.sqrtgt(nmax_L)/4+2), function(q) {
max_L = L;

      // Adaptive precision calculationC for= performanceB.div(q);
        if (qPsi_ >= genexp(C,C,-1,C,-1).times(new BigNumber.config(q).sqrt(5));
 + 1.115 * Math.sqrt(n) / q + Math.log(n)p /= Mathp.logplus(100)L.times(Psi_)|0);
        returnif L(q)Psi_.times(Psi_max_L).abs(q).lt(ABsqrt12)) break;
    })
    return p.div(ABsqrt12).round();
};

It computes partition(10000) in about 0.7167 seconds using Node on a 3.5GHz PC.

This depends on a BigNumber implementation, but doesn't demand much of it.

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, /* ROUND_EVEN */6);

    // Hardy-Ramanujan-Rademacher
    var zero = new BigNumber(0),
        // \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(new BigNumber(1).div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        sum = function(min, max, fn) { return min > max ? zero : fn(min).plus(sum(min + 1, max, fn)) },
        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 = new BigNumber(0), z = new BigNumber(1), 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;
        },
        Psi_ = function(q) { var C = B.div(q); return genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt()) },
        // NB The .mod(4*q*q) is critical for performance
        s_ = function(h, q) { return sum(0, q-1, function(k) { return new BigNumber((2*(h*k %q) - q) * k - 4*h*n) }).mod(4*q*q) },
        L = function(q) { return sum(0, q-1, function(h) { return gcd(h,q)>1 ? zero : genexp(s_(h,q).div(2*q*q).times(PI),1,0,-1,0) }) };
    return sum(1, Math.max(5, Math.sqrt(n)/4+2), function(q) {
        // Adaptive precision calculation for performance
        if (q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);
        return L(q).times(Psi_(q))
    }).div(ABsqrt12).round();
};

It computes partition(10000) in about 0.71 seconds using Node on a 3.5GHz PC.

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.

2 added 1 characters in body
source | link
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, /* ROUND_EVEN */6);

    // Hardy-Ramanujan-Rademacher
    var zero = new BigNumber(0),
        // \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(new BigNumber(1).div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        sum = function(min, max, fn) { return min > max ? zero : fn(min).plus(sum(min + 1, max, fn)) },
        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 = new BigNumber(0), z = new BigNumber(1), 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;
        },
        Psi_ = function(q) { var C = B.div(q); return genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt()) },
        // NB The .mod(4*q*q) is critical for performance
        s_ = function(h, q) { return sum(0, q-1, function(k) { return new BigNumber((2*(h*k %q) - q) * k - 4*h*n) }).mod(4*q*q) },
        L = function(q) { return sum(0, q-1, function(h) { return gcd(h,q)>1 ? zero : genexp(s_(h,q).div(2*q*q).times(PI),1,0,-1,0) }) };
    return sum(1, Math.max(5, Math.sqrt(n)/4+2), function(q) {
        // Adaptive precision calculation for performance
        if (q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);
        return L(q).times(Psi_(q))
    }).div(ABsqrt12).round();
};
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, /* ROUND_EVEN */6);

    // Hardy-Ramanujan-Rademacher
    var zero = new BigNumber(0),
        // \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(new BigNumber(1).div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        sum = function(min, max, fn) { return min > max ? zero : fn(min).plus(sum(min + 1, max, fn)) },
        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 = new BigNumber(0), z = new BigNumber(1), 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;
        }
        Psi_ = function(q) { var C = B.div(q); return genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt()) },
        // NB The .mod(4*q*q) is critical for performance
        s_ = function(h, q) { return sum(0, q-1, function(k) { return new BigNumber((2*(h*k %q) - q) * k - 4*h*n) }).mod(4*q*q) },
        L = function(q) { return sum(0, q-1, function(h) { return gcd(h,q)>1 ? zero : genexp(s_(h,q).div(2*q*q).times(PI),1,0,-1,0) }) };
    return sum(1, Math.max(5, Math.sqrt(n)/4+2), function(q) {
        // Adaptive precision calculation for performance
        if (q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);
        return L(q).times(Psi_(q))
    }).div(ABsqrt12).round();
};
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, /* ROUND_EVEN */6);

    // Hardy-Ramanujan-Rademacher
    var zero = new BigNumber(0),
        // \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(new BigNumber(1).div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        sum = function(min, max, fn) { return min > max ? zero : fn(min).plus(sum(min + 1, max, fn)) },
        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 = new BigNumber(0), z = new BigNumber(1), 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;
        },
        Psi_ = function(q) { var C = B.div(q); return genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt()) },
        // NB The .mod(4*q*q) is critical for performance
        s_ = function(h, q) { return sum(0, q-1, function(k) { return new BigNumber((2*(h*k %q) - q) * k - 4*h*n) }).mod(4*q*q) },
        L = function(q) { return sum(0, q-1, function(h) { return gcd(h,q)>1 ? zero : genexp(s_(h,q).div(2*q*q).times(PI),1,0,-1,0) }) };
    return sum(1, Math.max(5, Math.sqrt(n)/4+2), function(q) {
        // Adaptive precision calculation for performance
        if (q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);
        return L(q).times(Psi_(q))
    }).div(ABsqrt12).round();
};
1
source | link

JavaScript Hardy-Ramanujan-Rademacher

This depends on a BigNumber implementation, but doesn't demand much of it.

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, /* ROUND_EVEN */6);

    // Hardy-Ramanujan-Rademacher
    var zero = new BigNumber(0),
        // \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(new BigNumber(1).div(24)),
        B = A.times(2).div(3).sqrt().times(PI),
        ABsqrt12 = A.times(B).times(new BigNumber(12).sqrt()),
        sum = function(min, max, fn) { return min > max ? zero : fn(min).plus(sum(min + 1, max, fn)) },
        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 = new BigNumber(0), z = new BigNumber(1), 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;
        }
        Psi_ = function(q) { var C = B.div(q); return genexp(C,C,-1,C,-1).times(new BigNumber(q).sqrt()) },
        // NB The .mod(4*q*q) is critical for performance
        s_ = function(h, q) { return sum(0, q-1, function(k) { return new BigNumber((2*(h*k %q) - q) * k - 4*h*n) }).mod(4*q*q) },
        L = function(q) { return sum(0, q-1, function(h) { return gcd(h,q)>1 ? zero : genexp(s_(h,q).div(2*q*q).times(PI),1,0,-1,0) }) };
    return sum(1, Math.max(5, Math.sqrt(n)/4+2), function(q) {
        // Adaptive precision calculation for performance
        if (q > 1) BigNumber.config((5 + 1.115 * Math.sqrt(n) / q + Math.log(n) / Math.log(100))|0);
        return L(q).times(Psi_(q))
    }).div(ABsqrt12).round();
};

It computes partition(10000) in about 0.71 seconds using Node on a 3.5GHz PC.