# Best search algorithm to find condition within a range

jonas.thornvall at gmail.com jonas.thornvall at gmail.com
Tue Apr 7 11:44:24 CEST 2015

```
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;

One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?

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?

Below the actual algorithm.

<SCRIPT LANGUAGE="Javascript">
//CONVERT A DECIMAL NUMBER INTO ANYBASE
function newbase(decNumber,base){
digits=1;
digmult=1;
while(digmult*base<=decNumber){
digmult=digmult*base
digits++;
}
digsave=digmult;
while(decNumber>0 || digits>0){
loop=1;
digit=0;
for (digit=0;digit<=base;digit++) {
if((digit+1)*digmult>decNumber)break;
}
out[digits]=digit;
digmult=digmult*digit;
decNumber=decNumber-digmult;
digsave=digsave/base;
digmult=digsave;
digits--;
}
return out;
}

var out= [];
base=256;
number=854544;
out=newbase(number,base);
out.reverse();
document.write("Number = ",out,"<BR>");
</script>

```