Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Tue, 07 Apr 2015 09:29:59 -0400
From: Dave Angel <davea@davea.name>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.5.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Best search algorithm to find condition within a range
References: <2e3a3c01-20b3-4948-9b32-bd80ed46822b@googlegroups.com>
In-Reply-To: <2e3a3c01-20b3-4948-9b32-bd80ed46822b@googlegroups.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.89.1428413413.12925.python-list@python.org>
Lines: 103
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:88575

On 04/07/2015 05:44 AM, jonas.thornvall@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