# Is there a more efficient way to compute the first digit of a number?

I need to compute the first digit of some large numbers. So far I've been converting them to strings, although it can be somewhat slow. For example:

sage: %timeit str(2^57885161)[0]
1 loops, best of 3: 3.07 s per loop


Is there a faster way to to do this? For my purpose you can assume that all the numbers involved are powers of some small base.

edit retag close merge delete

Sort by » oldest newest most voted

I am not sure it is the fastest way, but this i already much faster:

sage: %timeit str(RealLazyField()(2^57885161))[0]
100 loops, best of 3: 11.1 ms per loop


(my laptop is slower than yours, since your timeit takes me 13.4 s per loop, so you should get a better timing).

more

Floats are supposed to get the first few digits correct, so

sage: sage: RR(2)^57885161
5.81887266232246e17425169


should give you the answer. It's fast:

sage: %timeit str(RR(2)^57885161)[0]
100000 loops, best of 3: 3.57 µs per loop

( 2015-11-11 17:42:24 +0200 )edit

Note though that using RR may be dangerous in some cases:

sage: p = 1164288119
sage: q = 858893931563
sage: p*q
999999999999999999997
sage: RR(p*q)
1.00000000000000e21
sage: RR(p)*RR(q)
1.00000000000000e21


Also, without relying on RealLazyField, you can search the first digit by dichotomy: Let k = 10^(d-1) where d is the number of digits (sage: d = (2^57885161).ndigits()), you only have to find c between 1 and 9 such that you number is between c*k and (c+1)*k. My own implementation of this method is longer that Thierry's for you example, but is faster with my example above.

( 2015-11-12 11:33:28 +0200 )edit

Can you explain how this works? I have no trouble with the concept of lazy evaluation, but why doesn't str force the evaluation of the whole number? Or maybe it does, automatically selecting the optimal precision to compute the required result?

( 2015-11-12 21:29:03 +0200 )edit

By the way, is there a particular reason why you used RLF(2^57885161) instead of RLF(2)^57885161? On my machine timing the first expression gives 100 loops, best of 3: 2.42 ms per loop, while the second one gives 1000 loops, best of 3: 285 µs per loop. To my inexpert eye this suggests that in the first case 2^57885161 is computed exactly and then converted to a floating point value, while in the second case the power is computed directly in floating point arithmetic.

( 2015-11-12 22:21:26 +0200 )edit

Good point about floating point errors being able to affect the leading digit! You'd have to check that the value is not very close to a cross-over point:

sage: a=RR(2)^57885161
sage: (a-(10.0)^floor(a.log()/(10.0).log()))/a
0.828145405814591


as long as this value isn't very close to 0 or 1 you should be fine.

If you want to use integer arithmetic, please don't use dichotomy, though. That's what we have long division for.

sage: a=2^57885161
sage: b=10^((RR(a).log()/log(10.0)).floor())
sage: b<=a
True
sage: a//b
5


If you get "True" and 0,...,9 from this, it's certainly the leading digit. If not, some rounding managed to get you the wrong number of digits (shouldn't really happen).

( 2015-11-12 22:23:52 +0200 )edit