Skip Menu |
 

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

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

People
Owner: Nobody in particular
Requestors: emazep [...] gmail.com
Cc:
AdminCc:

Bug Information
Severity: Normal
Broken in: 1.89
Fixed in: 1.999701



Subject: Huge slowdown in blog(x) when x begins with 1
It seems that there is a huge slowdown in blog(x) whenever x is a number beginning with 1. Consider the following script: --- use strict; use warnings; use Benchmark qw(cmpthese); use Math::BigFloat; # $x is a big number beginning with 1 our $x = Math::BigFloat->new( '1234567890' x 20 ); # $x2 = $x * 2 ($x2 begins with 2) our $x2 = $x->copy->bmul(2); cmpthese( -10, { log_2x => sub { $x2->copy->blog }, log_x => sub { $x->copy->blog } }); --- It prints out: Rate log_x log_2x log_x 1.14/s -- -95% log_2x 24.4/s 2038% -- which shows that (in this case) calculating blog(x) takes more than *20 times* longer than calculating blog(2*x) (this ratio tends to diverge when the size of x increases). Whatever the reason, this can easily be avoided at least by naively implementing blog(x) by blog(2*x)-blog(2) when x is a number beginning with 1 (multiplying by 2 a number beginning with 1 always gives a number beginning with a digit != 1). Thank you for your great work, Emanuele Zeppieri
Subject: perl-V.txt
Download perl-V.txt
text/plain 2.6k
Summary of my perl5 (revision 5 version 10 subversion 0 patch 34065) configuration: Platform: osname=cygwin, osvers=1.5.25(0.15642), archname=cygwin-thread-multi-64int uname='cygwin_nt-5.1 reini 1.5.25(0.15642) 2008-06-12 19:34 i686 cygwin ' config_args='-de -Dmksymlinks -Dusethreads -Dmad=y -Dusedevel' hint=recommended, useposix=true, d_sigaction=define useithreads=define, usemultiplicity=define useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef use64bitint=define, use64bitall=undef, uselongdouble=undef usemymalloc=y, bincompat5005=undef Compiler: cc='gcc', ccflags ='-DPERL_USE_SAFE_PUTENV -U__STRICT_ANSI__ -fno-strict-aliasing -pipe -I/usr/local/include', optimize='-O3', cppflags='-DPERL_USE_SAFE_PUTENV -U__STRICT_ANSI__ -fno-strict-aliasing -pipe -I/usr/local/include' ccversion='', gccversion='3.4.4 (cygming special, gdc 0.12, using dmd 0.125)', gccosandvers='' intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=12345678 d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12 ivtype='long long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8 alignbytes=8, prototype=define Linker and Libraries: ld='g++', ldflags =' -Wl,--enable-auto-import -Wl,--export-all-symbols -Wl,--stack,8388608 -Wl,--enable-auto-image-base -L/usr/local/lib' libpth=/usr/local/lib /usr/lib /lib libs=-lgdbm -ldb -ldl -lcrypt -lgdbm_compat perllibs=-ldl -lcrypt libc=/usr/lib/libc.a, so=dll, useshrplib=true, libperl=libperl.a gnulibc_version='' Dynamic Linking: dlsrc=dl_dlopen.xs, dlext=dll, d_dlsymun=undef, ccdlflags=' ' cccdlflags=' ', lddlflags=' --shared -Wl,--enable-auto-import -Wl,--export-all-symbols -Wl,--stack,8388608 -Wl,--enable-auto-image-base -L/usr/local/lib' Characteristics of this binary (from libperl): Compile-time options: MULTIPLICITY MYMALLOC PERL_DONT_CREATE_GVSV PERL_IMPLICIT_CONTEXT PERL_MAD PERL_MALLOC_WRAP PERL_USE_SAFE_PUTENV USE_64_BIT_INT USE_ITHREADS USE_LARGE_FILES USE_PERLIO USE_REENTRANT_API Locally applied patches: MAINT34065 CYG11 no-bs CYG12 no archlib in otherlibdirs CYG14 Dynaloader CYG15 static-Win32CORE Bug#55162 File::Spec::case_tolerant performance Built under cygwin Compiled at Jun 30 2008 16:05:15 %ENV: CYGWIN="" @INC: /usr/lib/perl5/5.10/i686-cygwin /usr/lib/perl5/5.10 /usr/lib/perl5/site_perl/5.10/i686-cygwin /usr/lib/perl5/site_perl/5.10 /usr/lib/perl5/vendor_perl/5.10/i686-cygwin /usr/lib/perl5/vendor_perl/5.10 /usr/lib/perl5/vendor_perl/5.10 /usr/lib/perl5/site_perl/5.8 /usr/lib/perl5/vendor_perl/5.8 .
Subject: Re: [rt.cpan.org #43924] Huge slowdown in blog(x) when x begins with 1
Date: Sat, 7 Mar 2009 14:52:43 +0100
To: bug-Math-BigInt [...] rt.cpan.org
From: Tels <nospam-abuse [...] bloodgate.com>
On Saturday 07 March 2009 12:08:03 Emanuele Zeppieri via RT wrote: Show quoted text
> Sat Mar 07 06:08:02 2009: Request 43924 was acted upon. > Transaction: Ticket created by emazep > Queue: Math-BigInt > Subject: Huge slowdown in blog(x) when x begins with 1 > Broken in: 1.89 > Severity: Normal > Owner: Nobody > Requestors: emazep@gmail.com > Status: new > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=43924 > > > > It seems that there is a huge slowdown in blog(x) whenever x is a > number beginning with 1. > > Consider the following script: > > --- > > use strict; > use warnings; > > use Benchmark qw(cmpthese); > use Math::BigFloat; > > # $x is a big number beginning with 1 > our $x = Math::BigFloat->new( '1234567890' x 20 ); > # $x2 = $x * 2 ($x2 begins with 2) > our $x2 = $x->copy->bmul(2); > > cmpthese( -10, { > log_2x => sub { $x2->copy->blog }, > log_x => sub { $x->copy->blog } > }); > > --- > > It prints out: > > Rate log_x log_2x > log_x 1.14/s -- -95% > log_2x 24.4/s 2038% -- > > which shows that (in this case) calculating blog(x) takes more than > *20 times* longer than calculating blog(2*x) (this ratio tends to > diverge when the size of x increases). > > Whatever the reason, this can easily be avoided at least by naively > implementing blog(x) by blog(2*x)-blog(2) when x is a number > beginning with 1 (multiplying by 2 a number beginning with 1 always > gives a number beginning with a digit != 1).
I haven't looked (and I currently have almost zero time for Perl, sorry :( but it might be a simple case of the code accidentily using BigIntegers internally when the number begins with 1, by not converting some small number to a scalar or so. Thank you for your report! Tels -- Signed on Sat Mar 7 14:51:51 2009 with key 0x93B84C15. Get one of my photo posters: http://bloodgate.com/posters PGP key on http://bloodgate.com/tels.asc or per email. "Now, admittedly, it's critical software. This is the 'let's go kill people' software." -- Mark A. Welsh III
Download signature.asc
application/pgp-signature 481b

Message body not shown because it is not plain text.

Download (untitled) / with headers
text/plain 392b
Confirmed that this is still an issue: use strict; use warnings; use Benchmark qw(cmpthese); use Math::BigFloat; our $x = Math::BigFloat->new( '1234567890' x 20 ); our $x2 = Math::BigFloat->new( '2234567890' x 20 ); cmpthese( -10, { log_2x => sub { $x2->copy->blog }, log_x => sub { $x->copy->blog } }); Rate log_x log_2x log_x 1.18/s -- -98% log_2x 47.2/s 3914% --
Download (untitled) / with headers
text/plain 934b
This happens because _log_10 first moves the decimal place over (so XYYYYYY.ZZZ becomes X.YYYYYYZZZ) then we do a comparison of X >= 2 right before the "if $twos != 0" loop. If X >= 2, we divide by two *and round to $scale+4*. So in the case of '2234567890' x 20, we have divided by two with rounding, so we send to _log: '1.11728394511172839451117283945111728394511172839' In the case of '1234567890' x 20, we send: '1.234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' The former is much faster. Adding the line: $x->bround($scale+4) on line ~1480 of BigFloat.pm, right after the while statements and before the 'if ($twos != 0)' will speed up the first case in the benchmark by about 20x. With that change, the test suite passes. I'm not sure if it is the *right* fix.
Subject: Re: [rt.cpan.org #43924] Huge slowdown in blog(x) when x begins with 1
Date: Wed, 23 Oct 2013 13:56:02 -0400
To: bug-Math-BigInt [...] rt.cpan.org
From: "Tels" <nospam-abuse [...] bloodgate.com>
Download (untitled) / with headers
text/plain 1.6k
On Tue, October 22, 2013 3:19 pm, Dana Jacobsen via RT wrote: Show quoted text
> Queue: Math-BigInt > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=43924 > > > This happens because _log_10 first moves the decimal place over (so > XYYYYYY.ZZZ becomes X.YYYYYYZZZ) then we do a comparison of X >= 2 right > before the "if $twos != 0" loop. If X >= 2, we divide by two *and round > to $scale+4*. > > So in the case of '2234567890' x 20, we have divided by two with rounding, > so we send to _log: > '1.11728394511172839451117283945111728394511172839' > > In the case of '1234567890' x 20, we send: > '1.234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' > > The former is much faster. Adding the line: > > $x->bround($scale+4) > > on line ~1480 of BigFloat.pm, right after the while statements and before > the 'if ($twos != 0)' will speed up the first case in the benchmark by > about 20x. > > With that change, the test suite passes. I'm not sure if it is the > *right* fix.
IIRC the routine is asked to return a precision of scale, so it keeps internally $scale + 4 (to have enough digits to avoid rounding). So rounding the input in both cases is the "right" thing todo, e.g. at least it will have the same possible output inaccuraries in both cases. Not rounding in one path was probably an oversight on my part, and the testsuite wouldn't catch it if the final result is rounded to $scale before output, unless the intermidiate rounding produces errors due to accumulating them. Hope this helps, tels -- http://bloodgate.com/galleries/
Subject: Re: [rt.cpan.org #43924] Huge slowdown in blog(x) when x begins with 1
Date: Wed, 04 Jun 2014 10:23:19 +0200
To: bug-Math-BigInt [...] rt.cpan.org
From: Emanuele Zeppieri <emazep [...] gmail.com>
Download (untitled) / with headers
text/plain 1.1k
To the maintainer: can we apply this fix please? Thanks! -Emanuele On 2013-10-22 21:19, Dana Jacobsen via RT wrote: Show quoted text
> <URL: https://rt.cpan.org/Ticket/Display.html?id=43924 > > > This happens because _log_10 first moves the decimal place over (so XYYYYYY.ZZZ becomes X.YYYYYYZZZ) then we do a comparison of X >= 2 right before the "if $twos != 0" loop. If X >= 2, we divide by two *and round to $scale+4*. > > So in the case of '2234567890' x 20, we have divided by two with rounding, so we send to _log: > '1.11728394511172839451117283945111728394511172839' > > In the case of '1234567890' x 20, we send: > '1.234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' > > The former is much faster. Adding the line: > > $x->bround($scale+4) > > on line ~1480 of BigFloat.pm, right after the while statements and before the 'if ($twos != 0)' will speed up the first case in the benchmark by about 20x. > > With that change, the test suite passes. I'm not sure if it is the *right* fix. >
Fixed in Math-BigInt-1.999701.


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.