Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[PATCH] Math::BigInt->new($n)->bnok($k) incorrect for $k==0 and $k===$n-1 #10601

Closed
p5pRT opened this issue Sep 2, 2010 · 5 comments
Closed

Comments

@p5pRT
Copy link

p5pRT commented Sep 2, 2010

Migrated from rt.perl.org#77640 (status was 'resolved')

Searchable as RT77640$

@p5pRT
Copy link
Author

p5pRT commented Sep 2, 2010

From pfusik@op.pl

This is a bug report for perl from pfusik@​op.pl,
generated with the help of perlbug 1.39 running under perl 5.12.1.


There is a bug in Math​::BigInt's implementation of n over k​:
Math​::BigInt->new($n)->bnok(0) is $n+1, should be 1.
Math​::BigInt->new($n)->bnok($n-1) is 1, should be $n.

Attached is a patch.
I've fixed one test case and added new test cases.
I've corrected misleading comments, including one in Math​::BigInt​::Calc​::_is_odd.



Flags​:
  category=library
  severity=medium
  module=Math​::BigInt


Site configuration information for perl 5.12.1​:

Configured by 1 at Thu Jul 29 16​:39​:48 2010.

Summary of my perl5 (revision 5 version 12 subversion 1) configuration​:
 
  Platform​:
  osname=MSWin32, osvers=5.1, archname=MSWin32-x86-multi-thread
  uname='Win32 strawberryperl 5.12.1.0 #1 Thu Jul 29 10​:08​:11 2010 i386'
  config_args='undef'
  hint=recommended, useposix=true, d_sigaction=undef
  useithreads=define, usemultiplicity=define
  useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef
  use64bitint=undef, use64bitall=undef, uselongdouble=undef
  usemymalloc=n, bincompat5005=undef
  Compiler​:
  cc='gcc', ccflags =' -s -O2 -DWIN32 -DHAVE_DES_FCRYPT -DUSE_SITECUSTOMIZE -DPERL_IMPLICIT_CONTEXT -DPERL_IMPLICIT_SYS -fno-strict-aliasing -mms-bitfields -DPERL_MSVCRT_READFIX',
  optimize='-s -O2',
  cppflags='-DWIN32'
  ccversion='', gccversion='4.4.3', gccosandvers=''
  intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=1234
  d_longlong=undef, longlongsize=8, d_longdbl=define, longdblsize=12
  ivtype='long', ivsize=4, nvtype='double', nvsize=8, Off_t='long long', lseeksize=8
  alignbytes=8, prototype=define
  Linker and Libraries​:
  ld='g++', ldflags ='-s -L"C​:\bin\strawberry\perl\lib\CORE" -L"C​:\bin\strawberry\c\lib"'
  libpth=C​:\bin\strawberry\c\lib C​:\bin\strawberry\c\i686-w64-mingw32\lib
  libs=-lmoldname -lkernel32 -luser32 -lgdi32 -lwinspool -lcomdlg32 -ladvapi32 -lshell32 -lole32 -loleaut32 -lnetapi32 -luuid -lws2_32 -lmpr -lwinmm -lversion -lodbc32 -lodbccp32 -lcomctl32
  perllibs=-lmoldname -lkernel32 -luser32 -lgdi32 -lwinspool -lcomdlg32 -ladvapi32 -lshell32 -lole32 -loleaut32 -lnetapi32 -luuid -lws2_32 -lmpr -lwinmm -lversion -lodbc32 -lodbccp32 -lcomctl32
  libc=, so=dll, useshrplib=true, libperl=libperl512.a
  gnulibc_version=''
  Dynamic Linking​:
  dlsrc=dl_win32.xs, dlext=dll, d_dlsymun=undef, ccdlflags=' '
  cccdlflags=' ', lddlflags='-mdll -s -L"C​:\bin\strawberry\perl\lib\CORE" -L"C​:\bin\strawberry\c\lib"'

Locally applied patches​:
 


@​INC for perl 5.12.1​:
  C​:/bin/strawberry/perl/site/lib
  C​:/bin/strawberry/perl/vendor/lib
  C​:/bin/strawberry/perl/lib
  .


Environment for perl 5.12.1​:
  CYGWIN=nodosfilewarning
  HOME=C​:\Documents and Settings\Administrator
  LANG (unset)
  LANGUAGE (unset)
  LD_LIBRARY_PATH (unset)
  LOGDIR (unset)
  PATH=C​:\Program Files\ImageMagick-6.6.3-Q16;C​:\bin;C​:\bin\strawberry\perl\site\bin;C​:\bin\strawberry\perl\bin;c​:\bin\ruby\bin;C​:\bin\nant\bin;C​:\Program Files\GnuWin32\bin;C​:\bin\ragel\bin;C​:\bin\MinGW\bin;C​:\bin\cygwin\bin;C​:\WINDOWS\system32;C​:\WINDOWS;C​:\WINDOWS\System32\Wbem;C​:\Program Files\Intel\DMIX;C​:\Program Files\Intel\WiFi\bin\;C​:\Program Files\Common Files\Roxio Shared\DLLShared\;C​:\Program Files\Common Files\Roxio Shared\9.0\DLLShared\;C​:\WINDOWS\Microsoft.NET\Framework\v4.0.30319;C​:\Program Files\java\jdk1.6.0_10\bin;C​:\Program Files\Microsoft SQL Server\100\Tools\Binn\;C​:\Program Files\Microsoft SQL Server\100\DTS\Binn\;C​:\Program Files\Microsoft SQL Server\100\Tools\Binn\VSShell\Common7\IDE\;C​:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE\PrivateAssemblies\;C​:\WINDOWS\system32\WindowsPowerShell\v1.0;C​:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE;C​:\Program Files\Microsoft Visual Studio 9.0\VC\bin;C​:\Program Files\Microsoft SDKs\Windows\v6.0A\bin;C​:\bin\oracle\product\10.2.0\db_1\bin;C​:\Program Files\7-Zip;C​:\Program Files\VoiceAge\Common;C​:\bin\MinGW\opt\mingw32ce\bin;C​:\Program Files\TortoiseSVN\bin;C​:\Program Files\Windows Installer XML v3\bin;C​:\bin\flex_sdk\bin;C​:\bin\apache-cxf-2.2.2\bin;C​:\Program Files\MPlayer-1.0rc2;C​:\bin\python\Scripts;C​:\Program Files\Git\bin;C​:\Program Files\RSA Security\RSA SecurID Software Token\;C​:\bin\D\dmd\windows\bin;C​:\bin\D\dmd2\windows\bin;C​:\WINDOWS\system32\WindowsPowerShell\v1.0;C​:\Program Files\FAIL\;C​:\Program Files\TortoiseGit\bin;C​:\bin\strawberry\c\bin
  PERL_BADLANG (unset)
  SHELL (unset)

@p5pRT
Copy link
Author

p5pRT commented Sep 2, 2010

From pfusik@op.pl

Math-BigInt-bnok.patch
diff --git a/cpan/Math-BigInt/lib/Math/BigInt.pm b/cpan/Math-BigInt/lib/Math/BigInt.pm
index f97e438..303f4a0 100644
--- a/cpan/Math-BigInt/lib/Math/BigInt.pm
+++ b/cpan/Math-BigInt/lib/Math/BigInt.pm
@@ -1320,18 +1320,17 @@ sub bnok
     }
   else
     {
-    # ( 7 )    7!          7*6*5 * 4*3*2*1   7 * 6 * 5
-    # ( - ) = --------- =  --------------- = ---------
-    # ( 3 )   3! (7-3)!    3*2*1 * 4*3*2*1   3 * 2 * 1 
+    # ( 7 )       7!       1*2*3*4 * 5*6*7   5 * 6 * 7       6   7
+    # ( - ) = --------- =  --------------- = --------- = 5 * - * -
+    # ( 3 )   (7-3)! 3!    1*2*3*4 * 1*2*3   1 * 2 * 3       2   3
 
-    # compute n - k + 2 (so we start with 5 in the example above)
-    my $z = $x - $y;
-    if (!$z->is_one())
+    if (!$y->is_zero())
       {
+      my $z = $x - $y;
       $z->binc();
       my $r = $z->copy(); $z->binc();
       my $d = $self->new(2);
-      while ($z->bacmp($x) <= 0)		# f < x ?
+      while ($z->bacmp($x) <= 0)		# f <= x ?
         {
         $r->bmul($z); $r->bdiv($d);
         $z->binc(); $d->binc();
diff --git a/cpan/Math-BigInt/lib/Math/BigInt/Calc.pm b/cpan/Math-BigInt/lib/Math/BigInt/Calc.pm
index 52e33d2..6527b38 100644
--- a/cpan/Math-BigInt/lib/Math/BigInt/Calc.pm
+++ b/cpan/Math-BigInt/lib/Math/BigInt/Calc.pm
@@ -1264,7 +1264,7 @@ sub _is_even
 
 sub _is_odd
   {
-  # return true if arg is even
+  # return true if arg is odd
   (($_[1]->[0] & 1)) <=> 0; 
   }
 
@@ -1536,22 +1536,20 @@ sub _nok
   # ref to array, return ref to array
   my ($c,$n,$k) = @_;
 
-  # ( 7 )    7!          7*6*5 * 4*3*2*1   7 * 6 * 5
-  # ( - ) = --------- =  --------------- = ---------
-  # ( 3 )   3! (7-3)!    3*2*1 * 4*3*2*1   3 * 2 * 1 
-
-  # compute n - k + 2 (so we start with 5 in the example above)
-  my $x = _copy($c,$n);
+  # ( 7 )       7!       1*2*3*4 * 5*6*7   5 * 6 * 7       6   7
+  # ( - ) = --------- =  --------------- = --------- = 5 * - * -
+  # ( 3 )   (7-3)! 3!    1*2*3*4 * 1*2*3   1 * 2 * 3       2   3
 
-  _sub($c,$n,$k);
-  if (!_is_one($c,$n))
+  if (!_is_zero($c,$k))
     {
+    my $x = _copy($c,$n);
+    _sub($c,$n,$k);
     _inc($c,$n);
     my $f = _copy($c,$n); _inc($c,$f);		# n = 5, f = 6, d = 2
     my $d = _two($c);
-    while (_acmp($c,$f,$x) <= 0)		# f < n ?
+    while (_acmp($c,$f,$x) <= 0)		# f <= n ?
       {
-      # n = (n * f / d) == 5 * 6 / 2 => n == 3
+      # n = (n * f / d) == 5 * 6 / 2
       $n = _mul($c,$n,$f); $n = _div($c,$n,$d);
       # f = 7, d = 3
       _inc($c,$f); _inc($c,$d);
diff --git a/cpan/Math-BigInt/t/bigintpm.inc b/cpan/Math-BigInt/t/bigintpm.inc
index 87140ba..317e5ed 100644
--- a/cpan/Math-BigInt/t/bigintpm.inc
+++ b/cpan/Math-BigInt/t/bigintpm.inc
@@ -2346,9 +2346,12 @@ NaN:1:NaN
 1:-2:0
 # 7 over 3 = 35
 7:3:35
-7:6:1
+7:6:7
 100:90:17310309456440
 100:95:75287520
+2:0:1
+7:0:1
+2:1:2
 &bround
 $round_mode('trunc')
 0:12:0

@p5pRT
Copy link
Author

p5pRT commented Sep 3, 2010

From @rafl

Applied, after some slight fixups, as
d573594. Thanks!

@p5pRT
Copy link
Author

p5pRT commented Sep 3, 2010

From [Unknown Contact. See original ticket]

Applied, after some slight fixups, as
d573594. Thanks!

@p5pRT
Copy link
Author

p5pRT commented Sep 3, 2010

@rafl - Status changed from 'new' to 'resolved'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant