Ask Your Question
1

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

asked 2015-11-11 04:10:44 -0600

A.P. gravatar image

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 flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
0

answered 2015-11-11 04:51:53 -0600

tmonteil gravatar image

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).

edit flag offensive delete link more

Comments

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
nbruin gravatar imagenbruin ( 2015-11-11 10:42:24 -0600 )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.

B r u n o gravatar imageB r u n o ( 2015-11-12 04:33:28 -0600 )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?

A.P. gravatar imageA.P. ( 2015-11-12 14:29:03 -0600 )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.

A.P. gravatar imageA.P. ( 2015-11-12 15:21:26 -0600 )edit

@Bruno:

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).

nbruin gravatar imagenbruin ( 2015-11-12 15:23:52 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-11-11 04:10:44 -0600

Seen: 113 times

Last updated: Nov 11 '15