Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #88572 > unrolled thread

Best search algorithm to find condition within a range

Back to article view | Back to comp.lang.python

Contents

  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

Page 3 of 7 — ← Prev page 1 2 [3] 4 5 6 7  Next page →

#88670

On Tue, Apr 7, 2015 at 7:18 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Wed, 8 Apr 2015 10:38 am, Steven D'Aprano wrote:
>
>> On Wed, 8 Apr 2015 03:44 am, Ian Kelly wrote:
>>
>>>>>>
>>
> to_base(2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490,
>>>>>> 429496729)
>>> [27626525, 286159541, 134919277, 305018215, 329341598, 48181777,
>>> 79384857, 112868646, 221068759, 70871527, 416507001, 31]
>>
>>
>> They're not exactly *digits* though, are they?
>
> Oh, I forgot... I think this is why Python long ints effectively uses a base
> 256 internal storage. If memory serves me correctly, internally a long int
> is stored as an array of bytes using digits:
>
> \x0 \x1 \x2 ... \xFF
>
> (in decimal, 0 to 255). Each digit takes a single byte, so it's nicely
> compact, and Python includes a bunch of fast algorithms for doing
> arithmetic on these.

According to the comments in longintrepr.h, Python uses either 15- or
30-bit digits, determined at configure time.

[toc] | [prev] | [next] | [standalone]

#88653

Den onsdag 8 april 2015 kl. 02:38:57 UTC+2 skrev Steven D'Aprano:
> On Wed, 8 Apr 2015 03:44 am, Ian Kelly wrote:
> 
> >>>>
> to_base(2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490,
> >>>> 429496729)
> > [27626525, 286159541, 134919277, 305018215, 329341598, 48181777,
> > 79384857, 112868646, 221068759, 70871527, 416507001, 31]
> 
> 
> They're not exactly *digits* though, are they? Without an easy to use set of
> 429496729 different symbols, the whole exercise is rather pointless. It's
> not more compact: 97 decimal digits, versus 121 characters in the list
> representation. 110 if you strip out the spaces between items. It's
> certainly not more memory efficient: the long int 293...490 takes 56 bytes,
> compared to 80 bytes for just the list, not including the memory used by
> its 12 int items. (Results may vary in other versions of Python.) You can't
> do arithmetic on it faster than Python's built-ins.
> 
> Besides, it isn't clear to me whether Jonas wants to convert decimal
> 293...490 *into* base 429496729 as you have done, or *base 429496729*
> 293...490 into decimal.
> 
> 
> 
> -- 
> Steven

Well Steven you just draw a line under connecting them all, and now you are allowed to call whatever combination you write down a single digit.

And you have just created 429496729 unique symbols ;), in a pencil stroke.
I know at least one intergalactic poster that will be impressed ;)

[toc] | [prev] | [next] | [standalone]

#88665

On Tue, 07 Apr 2015 23:19:49 -0700, jonas.thornvall wrote:

> And you have just created 429496729 unique symbols ;), in a pencil
> stroke.

No.  You did that, when you said base 429496729.  Representing the 
symbols in a computer is no problem, any Python long int can do that.  To 
display the symbols, you can use PIL to make up glyphs out of coloured 
pixels 864x864.  You can keep your glyphs in GIFs.  Where you keep them 
is up to you.  Keeping them in Tumbolia and computing them out as 
required will work well.

[toc] | [prev] | [next] | [standalone]

#88671

Den onsdag 8 april 2015 kl. 15:40:46 UTC+2 skrev Mel Wilson:
> On Tue, 07 Apr 2015 23:19:49 -0700, jonas.thornvall wrote:
> 
> > And you have just created 429496729 unique symbols ;), in a pencil
> > stroke.
> 
> No.  You did that, when you said base 429496729.  Representing the 
> symbols in a computer is no problem, any Python long int can do that.  To 
> display the symbols, you can use PIL to make up glyphs out of coloured 
> pixels 864x864.  You can keep your glyphs in GIFs.  Where you keep them 
> is up to you.  Keeping them in Tumbolia and computing them out as 
> required will work well.

Well many interpretate a numeral digit as a single unique symbol representing a number written out in one pensttroke. I just pointed out that using handwriting or underscore a compination can be considered a numerical digit in itself.

There is no need for inventing a new set of characters representing 32-bit numbers. You will not be able to learn them by heart anyway, unless they build on a interpretation system binaries, decimals. 

Of course you could rather easily create a new set building on Points and lines and their interpretation.

Well just saying the Babylonians and Sumerians already did this, even the old greek had some sort of system with 120 unique digits. But what would be the need for such system when we so easy can create a unique permutation representing any number, using our 10 digits.

[toc] | [prev] | [next] | [standalone]

#88678

On Wed, 08 Apr 2015 07:56:05 -0700, jonas.thornvall wrote:

> There is no need for inventing a new set of characters representing
> 32-bit numbers. You will not be able to learn them by heart anyway,
> unless they build on a interpretation system binaries, decimals.

See Jorge Luis Borges, _Funes the Memorious_.  Gotta keep up with the 
literature.

[toc] | [prev] | [next] | [standalone]

#88681

Den onsdag 8 april 2015 kl. 19:34:39 UTC+2 skrev Mel Wilson:
> On Wed, 08 Apr 2015 07:56:05 -0700, jonas.thornvall wrote:
> 
> > There is no need for inventing a new set of characters representing
> > 32-bit numbers. You will not be able to learn them by heart anyway,
> > unless they build on a interpretation system binaries, decimals.
> 
> See Jorge Luis Borges, _Funes the Memorious_.  Gotta keep up with the 
> literature.

One thing is true though the bigger the chunks the less operations doing add.
So arithmetic may turn out to be obsolete and replaced with search in lookuptables.

[toc] | [prev] | [next] | [standalone]

#88682

Den onsdag 8 april 2015 kl. 21:28:34 UTC+2 skrev jonas.t...@gmail.com:
> Den onsdag 8 april 2015 kl. 19:34:39 UTC+2 skrev Mel Wilson:
> > On Wed, 08 Apr 2015 07:56:05 -0700, jonas.thornvall wrote:
> > 
> > > There is no need for inventing a new set of characters representing
> > > 32-bit numbers. You will not be able to learn them by heart anyway,
> > > unless they build on a interpretation system binaries, decimals.
> > 
> > See Jorge Luis Borges, _Funes the Memorious_.  Gotta keep up with the 
> > literature.
> 
> One thing is true though the bigger the chunks the less operations doing add.
> So arithmetic may turn out to be obsolete and replaced with search in lookuptables.

When doing by hand and working within the digitspace of a single decimal digit like 3+4 the operation is implicit. You do not really add anything you use a lookup table.

But if you take an expression like 193+169, most people perform the arithmetic. Unless they do not happen to be your favourit numbers and you learnt the sum by heart.

Top down or bottom up is basicly the choices.

[toc] | [prev] | [next] | [standalone]

#88683

On 08/04/2015 20:36, jonas.thornvall@gmail.com wrote:
> Den onsdag 8 april 2015 kl. 21:28:34 UTC+2 skrev jonas.t...@gmail.com:
>> Den onsdag 8 april 2015 kl. 19:34:39 UTC+2 skrev Mel Wilson:
>>> On Wed, 08 Apr 2015 07:56:05 -0700, jonas.thornvall wrote:
>>>
>>>> There is no need for inventing a new set of characters representing
>>>> 32-bit numbers. You will not be able to learn them by heart anyway,
>>>> unless they build on a interpretation system binaries, decimals.
>>>
>>> See Jorge Luis Borges, _Funes the Memorious_.  Gotta keep up with the
>>> literature.
>>
>> One thing is true though the bigger the chunks the less operations doing add.
>> So arithmetic may turn out to be obsolete and replaced with search in lookuptables.
>
> When doing by hand and working within the digitspace of a single decimal digit like 3+4 the operation is implicit. You do not really add anything you use a lookup table.
>
> But if you take an expression like 193+169, most people perform the arithmetic. Unless they do not happen to be your favourit numbers and you learnt the sum by heart.
>
> Top down or bottom up is basicly the choices.
>

Are you trolling or do you simply not have the faintest idea?

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#88684

On 08/04/2015 20:28, jonas.thornvall@gmail.com wrote:
> Den onsdag 8 april 2015 kl. 19:34:39 UTC+2 skrev Mel Wilson:
>> On Wed, 08 Apr 2015 07:56:05 -0700, jonas.thornvall wrote:
>>
>>> There is no need for inventing a new set of characters representing
>>> 32-bit numbers. You will not be able to learn them by heart anyway,
>>> unless they build on a interpretation system binaries, decimals.
>>
>> See Jorge Luis Borges, _Funes the Memorious_.  Gotta keep up with the
>> literature.
>
> One thing is true though the bigger the chunks the less operations doing add.
> So arithmetic may turn out to be obsolete and replaced with search in lookuptables.
>

I suggest that you put this on python ideas before writing up a PEP, it 
seems like a sure fire winner to me.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#88610

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

def to_base_dm(number, base):
     digits = []
     while number > 0:
         number, rem = divmod(number, base)
         digits.append(rem)
     return digits or [0]

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#88611

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

[toc] | [prev] | [next] | [standalone]

#88613

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.

[toc] | [prev] | [next] | [standalone]

#88621

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.

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#88654

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?

[toc] | [prev] | [next] | [standalone]

#88655

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.

[toc] | [prev] | [next] | [standalone]

#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) 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.

[toc] | [prev] | [next] | [standalone]

#88656

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?

The for loop should be replaced with a version of binary search making comparisson instead of adding to digit. It will be alot faster with a base using 32-bits.

But the point is the number of operations is linear for each digitplace with my approach/method, you will multiply bigger numbers. But the numbers of comparissons and multiplications is linear over the digitspace.

[toc] | [prev] | [next] | [standalone]

#88612

On Wed, Apr 8, 2015 at 5:19 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>> % 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

Nor mine, though eliminating the global lookup cuts some of the time:

rosuav@sikorsky:~$ python3 -m timeit -s "n = 1000000; x = 42" "n % x; n // x"
1000000 loops, best of 3: 0.231 usec per loop
rosuav@sikorsky:~$ python3 -m timeit -s "n = 1000000; x = 42" "divmod(n,x)"
1000000 loops, best of 3: 0.305 usec per loop
rosuav@sikorsky:~$ python3 -m timeit -s "n = 1000000; x = 42; dm =
divmod" "dm(n,x)"
1000000 loops, best of 3: 0.26 usec per loop

But this is microbenchmarking. It's pretty pointless.

ChrisA

[toc] | [prev] | [next] | [standalone]

#88614

On Tue, Apr 7, 2015 at 1:19 PM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
> 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

But curiously, if I time the whole function, then my results mirror
yours; I wonder why that is. I don't see anything obvious in the
disassembly that would explain it.

[toc] | [prev] | [next] | [standalone]

Page 3 of 7 — ← Prev page 1 2 [3] 4 5 6 7  Next page →

Back to top | Article view | comp.lang.python

csiph-web