summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-07-31 16:20:26 +0000
committerakr <akr@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2013-07-31 16:20:26 +0000
commit4f1b07e9eb2a3aa00ab62d745f3e6e7d6b2d51d8 (patch)
tree5819a251c99f37f4a536870f0dc3fcbdddb6ea3d
parentd28913b4b9df545098a17de90588f45dbf110872 (diff)
* 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
-rw-r--r--ChangeLog9
-rw-r--r--bignum.c74
2 files changed, 49 insertions, 34 deletions
diff --git a/ChangeLog b/ChangeLog
index 4f09800..ac145f0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+Thu Aug 1 01:09:02 2013 Tanaka Akira <akr@fsij.org>
+
+ * 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 <akr@fsij.org>
* bignum.c (big2str_find_n1): Change the return type to size_t.
diff --git a/bignum.c b/bignum.c
index 3abcd6e..9da9530 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<<LOG2_KARATSUBA_BIG2STR_DIGITS)
-#define MAX_BIG2STR_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT)
+#define MAX_BIG2STR_TABLE_ENTRIES (SIZEOF_SIZE_T * CHAR_BIT + 1)
static VALUE big2str_power_cache[35][MAX_BIG2STR_TABLE_ENTRIES];
+static size_t big2str_numdigits_cache[35][MAX_BIG2STR_TABLE_ENTRIES];
static void
power_cache_init(void)
@@ -4118,40 +4117,47 @@ power_cache_init(void)
}
static inline VALUE
-power_cache_get_power0(int base, int i)
+power_cache_get_power(int base, int power_level, size_t *numdigits_ret)
{
- /* MAX_BIG2STR_TABLE_ENTRIES is big enough to that
+ /*
+ * MAX_BIG2STR_TABLE_ENTRIES is big enough to that
* big2str_power_cache[base][MAX_BIG2STR_TABLE_ENTRIES-1] fills whole memory.
- * So MAX_BIG2STR_TABLE_ENTRIES <= i is not possible to calculate.
+ * So MAX_BIG2STR_TABLE_ENTRIES <= power_level is not possible to calculate.
*
- * big2str_power_cache[base][MAX_BIG2STR_TABLE_ENTRIES-1] =
- * (base**KARATSUBA_BIG2STR_DIGITS)**(MAX_BIG2STR_TABLE_ENTRIES-1) =
- * (base**KARATSUBA_BIG2STR_DIGITS)**(SIZEOF_SIZE_T*CHAR_BIT-1) =
- * base**(KARATSUBA_BIG2STR_DIGITS*(SIZEOF_SIZE_T*CHAR_BIT-1)) > 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