summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-08-02 09:36:23 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-08-02 09:36:23 +0000
commitbc7c0a63fd9c3e51a34b0904539112b74b8147b3 (patch)
tree93a112c90266b962dd780914d1ebcb57d7d45131
parent9e8f82e087ac7bc34098f94c2db5ea658dd6be80 (diff)
* bignum.c (big2str_karatsuba): Reduce power_level more than one at
recursion, if possible. (rb_big2str1): Follow the above change. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42325 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r--ChangeLog6
-rw-r--r--bignum.c94
2 files changed, 81 insertions, 19 deletions
diff --git a/ChangeLog b/ChangeLog
index d11f4c4..ca31d14 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,9 @@
+Fri Aug 2 18:33:28 2013 Tanaka Akira <akr@fsij.org>
+
+ * bignum.c (big2str_karatsuba): Reduce power_level more than one at
+ recursion, if possible.
+ (rb_big2str1): Follow the above change.
+
Fri Aug 2 12:25:15 2013 Tanaka Akira <akr@fsij.org>
* bignum.c (bary_mul): Swap x and y for bary_mul1 if x is longer than y.
diff --git a/bignum.c b/bignum.c
index fffb65f..6913290 100644
--- a/bignum.c
+++ b/bignum.c
@@ -4300,33 +4300,87 @@ static void
big2str_karatsuba(struct big2str_struct *b2s, VALUE x,
int power_level, size_t taillen)
{
- size_t m1;
VALUE b, q, r;
+ size_t half_numdigits, lower_numdigits;
+ int lower_power_level;
+ size_t xn, bn;
+ BDIGIT *xds, *bds;
size_t len;
+ /*
+ * Precondition:
+ * abs(x) < maxpow_in_bdigit_dbl(base, &numdigits)**(2**power_level)
+ *
+ * This function generates sequence of zeros, and then stringized abs(x) into b2s->ptr.
+ *
+ * b2s->ptr can be NULL.
+ * It is allocated when the first character is generated via big2str_alloc.
+ *
+ * The prefix zeros should be generated if and only if b2s->ptr is not NULL.
+ * When the zeros are generated, the zeros and abs(x) consists
+ * numdigits*(2**power_level) characters at total.
+ *
+ * Note:
+ * power_cache_get_power(base, power_level, &len) may not be cached yet. It should not be called.
+ * power_cache_get_power(base, power_level-1, &len) should be cached already if 0 <= power_level-1.
+ */
+
if (BIGZEROP(x)) {
if (b2s->ptr) {
- power_cache_get_power(b2s->base, power_level+1, &len);
+ /* When x is zero, power_cache_get_power(base, power_level) should be cached already. */
+ power_cache_get_power(b2s->base, power_level, &len);
memset(b2s->ptr, '0', len);
b2s->ptr += len;
}
return;
}
- if (power_level < 0) {
+ if (power_level == 0) {
big2str_orig(b2s, x, taillen);
return;
}
- b = power_cache_get_power(b2s->base, power_level, &m1);
+ xn = RBIGNUM_LEN(x);
+ xds = BDIGITS(x);
+
+ lower_power_level = power_level-1;
+ b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
+ bn = RBIGNUM_LEN(b);
+ bds = BDIGITS(b);
+
+ half_numdigits = lower_numdigits;
+
+ while (0 < lower_power_level &&
+ (xn < bn ||
+ (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
+ lower_power_level--;
+ b = power_cache_get_power(b2s->base, lower_power_level, &lower_numdigits);
+ bn = RBIGNUM_LEN(b);
+ 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;
+ }
- bigdivmod(x, b, &q, &r);
- rb_obj_hide(q);
- rb_obj_hide(r);
- big2str_karatsuba(b2s, q, power_level-1, m1+taillen);
- rb_big_resize(q, 0);
- big2str_karatsuba(b2s, r, power_level-1, taillen);
- rb_big_resize(r, 0);
+ if (lower_power_level == 0 &&
+ (xn < bn ||
+ (xn == bn && bary_cmp(xds, xn, bds, bn) < 0))) {
+ big2str_orig(b2s, x, taillen);
+ }
+ else {
+ bigdivmod(x, b, &q, &r);
+ bigtrunc(q);
+ bigtrunc(r);
+ rb_obj_hide(q);
+ rb_obj_hide(r);
+ big2str_karatsuba(b2s, q, lower_power_level, lower_numdigits+taillen);
+ rb_big_resize(q, 0);
+ big2str_karatsuba(b2s, r, lower_power_level, taillen);
+ rb_big_resize(r, 0);
+ }
}
static VALUE
@@ -4395,15 +4449,16 @@ rb_big2str1(VALUE x, int base)
power = power_cache_get_power(base, power_level, NULL);
}
assert(power_level != MAX_BIG2STR_TABLE_ENTRIES);
- if (FIX2LONG(bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(power), RBIGNUM_LEN(power))) < 0) {
- power_level--;
+ if (FIX2LONG(bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(power), RBIGNUM_LEN(power))) >= 0) {
+ power_level++;
+ }
+
#ifndef NDEBUG
- if (0 <= power_level) {
- 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
+ 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);
}
+#endif
b2s_data.negative = RBIGNUM_NEGATIVE_P(x);
b2s_data.base = base;
@@ -4415,7 +4470,7 @@ rb_big2str1(VALUE x, int base)
xx = rb_big_clone(x);
RBIGNUM_SET_SIGN(xx, 1);
- if (power_level < 0) {
+ if (power_level == 0) {
big2str_orig(&b2s_data, xx, 0);
}
else {
@@ -4524,6 +4579,7 @@ big2ulong(VALUE x, const char *type)
return num;
}
+/* deprecated */
VALUE
rb_big2ulong_pack(VALUE x)
{