Best search algorithm to find condition within a range

[jonas.thornvall at gmail.com]

Den tisdag 7 april 2015 kl. 18:34:32 UTC+2 skrev Dave Angel:
> On 04/07/2015 11:40 AM, jonas.thornvall at gmail.com wrote:
> > Den tisdag 7 april 2015 kl. 16:32:56 UTC+2 skrev Ian:
> >> On Tue, Apr 7, 2015 at 3:44 AM,  <jonas.thornvall at gmail.com> wrote:
> >>>
> >>>
> >>> I want todo faster baseconversion for very big bases like base 1 000 000, so instead of adding up digits i search it.
> >>>
> >>> I need the fastest algorithm to find the relation to a decimal number.
> >>> Digmult is an instance of base at a digitplace (base^x) what i try to find is the digit for the below condition is true and the loop break.
> >>>
> >>>
> >>> *********************************
> >>> for (digit=0;digit<=base;digit++) {
> >>>         if((digit+1)*digmult>decNumber)break;
> >>> }
> >>> *********************************
> >>>
>     <snip>
> >>
> >>> One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?
> >>
> >> Do you mean binary search? That would be an improvement over the
> >> linear search algorithm you've shown. Whether a trinary search might
> >> be faster would depend on the distribution of the numbers you expect.
> >> If they're evenly distributed, it will be slower.
> >>
> >>> I Think also i remember that if the search space so big that at least 22 or 23 guesses, needed.A random Oracle may even faster?
> >>>
> >>> Just pick up a number and get lucky, is it any truth to that?
> >>
> >> On average, a random Oracle with a search space of 1000000 will need
> >> 1000000 guesses.
> >
> > Well of course you use same principles like a binary search setting min and max, closing in on the digit. In this case the searched numbers  > base^exp  and number< base^exp+1.
> >
> > But since the search is within large bases upto 32-bit space, so base 4294967295 is the biggest allowed. I need to find the nearest less exp in base for each (lets call them pseudo digits). But as you see there it will take time to add them up. So better doing a binary search, you know min-max half (iteration). You can do the same for a random oracle min max within range, and if the number of tries in general over 22 i think a random oracle do it better than a binary search.
> >
> > It was a long time since i did this, but i do know there is a threshold where searching min max with the oracle will be faster than the binary search.
> >
> 
> Once again, there's no point in doing a search, when a simple integer 
> divide can give you the exact answer.  And there's probably no point in 
> going left to right when right to left would yield a tiny, fast program.
> 
> I haven't seen one line of Python from you yet, so perhaps you're just 
> yanking our chain.  I'm not here to optimize Javascript code.
> 
> Using only Python 3.4 and builtin functions, this function can be 
> implemented straightforwardly in 7 lines, assuming number is nonnegative 
> integer, and base is positive integer.  It definitely could be done 
> smaller, but then the code might be more confusing.
> 
> -- 
> DaveA

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

Using base 429496729?

How long time did it take to find it?