Project

General

Profile

Bug #3034

Bignum: "bigadd_core: Assertion `i <= zn' failed"

Added by runpaint (Run Paint Run Run) over 10 years ago. Updated over 9 years ago.

Status:
Closed
Priority:
Normal
Target version:
ruby -v:
ruby 1.9.2dev (2010-03-22 trunk 27009) [i686-linux]
Backport:
[ruby-core:29088]

Description

=begin
ruby -ve 'Marshal.load(File.read("/tmp/bignum.mars")).reduce(:*)'
ruby 1.9.2dev (2010-03-22 trunk 27009) [i686-linux]
ruby: bignum.c:1844: bigadd_core: Assertion `i <= zn' failed.
Aborted

bignum.mars, attached, contains an Array of Bignums.
=end


Files

bignum.mars (186 KB) bignum.mars runpaint (Run Paint Run Run), 03/29/2010 06:42 AM
#1

Updated by mame (Yusuke Endoh) over 10 years ago

  • Assignee set to mame (Yusuke Endoh)
  • Target version set to 1.9.2

=begin
Hi, Run Paint Run Run

2010/3/29 Run Paint Run Run redmine@ruby-lang.org:

ruby -ve 'Marshal.load(File.read("/tmp/bignum.mars")).reduce(:*)'
ruby 1.9.2dev (2010-03-22 trunk 27009) [i686-linux]
ruby: bignum.c:1844: bigadd_core: Assertion `i <= zn' failed.
Aborted

bignum.mars, attached, contains an Array of Bignums.

Excellent report!!

This is a bug of Karatsuba multiplication:

diff --git a/bignum.c b/bignum.c
index 63635a6..77dec0f 100644
--- a/bignum.c
+++ b/bignum.c
@@ -2077,7 +2077,7 @@ static VALUE
bigmul1_karatsuba(VALUE x, VALUE y)
{
long i, n, xn, yn, t1n, t2n;

  • VALUE xh, xl, yh, yl, z, t1, t2;
  • VALUE xh, xl, yh, yl, z, t1, t2, t3;
    BDIGIT *zds;

    xn = RBIGNUM_LEN(x);
    @@ -2122,24 +2122,19 @@ bigmul1_karatsuba(VALUE x, VALUE y)
    /* copy t2 into low bytes of the result (z0) */
    MEMCPY(zds, BDIGITS(t2), BDIGIT, t2n);

    for (i = t2n; i < 2 * n; i++) zds[i] = 0;

  • /* subtract t2 from middle bytes of the result (z1) */

  • i = xn + yn - n;

  • bigsub_core(zds + n, i, BDIGITS(t2), t2n, zds + n, i);
    }
    else {

  • t2 = Qundef;
    +
    /* copy 0 into low bytes of the result (z0) */
    for (i = 0; i < 2 * n; i++) zds[i] = 0;
    }

  • /* subtract t1 from middle bytes of the result (z1) */

  • i = xn + yn - n;

  • bigsub_core(zds + n, i, BDIGITS(t1), t1n, zds + n, i);

    /* xh <- xh + xl */
    if (RBIGNUM_LEN(xl) > RBIGNUM_LEN(xh)) {

  • t1 = xl; xl = xh; xh = t1;

  • t3 = xl; xl = xh; xh = t3;
    }

  • /* xh has a margin for carry /
    bigadd_core(BDIGITS(xh), RBIGNUM_LEN(xh),
    BDIGITS(xl), RBIGNUM_LEN(xl),
    BDIGITS(xh), RBIGNUM_LEN(xh));
    @@ -2147,19 +2142,27 @@ bigmul1_karatsuba(VALUE x, VALUE y)
    /
    yh <- yh + yl */
    if (x != y) {
    if (RBIGNUM_LEN(yl) > RBIGNUM_LEN(yh)) {

  •  t1 = yl; yl = yh; yh = t1;
    
  •  t3 = yl; yl = yh; yh = t3;
    

    }

  • /* yh has a margin for carry */
    bigadd_core(BDIGITS(yh), RBIGNUM_LEN(yh),
    BDIGITS(yl), RBIGNUM_LEN(yl),
    BDIGITS(yh), RBIGNUM_LEN(yh));
    }
    else yh = xh;

  • /* t1 <- xh * yh */

  • t1 = bigmul0(xh, yh);

  • /* t3 <- xh * yh */

  • t3 = bigmul0(xh, yh);
    +

  • i = xn + yn - n;

  • /* add t3 to middle bytes of the result (z1) */

  • bigadd_core(zds + n, i, BDIGITS(t3), big_real_len(t3), zds + n, i);
    +

  • /* subtract t1 from middle bytes of the result (z1) */

  • bigsub_core(zds + n, i, BDIGITS(t1), t1n, zds + n, i);

  • /* add t1 to middle bytes of the result (z1) */

  • bigadd_core(zds + n, i, BDIGITS(t1), big_real_len(t1), zds + n, i);

  • /* subtract t2 from middle bytes of the result (z1) */

  • if (t2 != Qundef) bigsub_core(zds + n, i, BDIGITS(t2), t2n, zds + n, i);

    return z;
    }

--
Yusuke ENDOH mame@tsg.ne.jp
=end

#2

Updated by mame (Yusuke Endoh) over 10 years ago

  • Status changed from Open to Closed
  • % Done changed from 0 to 100

=begin
This issue was solved with changeset r27425.
Run Paint, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.

=end

Also available in: Atom PDF