diff options
author | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-08-03 13:27:25 +0000 |
---|---|---|
committer | akr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2013-08-03 13:27:25 +0000 |
commit | f858cd8a382169c40656b7511dd4b657f57f3bdc (patch) | |
tree | 4d23246305662705ac43c5e1f37d09d3bddea16c /bignum.c | |
parent | dfe7399a45eab3ef71ab4b0e72b7c4fdeab5aff2 (diff) |
* bignum.c (big2str_orig): Receive the number to stringize as
BDIGIT array and size.
(big2str_karatsuba): Receive the number to stringize as BDIGIT array
and size. Use an temporary array of BDIGIT.
(rb_big2str1): Follow the above change.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42356 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'bignum.c')
-rw-r--r-- | bignum.c | 74 |
1 files changed, 39 insertions, 35 deletions
@@ -4247,23 +4247,21 @@ big2str_alloc(struct big2str_struct *b2s, size_t len) } static void -big2str_orig(struct big2str_struct *b2s, VALUE x, size_t taillen) +big2str_orig(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, size_t taillen) { - long i = RBIGNUM_LEN(x); size_t j; - BDIGIT* ds = BDIGITS(x); BDIGIT_DBL num; char buf[SIZEOF_BDIGIT_DBL*CHAR_BIT], *p; int beginning = !b2s->ptr; size_t len = 0; - assert(i <= 2); + assert(xn <= 2); num = 0; - if (0 < i) - num = ds[0]; - if (1 < i) - num |= BIGUP(ds[1]); + if (0 < xn) + num = xds[0]; + if (1 < xn) + num |= BIGUP(xds[1]); if (beginning) { if (num == 0) @@ -4291,14 +4289,15 @@ big2str_orig(struct big2str_struct *b2s, VALUE x, size_t taillen) } static void -big2str_karatsuba(struct big2str_struct *b2s, VALUE x, - int power_level, size_t taillen) +big2str_karatsuba(struct big2str_struct *b2s, BDIGIT *xds, size_t xn, + int power_level, size_t taillen, + BDIGIT *wds, size_t wn) { - VALUE b, q, r; + VALUE b; size_t half_numdigits, lower_numdigits; int lower_power_level; - size_t xn, bn; - BDIGIT *xds, *bds; + size_t bn; + BDIGIT *bds; size_t len; /* @@ -4321,7 +4320,7 @@ big2str_karatsuba(struct big2str_struct *b2s, VALUE x, * power_cache_get_power(base, power_level-1, &len) should be cached already if 0 <= power_level-1. */ - if (BIGZEROP(x)) { + if (xn == 0 || bary_zero_p(xds, xn)) { if (b2s->ptr) { /* When x is zero, power_cache_get_power(base, power_level) should be cached already. */ power_cache_get_power(b2s->base, power_level, &len); @@ -4332,13 +4331,10 @@ big2str_karatsuba(struct big2str_struct *b2s, VALUE x, } if (power_level == 0) { - big2str_orig(b2s, x, taillen); + big2str_orig(b2s, xds, xn, taillen); return; } - 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); @@ -4363,24 +4359,35 @@ big2str_karatsuba(struct big2str_struct *b2s, VALUE x, memset(b2s->ptr, '0', len); b2s->ptr += len; } - big2str_orig(b2s, x, taillen); + big2str_orig(b2s, xds, xn, taillen); } else { + VALUE tmpw = 0; + BDIGIT *qds, *rds; + size_t qn, rn; 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); - rb_big_resize(q, 0); - big2str_karatsuba(b2s, r, lower_power_level, taillen); - rb_big_resize(r, 0); + if (wn < bn * 4 + BIGDIVREM_EXTRA_WORDS) { + wn = bn * 4 + BIGDIVREM_EXTRA_WORDS; + wds = ALLOCV_N(BDIGIT, tmpw, wn); + } + rn = bn; + qn = xn+BIGDIVREM_EXTRA_WORDS; + rds = wds; + qds = wds+rn; + bary_divmod(qds, qn, rds, rn, xds, xn, bds, bn); + while (0 < qn && qds[qn-1] == 0) + qn--; + assert(qn <= bn); + big2str_karatsuba(b2s, qds, qn, lower_power_level, lower_numdigits+taillen, qds+qn, wn-(rn+qn)); + while (0 < rn && rds[rn-1] == 0) + rn--; + big2str_karatsuba(b2s, rds, rn, lower_power_level, taillen, rds+rn, wn-rn); + if (tmpw) + ALLOCV_END(tmpw); } } @@ -4418,7 +4425,6 @@ big2str_base_powerof2(VALUE x, int base) static VALUE rb_big2str1(VALUE x, int base) { - VALUE xx; struct big2str_struct b2s_data; int power_level; VALUE power; @@ -4473,15 +4479,13 @@ rb_big2str1(VALUE x, int base) b2s_data.result = Qnil; b2s_data.ptr = NULL; - xx = rb_big_clone(x); - RBIGNUM_SET_SIGN(xx, 1); if (power_level == 0) { - big2str_orig(&b2s_data, xx, 0); + big2str_orig(&b2s_data, BDIGITS(x), RBIGNUM_LEN(x), 0); } else { - big2str_karatsuba(&b2s_data, xx, power_level, 0); + big2str_karatsuba(&b2s_data, BDIGITS(x), RBIGNUM_LEN(x), power_level, 0, NULL, 0); } - rb_big_resize(xx, 0); + RB_GC_GUARD(x); *b2s_data.ptr = '\0'; rb_str_resize(b2s_data.result, (long)(b2s_data.ptr - RSTRING_PTR(b2s_data.result))); |