Message253036
Currently, the code uses Py_ABS(Py_SIZE(x))*PyLong_SHIFT to estimate the upper-bound of the number of bits of the number x. It's a raw estimation, the difference can be up to 29 bits. We may try to compute the exact number of bits, x.bit_length().
Python 3.5 estimate the number of "decimalbase" (10**9) digits using:
def decimalbase_digits1(x):
bits = size(x) * PyLong_SHIFT
return 1 + bits // (3 * _PyLong_DECIMAL_SHIFT)
I wrote a test to compute how many digits are overallocated (and unused): 552961 for this function. I'm not sure that "1+" is needed, since 3.0 is already lower than log2(10) (3.32...). If we compute the exact number of bits using the Python 3.5 function, it's a little bit better:
def decimalbase_digits2(x):
bits = x.bit_length()
return 1 + bits // (3 * _PyLong_DECIMAL_SHIFT)
=> 546250 digits (1% less). You propose a better estimation:
def decimalbase_digits3(x):
digits = size(x)
d = (33 * _PyLong_DECIMAL_SHIFT) // (10 * PyLong_SHIFT - 33 * _PyLong_DECIMAL_SHIFT)
return 1 + digits + digits // d
With your estimation, only 504243 are overallocated (9% less than Python 3.5 function). But why only using 2 digits for log2(10) estimation? We can more digits:
def decimalbase_digits4(x):
bits = size(x) * PyLong_SHIFT
return bits * 10000 // (33219 * _PyLong_DECIMAL_SHIFT)
=> 491908 digits (11% less)
According to my tests, the best function uses the number of bits and the better estimation of log2(10):
def new_decimalbase_digits5(x):
bits = x.bit_length()
return bits * 10000 // (33219 * _PyLong_DECIMAL_SHIFT)
=> 483424 digits (13% less)
See attached for my tests. |
|
Date |
User |
Action |
Args |
2015-10-15 08:34:15 | vstinner | set | recipients:
+ vstinner, mark.dickinson, serhiy.storchaka |
2015-10-15 08:34:15 | vstinner | set | messageid: <1444898055.42.0.417015131896.issue25402@psf.upfronthosting.co.za> |
2015-10-15 08:34:15 | vstinner | link | issue25402 messages |
2015-10-15 08:34:14 | vstinner | create | |
|