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> 

 












 



More information about the Python-list mailing list