AMC Registration in 23 days
Mon December 15, 2008

Suffolk County Math Tournament in 48 days
Fri January 9, 2009

PUMaC in 70 days
Sat January 31, 2009

AMC 12A in 80 days
Tue February 10, 2009

HMMT in 91 days
Sat February 21, 2009

World Math Day in 102 days
Wed March 4, 2009

AIME I in 128 days
Mon March 30, 2009

PLUS! magazine deadline in 129 days
Tue March 31, 2009

USAMO in 157 days
Tue April 28, 2009

ARML in 188 days
Fri May 29, 2009

21st Birthday in 659 days
Sun September 12, 2010

Turning 40 in 7599 days
Wed September 12, 2029

tags in Topics

more tags

Feeds

Navigation

Links

If you liked this post, buy me a beer... I mean cookie.

Even more pi

Posted January 24th, 2007 by Mgccl

NOTE: BELIEVE IT! A EVEN FASTER Pi CALCULATOR THAN THIS ONE IS HERE!

After last release, I found Gauss-Legendre algorithm, in theory, the higher precision pi is, the faster this algorithm will be, because each time it loop though, it will create 2 times more correct digit. Compare to the old one, the new one can beat it's speed at around 500 digits. It generates 2000 digit in 8 seconds. If I can find anything faster(which is quite possible), it should be Borwein's algorithm that have Nonic convergence. I will try to implement it into PHP soon.
So this is the result of comparing the new Gauss-Legendre pi calculator and the old one:
Pi algorithms

function bcpi($precision){
	$limit = ceil(log($precision)/log(2))-1;
	bcscale($precision+6);
	$a = 1;
	$b = bcdiv(1,bcsqrt(2));
	$t = 1/4;
	$p = 1;
	while($n < $limit){
		$x = bcdiv(bcadd($a,$b),2);
		$y = bcsqrt(bcmul($a, $b));
		$t = bcsub($t, bcmul($p,bcpow(bcsub($a,$x),2)));
		$a = $x;
		$b = $y;
		$p = bcmul(2,$p);
		++$n;
	}
	return bcdiv(bcpow(bcadd($a, $b),2),bcmul(4,$t),$precision);
}

NOTE: BELIEVE IT! A EVEN FASTER Pi CALCULATOR THAN THIS ONE IS HERE!

Bookmark/Search this post with:

[...] Even more pi [...]

On Jan/25/2007 17:04:39 WebDevLogs - Place where Web Developing Abstracts + Concluti (not verified) says:

[...] Even more pi [...]

On Jan/25/2007 17:05:23 WebDevLogs - Place where Web Developing Abstracts + Concluti (not verified) says:

[...] Even more pi [...]

[...] think use PHP to

On Feb/02/2007 04:43:08 WebDevLogs - Place where Web Developing Abstracts + Concluti (not verified) says:

[...] think use PHP to calculate the 2000 places after pi in 8 seconds is fast? you haven't see anything yet. This is the 3rd last attempt of finding pi (at least till [...]

Borwein's Nonic Convergence

On Mar/25/2008 21:27:13 Anonymous (not verified) says:

I followed your other examples to make a bcpi function using Borwein's Nonic Convergence. The problem I ran into was it needs many many more decimal places for the calculations. I separated the iterations from the precision for testing purposes. I set the precision to 500. After 4 iterations I could not get any better than 104 decimals. I set the precision to precision*2, then *3, etc. Even at precision*4 I could only get 212 decimals out of it. For CPU comparison:
Gauss-Legendre algorithm 1.278711 seconds.
Borwein's Quartic convergence 0.582384 seconds.
Borwein's Nonic convergence (4 iterations) 26.619726 seconds. (212 correct)

With all of that said, I used bcgetscale, bcroot (0.2) and this code:

function bcpi4($precision) {
//      bcscale($precision+6);
        bcscale($precision*4);
        $a = bcdiv(1,3);
        $r = bcdiv(bcsub(bcsqrt(3),1),2);
        $s = bcroot(bcsub(1,bcpow($r,3)),3);
//      $count = ceil(log($precision+6)/log(2))-1;
        $count = 4;
        $i = 0;
        while($i < $count){
                $t = bcadd(1,bcmul(2,$r));
                $u = bcroot(bcmul(bcmul(9,$r),bcadd(1,bcadd($r,bcpow($r,2)))),3);
                $v = bcadd(bcpow($t,2),bcadd(bcmul($t,$u),bcpow($u,2)));
                $w = bcdiv(bcmul(27,bcadd(1,bcadd($s,bcpow($s,2)))),$v);
                if ($i == 0) {
                        $a = bcadd(bcmul($w,$a),bcmul($a,bcsub(1,$w)));
                } else {
                        $a = bcadd(bcmul($w,$a),bcmul(bcpow(3,2*$i-1),bcsub(1,$w)));
                }
                $s = bcdiv(bcpow(bcsub(1,$r),3),bcmul(bcadd($t,bcmul(2,$u)),$v));
                $r = bcroot(bcsub(1,bcpow($s,3)),3);
                ++$i;
        }
        return bcdiv(1,$a,$precision);
}

When you get to it, I hope you do a much better job with this than I did.

after some thought about

On Mar/26/2008 15:33:34 Mgccl says:

after some thought about it... I think the Nonic Convergence can't be that fast.
even though each iteration more digits are produced, each iteration costs a lot of time, especially finding the root of an number with my bcroot function is extremely slow.