29 Aug
2009
29 Aug
'09
11:12 p.m.
Bulat Ziganshin schrieb:
Hello Henning,
Tuesday, August 25, 2009, 7:01:24 PM, you wrote:
I hope that 'show' will not need quadratic time but will employ a more efficient algorithm
yes, you are right
I thought a little about it. If I had to implement that in GMP it could be done quite fast in many cases: Count the number of bits, say it is 'k' and multiply with logBase 10 2. If 2^k and 2^(k+1)-1 have the same number of decimal digits, we are done. Otherwise we have to process some of the most significant bits. If the number is between n*2^k and (n+1)*2^k-1 and both bounds have the same number of decimal digits (logBase 10 n + k * logBase 10 2), we are also done. Only for numbers close to powers of 10 we have to process the whole integer.