Re: Best search algorithm to find condition within a range

References	(7 earlier) <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	2015-04-08 08:35 -0600
Subject	Re: Best search algorithm to find condition within a range
Newsgroups	comp.lang.python
Message-ID	<mailman.141.1428503794.12925.python-list@python.org> (permalink)

Show all headers | View raw

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) is 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 exponential.

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.

Thread

Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 02:44 -0700
  Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 09:29 -0400
    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:10 -0700
      Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 10:26 -0400
      Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:34 +1000
    Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-07 14:29 +0000
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:36 -0700
        Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:49 +1000
          Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-07 15:05 +0000
            Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:23 -0400
            Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 01:37 +1000
            Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 17:02 +0100
        Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 16:00 +0100
          Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:43 -0700
            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:51 +1000
              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:46 +1000
        Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:04 -0400
        Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 09:06 -0600
          Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:47 -0700
            Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:06 -0400
            Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:49 +1200
        Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:36 +1000
          Re: Best search algorithm to find condition within a range Cameron Simpson <cs@zip.com.au> - 2015-04-08 08:51 +1000
        Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:01 -0400
        Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-18 18:08 +0000
          Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-19 23:02 +1000
            Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-19 17:56 +0300
              Re: Best search algorithm to find condition within a range Gene Heskett <gheskett@wdtv.com> - 2015-04-19 11:17 -0400
              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-20 12:53 +1000
            Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-19 14:52 -0400
            Re: Best search algorithm to find condition within a range Paul Rubin <no.email@nospam.invalid> - 2015-04-19 13:44 -0700
            Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-25 14:49 +0000
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 09:18 -0700
  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 08:32 -0600
    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:40 -0700
      Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 12:33 -0400
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 10:07 -0700
          Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 11:44 -0600
            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:38 +1000
              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 11:18 +1000
                Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:37 -0600
              Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:19 -0700
                Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 13:39 +0000
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 07:56 -0700
                Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 17:33 +0000
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:28 -0700
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:36 -0700
                Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:28 +0100
                Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:29 +0100
          Re: Best search algorithm to find condition within a range Terry Reedy <tjreedy@udel.edu> - 2015-04-07 14:55 -0400
          Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:19 -0600
            Re: Best search algorithm to find condition within a range Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 20:27 +0100
              Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 15:35 -0700
                Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 20:38 -0400
                Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:35 -0600
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:28 -0700
                Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:35 -0600
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:35 -0700
          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 05:25 +1000
          Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:28 -0600
          Re: Best search algorithm to find condition within a range Serhiy Storchaka <storchaka@gmail.com> - 2015-04-07 23:57 +0300
          Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:18 +1000
            Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-08 07:31 +0300
      Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 14:15 -0600
      Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-07 21:42 +0100
    Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:55 +1000
      Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:30 -0600
  Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:57 +1000
    Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:59 +1200
      Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 02:39 +0100
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:12 -0700
    Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:49 +1000
      Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-09 12:32 +1000
        Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-09 12:39 +1000
          Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 23:14 -0700
    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 22:50 -0700
    Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:07 -0700
      Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:18 -0700
        Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-08 17:27 +0000
          Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 10:50 -0700
    Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-08 22:22 +0100
      Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 01:06 +0300
        Re: Best search algorithm to find condition within a range Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-08 17:01 -0700
        Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-09 10:19 +0100
          Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 13:00 +0300
            Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 13:57 +0200
              Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 15:45 +0300
                Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 14:56 +0200
                Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-09 09:19 -0400
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:33 +0300
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:49 +0300
                Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 15:57 +0200
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 00:08 +1000
                Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 16:53 +0200
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:02 +1000
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:12 -0700
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:21 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:36 +1000
                Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-09 17:40 +0100
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 07:54 -0700
                Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 09:03 -0600
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:21 -0700
                Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 10:23 -0600
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:11 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:34 +1000
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 02:15 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:36 +1000
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:49 +1000
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 19:25 +0300
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:43 +1000
                Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 16:53 +0000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:00 +1000
                Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 17:44 +0000
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:41 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 04:07 +1000
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:14 +0300
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:11 +0300
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 20:43 +0300
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:35 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:56 +1000
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 23:18 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 23:41 +1000
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:15 +0300
                Re: Best search algorithm to find condition within a range Rustom Mody <rustompmody@gmail.com> - 2015-04-10 09:39 -0700
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:28 +0300

csiph-web