Best search algorithm to find condition within a range

[Ian Kelly]

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.