From 621d2b3d6cc2e9caf707840c63259552500cbe1c Mon Sep 17 00:00:00 2001 From: akr Date: Wed, 31 Jul 2013 13:42:22 +0000 Subject: * bignum.c (bary_cmp): Extracted from rb_big_cmp. (power_cache_get_power): Change n1 argument (number of digits) to power_level which is just passed to power_cache_get_power0. (big2str_karatsuba): Ditto. (rb_big2str1): Calculate the initial power_level. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42285 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- ChangeLog | 8 ++++++ bignum.c | 95 ++++++++++++++++++++++++++++++++++++++++----------------------- 2 files changed, 68 insertions(+), 35 deletions(-) diff --git a/ChangeLog b/ChangeLog index a7bf710034..9311919681 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +Wed Jul 31 22:36:21 2013 Tanaka Akira + + * bignum.c (bary_cmp): Extracted from rb_big_cmp. + (power_cache_get_power): Change n1 argument (number of digits) to + power_level which is just passed to power_cache_get_power0. + (big2str_karatsuba): Ditto. + (rb_big2str1): Calculate the initial power_level. + Wed Jul 31 22:04:36 2013 Kouhei Sutou * test/rexml/test_notationdecl_parsetest.rb: Fix a typo. diff --git a/bignum.c b/bignum.c index c530014798..6b40574ecc 100644 --- a/bignum.c +++ b/bignum.c @@ -481,6 +481,26 @@ maxpow_in_bdigit(int base, int *exp_ret) return maxpow; } +static int +bary_cmp(const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) +{ + while (0 < xn && xds[xn-1] == 0) + xn--; + while (0 < yn && yds[yn-1] == 0) + yn--; + + if (xn < yn) + return -1; + if (xn > yn) + return 1; + + while (xn-- && xds[xn] == yds[xn]) + ; + if (xn == (size_t)-1) + return 0; + return xds[xn] < yds[xn] ? -1 : 1; +} + static BDIGIT bary_small_lshift(BDIGIT *zds, const BDIGIT *xds, size_t n, int shift) { @@ -4125,19 +4145,13 @@ power_cache_get_power0(int base, int i) } static VALUE -power_cache_get_power(int base, long n1, long* m1) +power_cache_get_power(int base, int power_level, long *numdigits_ret) { - int i, m; - VALUE t; - - if (n1 <= KARATSUBA_BIG2STR_DIGITS) - rb_bug("n1 > KARATSUBA_BIG2STR_DIGITS"); - - m = bitsize(n1-1); /* ceil(log2(n1)) */ - if (m1) *m1 = 1 << m; /* smallest x which n1 <= x and x is a power of 2. */ - i = m - LOG2_KARATSUBA_BIG2STR_DIGITS; - t = power_cache_get_power0(base, i); - return t; + VALUE power; + power = power_cache_get_power0(base, power_level); + if (numdigits_ret) + *numdigits_ret = KARATSUBA_BIG2STR_DIGITS * (1 << power_level); + return power; } /* big2str_muraken_find_n1 @@ -4232,7 +4246,7 @@ big2str_orig(struct big2str_struct *b2s, VALUE x, char* ptr, long len, int trim) static long big2str_karatsuba(struct big2str_struct *b2s, VALUE x, char* ptr, - long n1, long len, int trim) + int power_level, long len, int trim) { long lh, ll, m1; VALUE b, q, r; @@ -4245,18 +4259,18 @@ big2str_karatsuba(struct big2str_struct *b2s, VALUE x, char* ptr, } } - if (n1 <= KARATSUBA_BIG2STR_DIGITS) { + if (power_level == 0) { return big2str_orig(b2s, x, ptr, len, trim); } - b = power_cache_get_power(b2s->base, n1, &m1); + b = power_cache_get_power(b2s->base, power_level, &m1); bigdivmod(x, b, &q, &r); rb_obj_hide(q); rb_obj_hide(r); - lh = big2str_karatsuba(b2s, q, ptr, (len - m1)/2, + lh = big2str_karatsuba(b2s, q, ptr, power_level-1, len - m1, trim); rb_big_resize(q, 0); - ll = big2str_karatsuba(b2s, r, ptr + lh, m1/2, + ll = big2str_karatsuba(b2s, r, ptr + lh, power_level-1, m1, !lh && trim); rb_big_resize(r, 0); @@ -4299,9 +4313,11 @@ rb_big2str1(VALUE x, int base, int trim) { int off; VALUE ss, xx; - long n1, n2, len; + long n2, len; char* ptr; struct big2str_struct b2s_data; + int power_level; + VALUE power; if (FIXNUM_P(x)) { return rb_fix2str(x, base); @@ -4320,21 +4336,38 @@ rb_big2str1(VALUE x, int base, int trim) return big2str_base_powerof2(x, (size_t)n2, base, trim); } - n1 = (n2 + 1) / 2; ss = rb_usascii_str_new(0, n2 + 1); /* plus one for sign */ ptr = RSTRING_PTR(ss); ptr[0] = RBIGNUM_SIGN(x) ? '+' : '-'; + power_level = 0; + power = power_cache_get_power0(base, power_level); + while (power_level < MAX_BIG2STR_TABLE_ENTRIES && + RBIGNUM_LEN(power) <= (RBIGNUM_LEN(x)+1)/2) { + power_level++; + power = power_cache_get_power0(base, power_level); + } + assert(power_level != MAX_BIG2STR_TABLE_ENTRIES); + 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_power0(base, power_level); + assert(FIX2LONG(bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(power0), RBIGNUM_LEN(power0))) >= 0); + } +#endif + } + b2s_data.base = base; b2s_data.hbase = maxpow_in_bdigit(base, &b2s_data.hbase_numdigits); off = !(trim && RBIGNUM_SIGN(x)); /* erase plus sign if trim */ xx = rb_big_clone(x); RBIGNUM_SET_SIGN(xx, 1); - if (n1 <= KARATSUBA_BIG2STR_DIGITS) { + if (power_level < 0) { len = off + big2str_orig(&b2s_data, xx, ptr + off, n2, trim); } else { - len = off + big2str_karatsuba(&b2s_data, xx, ptr + off, n1, + len = off + big2str_karatsuba(&b2s_data, xx, ptr + off, power_level, n2, trim); } rb_big_resize(xx, 0); @@ -4733,8 +4766,7 @@ rb_integer_float_eq(VALUE x, VALUE y) VALUE rb_big_cmp(VALUE x, VALUE y) { - long xlen = RBIGNUM_LEN(x); - BDIGIT *xds, *yds; + int cmp; switch (TYPE(y)) { case T_FIXNUM: @@ -4753,19 +4785,12 @@ rb_big_cmp(VALUE x, VALUE y) if (RBIGNUM_SIGN(x) > RBIGNUM_SIGN(y)) return INT2FIX(1); if (RBIGNUM_SIGN(x) < RBIGNUM_SIGN(y)) return INT2FIX(-1); - if (xlen < RBIGNUM_LEN(y)) - return (RBIGNUM_SIGN(x)) ? INT2FIX(-1) : INT2FIX(1); - if (xlen > RBIGNUM_LEN(y)) - return (RBIGNUM_SIGN(x)) ? INT2FIX(1) : INT2FIX(-1); - xds = BDIGITS(x); - yds = BDIGITS(y); - - while (xlen-- && (xds[xlen]==yds[xlen])); - if (-1 == xlen) return INT2FIX(0); - return (xds[xlen] > yds[xlen]) ? - (RBIGNUM_SIGN(x) ? INT2FIX(1) : INT2FIX(-1)) : - (RBIGNUM_SIGN(x) ? INT2FIX(-1) : INT2FIX(1)); + cmp = bary_cmp(BDIGITS(x), RBIGNUM_LEN(x), BDIGITS(y), RBIGNUM_LEN(y)); + if (RBIGNUM_SIGN(x)) + return INT2FIX(cmp); + else + return INT2FIX(-cmp); } enum big_op_t { -- cgit v1.2.3