Best search algorithm to find condition within a range

[jonas.thornvall at gmail.com]

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;
> > }
> > *********************************
> >
> > So i am looking for the digit where following condition true.
> >
> > if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then BREAK;
> 
> I'm not sure that I understand what it is that you're trying to
> accomplish. Are you trying to find the digits without using division
> because "division is slow"? If that's the case, then let me show you
> something.
> 
> $ python -m timeit -s "n = 1523837293" "n // 1000000"
> 1000000 loops, best of 3: 0.286 usec per loop
> 
> $ python -m timeit -s "n = 1523" "n * 1000000; (n+1) * 1000000"
> 1000000 loops, best of 3: 0.455 usec per loop
> 
> In Python, one addition and two multiplications are already slower
> than a single division. The only way you're going to beat division by
> using trial multiplication is if the first digit that you try is
> always correct. To do that, you would need an oracle feeding your
> search algorithm, and then you might as well just use the oracle.
> 
> > 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.