summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-08-02 14:53:22 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-08-02 14:53:22 +0000
commit54c3b1ba19793f8735f1b99dbc964995bb903e17 (patch)
treec28abffd667fdee551f01e66970775d80676a594
parent7c9a3d19fcacb57463d823d06f579129fa836820 (diff)
* bignum.c (power_cache_get_power): Appry bigtrunc to the result of
bigsq. (big2str_karatsuba): Fix number of leading zero characters. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42335 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r--ChangeLog6
-rw-r--r--bignum.c29
-rw-r--r--test/ruby/test_bignum.rb2
3 files changed, 28 insertions, 9 deletions
diff --git a/ChangeLog b/ChangeLog
index ae0a75f..9e668d8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+Fri Aug 2 23:50:53 2013 Tanaka Akira <akr@fsij.org>
+
+ * bignum.c (power_cache_get_power): Appry bigtrunc to the result of
+ bigsq.
+ (big2str_karatsuba): Fix number of leading zero characters.
+
Fri Aug 2 23:48:36 2013 Nobuyoshi Nakada <nobu@ruby-lang.org>
* parse.y (parser_yylex): calculate denominator directly as powers of
diff --git a/bignum.c b/bignum.c
index 092b83d..ded2d6b 100644
--- a/bignum.c
+++ b/bignum.c
@@ -4156,7 +4156,7 @@ power_cache_get_power(int base, int power_level, size_t *numdigits_ret)
numdigits = numdigits0;
}
else {
- power = bigsq(power_cache_get_power(base, power_level - 1, &numdigits));
+ power = bigtrunc(bigsq(power_cache_get_power(base, power_level - 1, &numdigits)));
numdigits *= 2;
}
rb_obj_hide(power);
@@ -4358,21 +4358,26 @@ big2str_karatsuba(struct big2str_struct *b2s, VALUE x,
bds = BDIGITS(b);
}
- if (lower_power_level != power_level-1 && b2s->ptr) {
- len = (half_numdigits - lower_numdigits) * 2;
- memset(b2s->ptr, '0', len);
- b2s->ptr += len;
- }
-
if (lower_power_level == 0 &&
(xn < bn ||
(xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
+ if (b2s->ptr) {
+ len = half_numdigits * 2 - lower_numdigits;
+ memset(b2s->ptr, '0', len);
+ b2s->ptr += len;
+ }
big2str_orig(b2s, x, taillen);
}
else {
+ if (lower_power_level != power_level-1 && b2s->ptr) {
+ len = (half_numdigits - lower_numdigits) * 2;
+ memset(b2s->ptr, '0', len);
+ b2s->ptr += len;
+ }
bigdivmod(x, b, &q, &r);
bigtrunc(q);
bigtrunc(r);
+ assert(RBIGNUM_LEN(q) <= RBIGNUM_LEN(b));
rb_obj_hide(q);
rb_obj_hide(r);
big2str_karatsuba(b2s, q, lower_power_level, lower_numdigits+taillen);
@@ -4454,8 +4459,14 @@ rb_big2str1(VALUE x, int base)
#ifndef NDEBUG
if (0 < power_level) {
- VALUE power0 = power_cache_get_power(base, power_level-1, NULL);
- assert(FIX2LONG(bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(power0), RBIGNUM_LEN(power0))) >= 0);
+ VALUE power1 = power_cache_get_power(base, power_level-1, NULL);
+ assert(FIX2LONG(bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(power1), RBIGNUM_LEN(power1))) >= 0);
+ /*
+ {
+ VALUE power0 = power_cache_get_power(base, power_level, NULL);
+ assert(FIX2LONG(bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(power0), RBIGNUM_LEN(power0))) < 0);
+ }
+ */
}
#endif
diff --git a/test/ruby/test_bignum.rb b/test/ruby/test_bignum.rb
index 95c5dd7..c2f8738 100644
--- a/test/ruby/test_bignum.rb
+++ b/test/ruby/test_bignum.rb
@@ -106,6 +106,8 @@ class TestBignum < Test::Unit::TestCase
assert_equal("nd075ib45k86g" ,18446744073709551616.to_s(31), "[ruby-core:10686]")
assert_equal("1777777777777777777777" ,18446744073709551615.to_s(8))
assert_equal("-1777777777777777777777" ,-18446744073709551615.to_s(8))
+ assert_match(/\A10{99}1\z/, (10**100+1).to_s)
+ assert_match(/\A10{900}9{100}\z/, (10**1000+(10**100-1)).to_s)
end
b = 2**64