Best search algorithm to find condition within a range
jonas.thornvall at gmail.com
jonas.thornvall at gmail.com
Tue Apr 7 16:10:49 CEST 2015
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.
More information about the Python-list
mailing list