Skip Menu |
 

This queue is for tickets about the Math-BigInt CPAN distribution.

Report information
The Basics
Id: 90033
Status: resolved
Priority: 0/
Queue: Math-BigInt

People
Owner: Nobody in particular
Requestors: DANAJ [...] cpan.org
Cc:
AdminCc:

Bug Information
Severity: Wishlist
Broken in: (no value)
Fixed in: 1.999705

Attachments


Subject: Math::BigFloat->bpi is very slow with many digits
Download (untitled) / with headers
text/plain 1.8k
At one point I decided I wanted a million or so digits of Pi, and tried using Math::BigFloat. It's really slow. While the following patch certainly won't give y-cruncher or similar programs any competition, it does speed up large inputs by a great deal. If we really cared, allowing a _bpi method to the backend would allow C implementations (Pari would just get Pari's Pi constant). I tried Wetherfield's newer arctan formula, which speeds things up about 10%. Not really worth upgrading. I briefly looked at spigot formulas, but in pure Perl they were a lot slower than the existing arctan solution for me. I tried the Chudnovsky's formula, which is just a little faster than the included patch using the Calc backend, but was substantially slower with the Pari or GMP backends. Someone may have a more efficient implementation. I tried Arndt's quartic method, which runs about half the speed of the AGM method with my implementation. It's possible one of the Borwein-type formulas may be faster. Timing for the included AGM method. We see a much better looking growth rate. digits Time-orig (s) Time-AGM (s) 1000 0.007 0.008 10000 0.52 0.13 50000 26.0 1.7 100000 130.9 4.7 200000 631.8 12.6 400000 31.7 800000 89.1 I've used a large string from y-cruncher and compared the output at various digits to the rounded string. The only issues I found up to 2M or so are similar to the ones impacting the current code: no matter how many guard digits we use, eventually we will find a x499999... or x049999... that will go a different direction. Look, for example, at 761, 776, 16686, 820160 digits with different rounding modes. If we really, really cared we could use one of the digit formulas to add more digits as needed for proper rounding.
Subject: bigfloat-bpi-performance.patch
--- perl-5.19.5/lib/Math/BigFloat.pm 2013-08-26 03:14:41.000000000 -0700 +++ perl-5.19.5/lib/5.19.5/Math/BigFloat.pm 2013-11-04 00:27:23.983550954 -0800 @@ -2679,6 +2679,27 @@ my $fallback = defined $n ? 0 : 1; $n = 40 if !defined $n || $n < 1; + # For large accuracy, the arctan formulas become very inefficient with + # Math::BigFloat. Switch to Brent-Salamin (aka AGM or Gauss-Legendre). + if ($n >= 1000) { + $n += 8; + $HALF = $self->new($HALF) unless ref($HALF); + my ($an, $bn, $tn, $pn) = ($self->bone, $HALF->copy->bsqrt($n), + $HALF->copy->bmul($HALF), $self->bone); + while ($pn < $n) { + my $prev_an = $an->copy; + $an->badd($bn)->bmul($HALF, $n); + $bn->bmul($prev_an)->bsqrt($n); + $prev_an->bsub($an); + $tn->bsub($pn * $prev_an * $prev_an); + $pn->badd($pn); + } + $an->badd($bn); + $an->bmul($an,$n)->bdiv(4*$tn, $n-8); + delete $an->{_a} if $fallback == 1; + return $an; + } + # after 黃見利 (Hwang Chien-Lih) (1997) # pi/4 = 183 * atan(1/239) + 32 * atan(1/1023) – 68 * atan(1/5832) # + 12 * atan(1/110443) - 12 * atan(1/4841182) - 100 * atan(1/6826318)
Thanks. Your code is included in the Math-BigInt-1.999705 distro.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

Please report any issues with rt.cpan.org to rt-cpan-admin@bestpractical.com.