Best search algorithm to find condition within a range

[Steven D'Aprano]

On Wed, 8 Apr 2015 03:07 am, jonas.thornvall at gmail.com wrote:

> So you can tell me the first (higest) digit of the integer
>
2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490


First digit:
py> s
= '2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490'
py> s[0]
'2'


Highest digit:

py> max(s)
'9'


> Using base 429496729?

That makes no sense. With base 429496729 you need to have 429496729
different digits. Of course it is possible that, just by chance, you end up
with something that only includes the digits 0 through 9. Of course that is
possible, just like there are decimal numbers which only use digits 0
through 1, e.g. 10001.

If you want to go the other way, and convert s FROM decimal INTO base
429496729, you need to tell us what digits to use. You need 429496729
different digits.


> How long time did it take to find it?

A tiny fraction of a second.

py> from timeit import Timer
py> setup = "s
= '2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490'"
py> t = Timer("s[0]; max(s)", setup)
py> min(t.repeat())
7.158415079116821


That's just over 7 seconds to calculate both the first and the highest digit
one million times, or about 7 microseconds each time.




-- 
Steven