Path: csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <davea@davea.name>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.087
X-Spam-Evidence: '*H*': 0.83; '*S*': 0.01; 'true,': 0.05; 'python3': 0.07; '[0]': 0.09; 'toss': 0.09; 'def': 0.12; '10000000': 0.16; 'expands': 0.16; 'internally': 0.16; 'reedy': 0.16; 'skip:t 100': 0.16; 'subject:search': 0.16; 'wrote:': 0.18; 'slightly': 0.19; '>>>': 0.22; 'header:User-Agent:1': 0.23; 'guys': 0.24; 'switch': 0.26; 'header:In-Reply-To:1': 0.27; '>>>>': 0.31; 'constant': 0.31; 'writes:': 0.31; 'probably': 0.32; 'skip:d 20': 0.34; 'but': 0.35; 'similar': 0.36; 'ben': 0.38; 'needed': 0.38; 'to:addr :python-list': 0.38; 'pm,': 0.38; 'sure': 0.39; 'to:addr:python.org': 0.39; 'enough': 0.39; 'according': 0.40; 'even': 0.60; 'ian': 0.60; 'results.': 0.60; 'times': 0.62; 'reach': 0.63; 'email addr:gmail.com': 0.63; 'become': 0.64; 'charset:windows-1252': 0.65; 'received:74.208': 0.68; '2015': 0.84; '6.1': 0.84; 'results,': 0.84; 'subject:find': 0.84; 'subject:Best': 0.91; 'factors': 0.97
Date: Tue, 07 Apr 2015 20:38:15 -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> <mailman.93.1428417164.12925.python-list@python.org> <d6e7bb84-3810-435a-bd7a-ad45da86f906@googlegroups.com> <mailman.108.1428424459.12925.python-list@python.org> <9fd13f49-8bfa-43ef-8787-21d5c76a6268@googlegroups.com> <CALwzidnbnbttdd+ow+gYg2-y8KDTAzXfEJ4c19OkEN=eOH2rLw@mail.gmail.com> <mg1973$lj6$1@ger.gmane.org> <mailman.112.1428434424.12925.python-list@python.org> <87384bzqlx.fsf@bsb.me.uk> <f6e43453-faa7-4243-ae4e-ad78e17d0966@googlegroups.com>
In-Reply-To: <f6e43453-faa7-4243-ae4e-ad78e17d0966@googlegroups.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Provags-ID: V03:K0:YacQimCrFOoRHMcBqdiWfU4inAlW/DwoyKZTvpw4WWS1zBJqMPg PTsprymtfi2VYU8EcG5G1nfeM/5bC6VqkOGeaV2jY6hvi86zpe3yCiRJAgyCrznuPMln0ZF PhUTOHeEfF3UtvHFLM4pTbDTw2q8BraFrB9Ip+k3v32RFF0xPRoL8EpWf5M9O4S4IOw8XfH 4DCRxQHHWKqUcNx9OtDJQ==
X-UI-Out-Filterresults: notjunk:1;
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.127.1428453500.12925.python-list@python.org>
Lines: 52
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1428453500 news.xs4all.nl 2889 [2001:888:2000:d::a6]:51956
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:88637

On 04/07/2015 06:35 PM, jonas.thornvall@gmail.com wrote:
> Den tisdag 7 april 2015 kl. 21:27:20 UTC+2 skrev Ben Bacarisse:
>> Ian Kelly <ian.g.kelly@gmail.com> writes:
>>
>>> On Tue, Apr 7, 2015 at 12:55 PM, Terry Reedy <tjreedy@udel.edu> wrote:
>>>> On 4/7/2015 1:44 PM, Ian Kelly wrote:
>>>>
>>>>>>>> def to_base(number, base):
>>>>>
>>>>> ...     digits = []
>>>>> ...     while number > 0:
>>>>> ...         digits.append(number % base)
>>>>> ...         number //= base
>>>>> ...     return digits or [0]
>>>>> ...
>>>>>>>>
>>>>>>>>
>>>>>>>> to_base(2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490,
>>>>>>>> 429496729)
>>>>>
>>>>> [27626525, 286159541, 134919277, 305018215, 329341598, 48181777,
>>>>> 79384857, 112868646, 221068759, 70871527, 416507001, 31]
>>>>> About 15 microseconds.
>>>>
>>>>
>>>> % and probably // call divmod internally and toss one of the results.
>>>> Slightly faster (5.7 versus 6.1 microseconds on my machine) is
>>>
>>> Not on my box.
>>>
>>> $ python3 -m timeit -s "n = 1000000; x = 42" "n % x; n // x"
>>> 10000000 loops, best of 3: 0.105 usec per loop
>>> $ python3 -m timeit -s "n = 1000000; x = 42" "divmod(n,x)"
>>> 10000000 loops, best of 3: 0.124 usec per loop
>>
>> I get similar results, but the times switch over when n is large enough
>> to become a bignum.
>>
>> --
>> Ben.
>
> I am not sure you guys realised, that althoug the size of the factors to muliply expands according to base^(exp+1) for each digitplace the number of comparissons needed to reach the digit place (multiple of base^exp+1) is constant with my approach/method.
>

Baloney.

But even if it were true, a search is slower than a divide.



-- 
DaveA