From 4f1b07e9eb2a3aa00ab62d745f3e6e7d6b2d51d8 Mon Sep 17 00:00:00 2001 From: akr Date: Wed, 31 Jul 2013 16:20:26 +0000 Subject: * bignum.c (LOG2_KARATSUBA_BIG2STR_DIGITS): Removed. (KARATSUBA_BIG2STR_DIGITS): Removed. (big2str_numdigits_cache): New variable. (power_cache_get_power): Merged with power_cache_get_power0. This function returns maxpow_in_bdigit_dbl(base)**(2**power_level). (rb_big2str1): use power_cache_get_power. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@42295 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- ChangeLog | 9 ++++++++ bignum.c | 74 ++++++++++++++++++++++++++++++++++----------------------------- 2 files changed, 49 insertions(+), 34 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4f0980068e..ac145f089d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +Thu Aug 1 01:09:02 2013 Tanaka Akira + + * bignum.c (LOG2_KARATSUBA_BIG2STR_DIGITS): Removed. + (KARATSUBA_BIG2STR_DIGITS): Removed. + (big2str_numdigits_cache): New variable. + (power_cache_get_power): Merged with power_cache_get_power0. + This function returns maxpow_in_bdigit_dbl(base)**(2**power_level). + (rb_big2str1): use power_cache_get_power. + Wed Jul 31 23:59:28 2013 Tanaka Akira * bignum.c (big2str_find_n1): Change the return type to size_t. diff --git a/bignum.c b/bignum.c index 3abcd6e7af..9da95309ab 100644 --- a/bignum.c +++ b/bignum.c @@ -4100,11 +4100,10 @@ big_rshift(VALUE x, unsigned long shift) return big_shift3(x, 0, s1, s2); } -#define LOG2_KARATSUBA_BIG2STR_DIGITS 7 -#define KARATSUBA_BIG2STR_DIGITS (1L< 2**(SIZEOF_SIZE_T*CHAR_BIT-1) - * where - * 2 <= base - * 1 < KARATSUBA_BIG2STR_DIGITS + * number-of-bytes = + * log256(big2str_power_cache[base][MAX_BIG2STR_TABLE_ENTRIES-1]) = + * log256(maxpow_in_bdigit_dbl(base)**(2**(MAX_BIG2STR_TABLE_ENTRIES-1))) = + * log256(maxpow_in_bdigit_dbl(base)**(2**(SIZEOF_SIZE_T*CHAR_BIT))) = + * (2**(SIZEOF_SIZE_T*CHAR_BIT))*log256(maxpow_in_bdigit_dbl(base)) = + * (256**SIZEOF_SIZE_T)*log256(maxpow_in_bdigit_dbl(base)) > + * (256**SIZEOF_SIZE_T)*(sizeof(BDIGIT_DBL)-1) > + * 256**SIZEOF_SIZE_T */ - if (MAX_BIG2STR_TABLE_ENTRIES <= i) - rb_bug("too big power number requested: (%d**%ld)**(2**%d)", base, KARATSUBA_BIG2STR_DIGITS, i); - - if (NIL_P(big2str_power_cache[base - 2][i])) { - big2str_power_cache[base - 2][i] = - i == 0 ? rb_big_pow(rb_int2big(base), INT2FIX(KARATSUBA_BIG2STR_DIGITS)) - : bigsq(power_cache_get_power0(base, i - 1)); - rb_gc_register_mark_object(big2str_power_cache[base - 2][i]); + if (MAX_BIG2STR_TABLE_ENTRIES <= power_level) + rb_bug("too big power number requested: maxpow_in_bdigit_dbl(%d)**(2**%d)", base, power_level); + + if (NIL_P(big2str_power_cache[base - 2][power_level])) { + VALUE power; + size_t numdigits; + if (power_level == 0) { + int numdigits0; + BDIGIT_DBL dd = maxpow_in_bdigit_dbl(base, &numdigits0); + power = bignew(2, 1); + BDIGITS(power)[0] = BIGLO(dd); + BDIGITS(power)[1] = (BDIGIT)BIGDN(dd); + numdigits = numdigits0; + } + else { + power = bigsq(power_cache_get_power(base, power_level - 1, &numdigits)); + numdigits *= 2; + } + big2str_power_cache[base - 2][power_level] = power; + big2str_numdigits_cache[base - 2][power_level] = numdigits; + rb_gc_register_mark_object(power); } - return big2str_power_cache[base - 2][i]; -} - -static VALUE -power_cache_get_power(int base, int power_level, size_t *numdigits_ret) -{ - VALUE power; - power = power_cache_get_power0(base, power_level); if (numdigits_ret) - *numdigits_ret = KARATSUBA_BIG2STR_DIGITS * ((size_t)1 << power_level); - return power; + *numdigits_ret = big2str_numdigits_cache[base - 2][power_level]; + return big2str_power_cache[base - 2][power_level]; } /* big2str_muraken_find_n1 @@ -4345,18 +4351,18 @@ rb_big2str1(VALUE x, int base, int trim) ptr[0] = RBIGNUM_SIGN(x) ? '+' : '-'; power_level = 0; - power = power_cache_get_power0(base, power_level); + power = power_cache_get_power(base, power_level, NULL); 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); + 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--; #ifndef NDEBUG if (0 <= power_level) { - VALUE power0 = power_cache_get_power0(base, 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 -- cgit v1.2.3