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

This is a bug report for perl from [email protected],
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)

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