Best search algorithm to find condition within a range

[jonas.thornvall at gmail.com]

Den tisdag 7 april 2015 kl. 15:30:36 UTC+2 skrev 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

I am doing it just like i would do it by hand finding the biggest digit first. To do that i need to know nearest base^exp that is less than the actual number. Add up the digit (multiply) it to the nearest smaller multiple. Subtract that number (base^exp*multiple). 

Divide / Scale down the exponent with base. And record the digit.
And start looking for next digit doing same manipulation until remainder = 0.

And that is what i am doing.