ruby-changes:30273
From: akr <ko1@a...>
Date: Fri, 2 Aug 2013 18:36:34 +0900 (JST)
Subject: [ruby-changes:30273] akr:r42325 (trunk): * bignum.c (big2str_karatsuba): Reduce power_level more than one at
akr 2013-08-02 18:36:23 +0900 (Fri, 02 Aug 2013) New Revision: 42325 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42325 Log: * bignum.c (big2str_karatsuba): Reduce power_level more than one at recursion, if possible. (rb_big2str1): Follow the above change. Modified files: trunk/ChangeLog trunk/bignum.c Index: ChangeLog =================================================================== --- ChangeLog (revision 42324) +++ ChangeLog (revision 42325) @@ -1,3 +1,9 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Fri Aug 2 18:33:28 2013 Tanaka Akira <akr@f...> + + * 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@f...> * bignum.c (bary_mul): Swap x and y for bary_mul1 if x is longer than y. Index: bignum.c =================================================================== --- bignum.c (revision 42324) +++ bignum.c (revision 42325) @@ -4300,33 +4300,87 @@ static void https://github.com/ruby/ruby/blob/trunk/bignum.c#L4300 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); - 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); + 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; + } + + 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) https://github.com/ruby/ruby/blob/trunk/bignum.c#L4449 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) https://github.com/ruby/ruby/blob/trunk/bignum.c#L4470 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) https://github.com/ruby/ruby/blob/trunk/bignum.c#L4579 return num; } +/* deprecated */ VALUE rb_big2ulong_pack(VALUE x) { -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/