* src/integer/conv/cl_I_cached_power.h: New file.

[cln.git] / src / integer / conv / cl_I_from_digits.cc

diff --git a/src/integer/conv/cl_I_from_digits.cc b/src/integer/conv/cl_I_from_digits.cc
index 7e101ac39175e4bd9013955a5a354138675d6150..bbb1a51f9cb7f1d6cff8edb31f4979025177ed66 100644 (file)
--- a/src/integer/conv/cl_I_from_digits.cc
+++ b/src/integer/conv/cl_I_from_digits.cc
@@ -10,6 +10,7 @@
 // Implementation.\r
 \r
 #include "cl_DS.h"\r
+#include "cl_I_cached_power.h"\r
 \r
 namespace cln {\r
 \r
@@ -57,39 +58,6 @@ static const cl_I digits_to_I_base2 (const char * MSBptr, uintL len, uintD base)
        return NUDS_to_I(erg_MSDptr,erg_len);\r
 }\r
 \r
-// For each base b in [2..36], power_table[b-2] contains the largest exponent e\r
-// such that b^e<2^intDsize, i.e. floor(log(2^intDsize-1,b)).\r
-static const uintC power_table [36-2+1] = {\r
-#if (intDsize==8)\r
-       /* base  2..7  */           7,  5,  3,  3,  3,  2,\r
-       /* base  8..15 */   2,  2,  2,  2,  2,  2,  2,  2,\r
-       /* base 16..23 */   1,  1,  1,  1,  1,  1,  1,  1,\r
-       /* base 24..31 */   1,  1,  1,  1,  1,  1,  1,  1,\r
-       /* base 32..36 */   1,  1,  1,  1,  1\r
-#endif\r
-#if (intDsize==16)\r
-       /* base  2..7  */          15, 10,  7,  6,  6,  5,\r
-       /* base  8..15 */   5,  5,  4,  4,  4,  4,  4,  4,\r
-       /* base 16..23 */   3,  3,  3,  3,  3,  3,  3,  3,\r
-       /* base 24..31 */   3,  3,  3,  3,  3,  3,  3,  3,\r
-       /* base 32..36 */   3,  3,  3,  3,  3\r
-#endif\r
-#if (intDsize==32)\r
-       /* base  2..7  */          31, 20, 15, 13, 12, 11,\r
-       /* base  8..15 */  10, 10,  9,  9,  8,  8,  8,  8,\r
-       /* base 16..23 */   7,  7,  7,  7,  7,  7,  7,  7,\r
-       /* base 24..31 */   6,  6,  6,  6,  6,  6,  6,  6,\r
-       /* base 32..36 */   6,  6,  6,  6,  6\r
-#endif\r
-#if (intDsize==64)\r
-       /* base  2..7  */          63, 40, 31, 27, 24, 22,\r
-       /* base  8..15 */  21, 20, 19, 18, 17, 17, 16, 16,\r
-       /* base 16..23 */  15, 15, 15, 15, 14, 14, 14, 14,\r
-       /* base 24..31 */  13, 13, 13, 13, 13, 13, 13, 12,\r
-       /* base 32..36 */  12, 12, 12, 12, 12\r
-#endif\r
-};\r
-\r
 static const cl_I digits_to_I_baseN (const char * MSBptr, uintL len, uintD base)\r
 {\r
        // base is not a power of two: Add digits one by one. Result nees\r
@@ -147,7 +115,7 @@ static const cl_I digits_to_I_baseN (const char * MSBptr, uintL len, uintD base)
                var uintD newdigit = 0;\r
                var uintC chx = 0;\r
                var uintD factor = 1;\r
-               while (chx < power_table[base-2] && len > 0) {\r
+               while (chx < power_table[base-2].k && len > 0) {\r
                        var uintB ch = *(const uintB *)MSBptr; MSBptr++; // next character\r
                        if (ch!='.') { // skip decimal point\r
                                // Compute value of ('0'-'9','A'-'Z','a'-'z'):\r
@@ -181,15 +149,25 @@ const cl_I digits_to_I (const char * MSBptr, uintL len, uintD base)
        } else {\r
                // This is quite insensitive to the breakeven point.\r
                // On a 1GHz Athlon I get approximately:\r
-               //   base  3: breakeven == 15000\r
-               //   base 10: breakeven ==  5000\r
-               //   base 36: breakeven ==  2000\r
-               if (len>50000/base)\r
+               //   base  3: breakeven around 25000\r
+               //   base 10: breakeven around  8000\r
+               //   base 36: breakeven around  2000\r
+               if (len>80000/base) {\r
                        // Divide-and-conquer:\r
-                       return digits_to_I(MSBptr,len/2,base)*expt_pos(base,len-len/2)\r
-                             +digits_to_I(MSBptr+len/2,len-len/2,base);\r
-               else\r
+                       // Find largest i such that B = base^(k*2^i) satisfies B <= X.\r
+                       var const cached_power_table_entry * p;\r
+                       var uintC len_B = power_table[base-2].k;\r
+                       for (uintC i = 0; ; i++) {\r
+                               p = cached_power(base, i);\r
+                               if (2*len_B >= len)\r
+                                       break;\r
+                               len_B = len_B*2;\r
+                       }\r
+                       return digits_to_I(MSBptr,len-len_B,base)*p->base_pow\r
+                             +digits_to_I(MSBptr+len-len_B,len_B,base);\r
+               } else {\r
                        return digits_to_I_baseN(MSBptr, len, base);\r
+               }\r
        }\r
 }\r
 \r