Best search algorithm to find condition within a range
jonas.thornvall at gmail.com
jonas.thornvall at gmail.com
Tue Apr 7 05:44:24 EDT 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>
More information about the Python-list
mailing list