Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.101
X-Spam-Level: *
X-Spam-Evidence: '*H*': 0.80; '*S*': 0.00; 'algorithm': 0.04; 'binary': 0.07; 'linear': 0.09; '4:35': 0.16; 'expands': 0.16; 'iteration': 0.16; 'meanwhile,': 0.16; 'subject:search': 0.16; 'wrote:': 0.18; 'wed,': 0.18; 'replace': 0.24; 'guys': 0.24; 'suggested': 0.26; 'second': 0.26; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; "doesn't": 0.30; 'operations,': 0.30; 'message- id:@mail.gmail.com': 0.30; 'largest': 0.30; 'comparison': 0.31; 'constant': 0.31; 'division': 0.31; 'operations.': 0.31; 'operations': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'words,': 0.36; 'method': 0.36; 'should': 0.36; 'needed': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'does': 0.39; 'sure': 0.39; 'to:addr:python.org': 0.39; 'either': 0.39; 'according': 0.40; 'how': 0.40; 'affect': 0.61; 'first': 0.61; 'reach': 0.63; 'account': 0.65; 'overall': 0.69; 'search,': 0.74; 'analysis': 0.75; '2015': 0.84; 'complexity': 0.84; 'subject:find': 0.84; 'subject:Best': 0.91; 'factors': 0.97
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=ZDr2CKsSVwxCtMSbpuvOLZJ21HeYzeTqrRyPPYNrJPs=; b=zNstBbsH8wnZsd2s/Ce/pceoJyxWSRsfLoTPY31JnDqWnav646H1uynzeJna7azv47 vwr4zNiuVdlKX2+iJl3OvSYWdaaeDRPsw6Q8twmkmle5lJn8qyBKqRiNoCbiIIuBbrXq 6+wc3gD/wDLppvIw0sbnd0/OcsiGe7b7fRcZbVB0sG1YWuWUtYV4eLghAcUU2fUnrJes blp9s9fAxqVAw5nA4UnnJlZIjDmMZXLlyZnFe/aWS1IxqeVgqUJOZvR6++lEZjEynUF4 /+oJmOGCTxBUwsTikIjvClYP+u+nJYaSRUfMg6YXh94XybXnfrv1wiajTohtVL5UimsW yUbg==
X-Received: by 10.107.29.21 with SMTP id d21mr39584726iod.11.1428503792657; Wed, 08 Apr 2015 07:36:32 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <ad4d7ca1-56b6-4be1-bd55-fc6a4cbb65aa@googlegroups.com>
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> <mailman.134.1428477364.12925.python-list@python.org> <ad4d7ca1-56b6-4be1-bd55-fc6a4cbb65aa@googlegroups.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Wed, 8 Apr 2015 08:35:52 -0600
Subject: Re: Best search algorithm to find condition within a range
To: Python <python-list@python.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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.141.1428503794.12925.python-list@python.org>
Lines: 27
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1428503794 news.xs4all.nl 2896 [2001:888:2000:d::a6]:51091
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:88668

On Wed, Apr 8, 2015 at 1:28 AM,  <jonas.thornvall@gmail.com> wrote:
> Den onsdag 8 april 2015 kl. 09:16:24 UTC+2 skrev Ian:
>> On Tue, Apr 7, 2015 at 4:35 PM,  <jonas.thornvall@gmail.com> wrote:
>> > 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) i=
s constant with my approach/method.
>>
>> No it isn't. You do one comparison on every iteration of your while
>> loop, and you do one iteration for every digit. How is that constant?
>
> Ok the number of comparissons is linear for each digitplace not exponenti=
al.

In other words, the first part of your algorithm where you find the
largest digit place takes O(log n) operations. But the second part
where you do a search for each digit takes O(b * log n) operations, so
the overall number of operations is O(b * log n). If you replace the
linear search with a binary search, that's still O(log b * log n).

Meanwhile, the division method that I and others have repeatedly
suggested does only one comparison and one division per digit, which
is just O(log n).

Note that this analysis doesn't take into account the complexity of
the individual arithmetic operations, but that should affect either
algorithm equally.