https://bugs.ruby-lang.org/
https://bugs.ruby-lang.org/favicon.ico?1711330511
2010-04-11T01:12:43Z
Ruby Issue Tracking System
Ruby master - Bug #3034: Bignum: "bigadd_core: Assertion `i <= zn' failed"
https://bugs.ruby-lang.org/issues/3034?journal_id=10044
2010-04-11T01:12:43Z
mame (Yusuke Endoh)
mame@ruby-lang.org
<ul><li><strong>Assignee</strong> set to <i>mame (Yusuke Endoh)</i></li><li><strong>Target version</strong> set to <i>1.9.2</i></li></ul><p>=begin<br>
Hi, Run Paint Run Run</p>
<p>2010/3/29 Run Paint Run Run <a href="mailto:redmine@ruby-lang.org" class="email">redmine@ruby-lang.org</a>:</p>
<blockquote>
<p>ruby -ve 'Marshal.load(File.read("/tmp/bignum.mars")).reduce(:*)'<br>
ruby 1.9.2dev (2010-03-22 trunk 27009) [i686-linux]<br>
ruby: bignum.c:1844: bigadd_core: Assertion `i <= zn' failed.<br>
Aborted</p>
<p><code>bignum.mars</code>, attached, contains an Array of Bignums.</p>
</blockquote>
<p>Excellent report!!</p>
<p>This is a bug of Karatsuba multiplication:</p>
<p>diff --git a/bignum.c b/bignum.c<br>
index 63635a6..77dec0f 100644<br>
--- a/bignum.c<br>
+++ b/bignum.c<br>
@@ -2077,7 +2077,7 @@ static VALUE<br>
bigmul1_karatsuba(VALUE x, VALUE y)<br>
{<br>
long i, n, xn, yn, t1n, t2n;</p>
<ul>
<li>VALUE xh, xl, yh, yl, z, t1, t2;</li>
</ul>
<ul>
<li>
<p>VALUE xh, xl, yh, yl, z, t1, t2, t3;<br>
BDIGIT *zds;</p>
<p>xn = RBIGNUM_LEN(x);<br>
@@ -2122,24 +2122,19 @@ bigmul1_karatsuba(VALUE x, VALUE y)<br>
/* copy t2 into low bytes of the result (z0) */<br>
MEMCPY(zds, BDIGITS(t2), BDIGIT, t2n);<br>
for (i = t2n; i < 2 * n; i++) zds[i] = 0;</p>
</li>
</ul>
<ul>
<li>
<li>/* subtract t2 from middle bytes of the result (z1) */</li>
<li>i = xn + yn - n;</li>
<li>bigsub_core(zds + n, i, BDIGITS(t2), t2n, zds + n, i);<br>
}<br>
else {</li>
</ul>
<ul>
<li>t2 = Qundef;</li>
<li>/* copy 0 into low bytes of the result (z0) */<br>
for (i = 0; i < 2 * n; i++) zds[i] = 0;<br>
}</li>
</ul>
<ul>
<li>/* subtract t1 from middle bytes of the result (z1) */</li>
<li>i = xn + yn - n;</li>
<li>bigsub_core(zds + n, i, BDIGITS(t1), t1n, zds + n, i);</li>
<li>/* xh <- xh + xl */<br>
if (RBIGNUM_LEN(xl) > RBIGNUM_LEN(xh)) {</li>
<li>t1 = xl; xl = xh; xh = t1;</li>
</ul>
<ul>
<li>t3 = xl; xl = xh; xh = t3;<br>
}</li>
<li>/* xh has a margin for carry <em>/<br>
bigadd_core(BDIGITS(xh), RBIGNUM_LEN(xh),<br>
BDIGITS(xl), RBIGNUM_LEN(xl),<br>
BDIGITS(xh), RBIGNUM_LEN(xh));<br>
@@ -2147,19 +2142,27 @@ bigmul1_karatsuba(VALUE x, VALUE y)<br>
/</em> yh <- yh + yl */<br>
if (x != y) {<br>
if (RBIGNUM_LEN(yl) > RBIGNUM_LEN(yh)) {</li>
</ul>
<ul>
<li>
<pre><code> t1 = yl; yl = yh; yh = t1;
</code></pre>
</li>
</ul>
<ul>
<li>
<pre><code> t3 = yl; yl = yh; yh = t3;
</code></pre>
}</li>
<li>/* yh has a margin for carry */<br>
bigadd_core(BDIGITS(yh), RBIGNUM_LEN(yh),<br>
BDIGITS(yl), RBIGNUM_LEN(yl),<br>
BDIGITS(yh), RBIGNUM_LEN(yh));<br>
}<br>
else yh = xh;</li>
</ul>
<ul>
<li>/* t1 <- xh * yh */</li>
<li>t1 = bigmul0(xh, yh);</li>
</ul>
<ul>
<li>/* t3 <- xh * yh */</li>
<li>t3 = bigmul0(xh, yh);</li>
<li>
<li>i = xn + yn - n;</li>
<li>/* add t3 to middle bytes of the result (z1) */</li>
<li>bigadd_core(zds + n, i, BDIGITS(t3), big_real_len(t3), zds + n, i);</li>
<li>
<li>/* subtract t1 from middle bytes of the result (z1) */</li>
<li>bigsub_core(zds + n, i, BDIGITS(t1), t1n, zds + n, i);</li>
</ul>
<ul>
<li>/* add t1 to middle bytes of the result (z1) */</li>
<li>bigadd_core(zds + n, i, BDIGITS(t1), big_real_len(t1), zds + n, i);</li>
</ul>
<ul>
<li>
<p>/* subtract t2 from middle bytes of the result (z1) */</p>
</li>
<li>
<p>if (t2 != Qundef) bigsub_core(zds + n, i, BDIGITS(t2), t2n, zds + n, i);</p>
<p>return z;<br>
}</p>
</li>
</ul>
<p>--<br>
Yusuke ENDOH <a href="mailto:mame@tsg.ne.jp" class="email">mame@tsg.ne.jp</a><br>
=end</p>
Ruby master - Bug #3034: Bignum: "bigadd_core: Assertion `i <= zn' failed"
https://bugs.ruby-lang.org/issues/3034?journal_id=10382
2010-04-21T00:37:06Z
mame (Yusuke Endoh)
mame@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>=begin<br>
This issue was solved with changeset r27425.<br>
Run Paint, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<p>=end</p>