Best search algorithm to find condition within a range

[Dave Angel]

On 04/07/2015 05: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.

For this and most of the following statements:  I can almost guess what 
you're trying to say.  However, I cannot.  No idea why you're adding up 
digits, that sounds like casting out nines.  And in base-N, that would 
be casting out (N-1)'s.

What's the it you're trying to search?

How do you know the baseconversion is the bottleneck, if you haven't 
written any Python code yet?


>
> I need the fastest algorithm to find the relation to a decimal number.

What relation would that be?  Between what and what?

> 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.
>

You haven't defined a class "Base" yet.  In fact, I don't see any Python 
code in the whole message.

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

You could try integer divide.  That's just something like
      digit = decNumber // digmult
But if you think hard enough you'd realize that


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

If that code were in Python, I could be more motivated to critique it. 
The whole algorithm could be much simpler.  But perhaps there is some 
limitation of javascript that's crippling the code.

How would you do it if you were converting the base by hand?  I 
certainly wouldn't be doing any trial and error.  For each pass, I'd 
calculate quotient and remainder, where remainder is the digit, and 
quotient is the next value you work on.


-- 
DaveA