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 4 of 7 — ← Prev page 1 2 3 [4] 5 6 7  Next page →

#88618

On 07.04.15 22:28, Ian Kelly wrote:
> 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:
>>> % 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.

Try large numbers.

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

#88635

On Wed, 8 Apr 2015 03:07 am, jonas.thornvall@gmail.com wrote:

> So you can tell me the first (higest) digit of the integer
>
2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490


First digit:
py> s
= '2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490'
py> s[0]
'2'


Highest digit:

py> max(s)
'9'


> Using base 429496729?

That makes no sense. With base 429496729 you need to have 429496729
different digits. Of course it is possible that, just by chance, you end up
with something that only includes the digits 0 through 9. Of course that is
possible, just like there are decimal numbers which only use digits 0
through 1, e.g. 10001.

If you want to go the other way, and convert s FROM decimal INTO base
429496729, you need to tell us what digits to use. You need 429496729
different digits.


> How long time did it take to find it?

A tiny fraction of a second.

py> from timeit import Timer
py> setup = "s
= '2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490'"
py> t = Timer("s[0]; max(s)", setup)
py> min(t.repeat())
7.158415079116821


That's just over 7 seconds to calculate both the first and the highest digit
one million times, or about 7 microseconds each time.




-- 
Steven

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

#88648

Steven D'Aprano <steve+comp.lang.python@pearwood.info>:

> On Wed, 8 Apr 2015 03:07 am, jonas.thornvall@gmail.com wrote:
>> Using base 429496729?
>
> That makes no sense. With base 429496729 you need to have 429496729
> different digits.

You can use integers as digits. We already do that when we express times
and angles in base-60. I think even the Babylonians might have used such
structured digits.

>>> x = 2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490
>>> while x >= 429496729: x //= 429496729
... 
>>> x
31


Marko

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

#88616

On Tue, Apr 7, 2015 at 9:40 AM,  <jonas.thornvall@gmail.com> wrote:
> Well of course you use same principles like a binary search setting min and max, closing in on the digit. In this case the searched numbers  > base^exp  and number< base^exp+1.
>
> But since the search is within large bases upto 32-bit space, so base 4294967295 is the biggest allowed. I need to find the nearest less exp in base for each (lets call them pseudo digits). But as you see there it will take time to add them up. So better doing a binary search, you know min-max half (iteration). You can do the same for a random oracle min max within range, and if the number of tries in general over 22 i think a random oracle do it better than a binary search.

Okay, so you're talking about doing a binary search but picking the
partition point randomly instead of evenly?

> It was a long time since i did this, but i do know there is a threshold where searching min max with the oracle will be faster than the binary search.

I don't know where you got this idea from, but it's fiction. If you
split the space in half, then you are always reducing the amount of
work remaining by a factor of 2, and the total work is O(log n). If
you do an uneven split, then while you will sometimes make a good
partition and reduce the amount of work by more than a factor of two,
more often the target will be in the larger subspace and you will have
reduced the amount of work by less than a factor of two. In the worst
case of this, you only remove one element from the search space at a
time and end up with a linear search.

As a demonstration of this, here's a function which does a binary
search for a number in a range and returns the number of partitions it
had to perform to find the number:

>>> def binsearch(n, min, max):
...   if min == max: return 0
...   med = (max + min) // 2
...   if n <= med:
...     return 1 + binsearch(n, min, med)
...   else:
...     return 1 + binsearch(n, med+1, max)
...

And here's the average number of partitions needed to find a number in
various ranges:

>>> sum(binsearch(i, 1, n) for i in range(1, n+1)) / n
16.68928
>>> n = 1000000
>>> sum(binsearch(i, 1, n) for i in range(1, n+1)) / n
19.951424
>>> n = 10000000
>>> sum(binsearch(i, 1, n) for i in range(1, n+1)) / n
23.3222784

Now let's try a variant function that splits the range at one third
instead of evenly:

>>> def trisearch(n, min, max):
...     if min == max: return 0
...     tern = (min + min + max) // 3
...     if n <= tern:
...         return 1 + trisearch(n, min, tern)
...     else:
...         return 1 + trisearch(n, tern+1, max)
...
>>> n = 100000
>>> sum(trisearch(i, 1, n) for i in range(1, n+1)) / n
17.88387
>>> n = 1000000
>>> sum(trisearch(i, 1, n) for i in range(1, n+1)) / n
21.502276
>>> n = 10000000
>>> sum(trisearch(i, 1, n) for i in range(1, n+1)) / n
25.1157592

The ternary version invariably takes more partitions on average to
find the goal number. Now let's try a third variant that partitions
the range randomly:

>>> def randsearch(n, min, max):
...     if min == max: return 0
...     part = randrange(min, max)
...     if n <= part:
...         return 1 + randsearch(n, min, part)
...     else:
...         return 1 + randsearch(n, part+1, max)
...
>>> n = 100000
>>> sum(randsearch(i, 1, n) for i in range(1, n+1)) / n
22.17863
>>> n = 1000000
>>> sum(randsearch(i, 1, n) for i in range(1, n+1)) / n
26.78371
>>> n = 10000000
>>> sum(randsearch(i, 1, n) for i in range(1, n+1)) / n
31.3916557

As you can see, this one does a lot worse on average, and at n=1e6
it's already performing worse than either of the previous versions did
at n=1e7.  I'm not even going to try this for n=1e8 because it would
take too long to run.

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

#88617

On 07/04/2015 17:33, Dave Angel wrote:
> On 04/07/2015 11:40 AM, jonas.thornvall@gmail.com wrote:
>
> I haven't seen one line of Python from you yet, so perhaps you're just
> yanking our chain.
>

This wouldn't surprise me, he's the guy who refused point blank to 
modify his use of gg some 18 months ago.

-- 
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]

#88626

On Wed, 8 Apr 2015 12:32 am, Ian Kelly wrote:

> On average, a random Oracle with a search space of 1000000 will need
> 1000000 guesses.

Surely on average it will only take 500000 guesses?

Best case is that it gets lucky the first time (1 guess). Worst case is that
it guesses every wrong answer until there is only one answer it hasn't
given, which is right (1000000 guesses). I assume that the Oracle is smart
enough to never repeat a guess.


-- 
Steven

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

#88629

On Tue, Apr 7, 2015 at 4:55 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Wed, 8 Apr 2015 12:32 am, Ian Kelly wrote:
>
>> On average, a random Oracle with a search space of 1000000 will need
>> 1000000 guesses.
>
> Surely on average it will only take 500000 guesses?
>
> Best case is that it gets lucky the first time (1 guess). Worst case is that
> it guesses every wrong answer until there is only one answer it hasn't
> given, which is right (1000000 guesses). I assume that the Oracle is smart
> enough to never repeat a guess.

I didn't make that assumption. With replacement, the mean is 1000000,
per the binomial distribution.

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

#88627

On Tue, 7 Apr 2015 07:44 pm, 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.

What digits would you use for base one-million?

Base 2 uses 0 1.
Base 3 uses 0 1 2.
Base 10 uses 0 1 2 3 4 5 6 7 8 9.
Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.

Base one million uses what?

How would you write down 12345 in base one-million?



-- 
Steven

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

#88641

Steven D'Aprano wrote:

> What digits would you use for base one-million?

Interesting question. Unicode currently has about
75,000 CJK characters, so we would need to find about
12 more independently developed cultures with similar
writing systems to get enough characters. I suggest
revisiting the issue when interstellar travel and
exploration have been better developed.

-- 
Greg

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

#88644

On 08/04/2015 01:59, Gregory Ewing wrote:
> Steven D'Aprano wrote:
>
>> What digits would you use for base one-million?
>
> Interesting question. Unicode currently has about
> 75,000 CJK characters, so we would need to find about
> 12 more independently developed cultures with similar
> writing systems to get enough characters. I suggest
> revisiting the issue when interstellar travel and
> exploration have been better developed.
>

If it's available during PyCon can't we borrow the time machine? :)

-- 
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]

#88651

Den onsdag 8 april 2015 kl. 03:00:12 UTC+2 skrev Gregory Ewing:
> Steven D'Aprano wrote:
> 
> > What digits would you use for base one-million?
> 
> Interesting question. Unicode currently has about
> 75,000 CJK characters, so we would need to find about
> 12 more independently developed cultures with similar
> writing systems to get enough characters. I suggest
> revisiting the issue when interstellar travel and
> exploration have been better developed.
> 
> -- 
> Greg

No need Greg it is an easy task creating visual interpretable symbols from low to high using lines in a point/pixel space. I could create the set in a day.

And if i use colour space it is even easier.

The hard part is making the point space visible and interpretabel without calculation and holding remainders in head. 

But then again when numbers have more than 5 digitplaces people tend to interpretate them digitwise anyway.

10010 is interpretated as a single digit by brain.
7582560 people mostly interpretate as 7 m 582 000 and 560.

You can tell how people group and think about numbers by having them reading up a very long telephone number.

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

#88646

On Wed, Apr 8, 2015 at 8:57 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> On Tue, 7 Apr 2015 07:44 pm, 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.
>
> What digits would you use for base one-million?
>
> Base 2 uses 0 1.
> Base 3 uses 0 1 2.
> Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
>
> Base one million uses what?
>
> How would you write down 12345 in base one-million?

You could use base 1,114,112 fairly readily in any decent modern
programming language. That'll happily represent base one-million.

ChrisA

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

#88692

On Wed, 8 Apr 2015 11:49 am, Chris Angelico wrote:

> You could use base 1,114,112 fairly readily in any decent modern
> programming language. That'll happily represent base one-million.


Well, not really...

Here is the breakdown of Unicode code points by category, as of Python 3.3:

# Other
Cc: 65 (control characters)
Cf: 139 (format characters)
Cn: 864415 (unassigned)
Co: 137468 (private use)
Cs: 2048 (surrogates)

# Letters
Ll: 1751 (lowercase)
Lm: 237 (modifier)
Lo: 97553 (other)
Lt: 31 (titlecase)
Lu: 1441 (uppercase)

# Marks
Mc: 353 (spacing combining)
Me: 12 (enclosing)
Mn: 1280 (nonspacing)

# Numbers
Nd: 460 (decimal digit)
Nl: 224 (letter)
No: 464 (other)

# Punctuation
Pc: 10 (connector)
Pd: 23 (dash)
Pe: 71 (close)
Pf: 10 (final quote)
Pi: 12 (initial quote)
Po: 434 (other)
Ps: 72 (open)

# Symbols
Sc: 48 (currency)
Sk: 115 (modifier)
Sm: 952 (math)
So: 4404 (other)

# Separator
Zl: 1 (line)
Zs: 18 (paragraph)
Zp: 1 (space)


Clearly we shouldn't use control or format characters, surrogates,
separators, marks, etc. (At least, I hope it is clear why you don't want,
say, newlines, to be used as digits.) Punctuation is borderline, as are
symbols, since that won't interoperate well with anything else. How can you
parse number+number if the numbers themselves might contain + signs? I
wouldn't use unassigned code points, as that is all but guaranteed to lead
to future problems, but I might reluctantly allow private use. That leaves
us the following which *may* be suitable:

Co: 137468 (private use)
Ll: 1751 (lowercase)
Lo: 97553 (other)
Lt: 31 (titlecase)
Lu: 1441 (uppercase)
Nd: 460 (decimal digit)
Nl: 224 (letter)
No: 464 (other)
Sc: 48 (currency)
Sm: 952 (math)
So: 4404 (other)

which comes to a total of 244796, far short of a million. Add in the 632
punctuation marks if you like, and we're short.

There are other problems too:

- Confusables. Can you tell the difference between AΑА versus АAΑ, 
  or ВΒB versus BΒВ? Or even O versus 0?

- Lack of glyphs for the majority of those code points in most fonts. 
  Most numbers will look like a sequence of boxes.

- Difficulty of data entry.

- Some people's digits will not have the value that they expect,
  e.g. digit '1' might not have the numeric value 1, for at least
  all-but-ten of the 460 different decimal digits in use.

- Realistically, who is going to use this?

Even as an intellectual exercise, using huge bases for human input and
output isn't very useful. The idea of using massive implicit bases for the
internal implementation of BigNums is quite reasonable, but for human input
and output, it doesn't fly.



-- 
Steven

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

#88693

On Thu, Apr 9, 2015 at 12:32 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> - Realistically, who is going to use this?

Nobody. I was never suggesting it as a serious option; just threw it
out there as another dumb alternative :)

ChrisA

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

#88694

Le jeudi 9 avril 2015 04:40:14 UTC+2, Chris Angelico a écrit :

====

(Most) everything is doable.
There are even people who are recommending to
represent this decimal number 8364 with a 
sequence of these three decimal numbers 226 130 172
;-)
jmf

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

#88649

Den onsdag 8 april 2015 kl. 00:57:27 UTC+2 skrev Steven D'Aprano:
> On Tue, 7 Apr 2015 07:44 pm, 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.
> 
> What digits would you use for base one-million?
> 
> Base 2 uses 0 1.
> Base 3 uses 0 1 2.
> Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
> 
> Base one million uses what?
> 
> How would you write down 12345 in base one-million?
> 
> 
> 
> -- 
> Steven

Well digit places have to be comma separated i think i told you, in low bases we have unique digits so there is no problems write out numbers without separaation of digitplaces. But when the base is higher than the number of digits you have a choice to make. Either you invent a new numeral(number digit.

I think you realise that BB = 11,11

So your example would of course be ,12345

I hope you see A,B,C,D,E,F is only replacement for 10,11,12,13,14,15

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

#88650

Le mercredi 8 avril 2015 00:57:27 UTC+2, Steven D'Aprano a écrit :
> On Tue, 7 Apr 2015 07:44 pm, 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.
> 
> What digits would you use for base one-million?
> 
> Base 2 uses 0 1.
> Base 3 uses 0 1 2.
> Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
> 
> Base one million uses what?
> 
> How would you write down 12345 in base one-million?
> 

=========

Why should a "digit" contain a single/unique character?

Representation of the number 257 in base 256:

257 (base 10) --> FF 02 (base 256)

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

#88652

Le mercredi 8 avril 2015 08:08:04 UTC+2, wxjm...@gmail.com a écrit :
> Le mercredi 8 avril 2015 00:57:27 UTC+2, Steven D'Aprano a écrit :
> > On Tue, 7 Apr 2015 07:44 pm, 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.
> > 
> > What digits would you use for base one-million?
> > 
> > Base 2 uses 0 1.
> > Base 3 uses 0 1 2.
> > Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> > Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
> > 
> > Base one million uses what?
> > 
> > How would you write down 12345 in base one-million?
> > 
> 
> =========
> 
> Why should a "digit" contain a single/unique character?
> 
> Representation of the number 257 in base 256:
> 
> 257 (base 10) --> FF 02 (base 256)

======

Oops, typo, erratum

*** 257 (base 10) --> 01 01 (base 256) ***

instead of

> 257 (base 10) --> FF 02 (base 256)

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

#88677

On Tue, 07 Apr 2015 23:18:14 -0700, wxjmfauth wrote:

> Le mercredi 8 avril 2015 08:08:04 UTC+2, wxjm...@gmail.com a écrit :
>> Le mercredi 8 avril 2015 00:57:27 UTC+2, Steven D'Aprano a écrit :
>> > On Tue, 7 Apr 2015 07:44 pm, 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.
>> > 
>> > What digits would you use for base one-million?
>> > 
>> > Base 2 uses 0 1.
>> > Base 3 uses 0 1 2.
>> > Base 10 uses 0 1 2 3 4 5 6 7 8 9.
>> > Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
>> > 
>> > Base one million uses what?
>> > 
>> > How would you write down 12345 in base one-million?
>> > 
>> > 
>> =========
>> 
>> Why should a "digit" contain a single/unique character?
>> 
>> Representation of the number 257 in base 256:
>> 
>> 257 (base 10) --> FF 02 (base 256)
> 
> ======
> 
> Oops, typo, erratum
> 
> *** 257 (base 10) --> 01 01 (base 256) ***

Bzzzzttttt. Wrong.

0101(256) is 0 * 256^3 + 1 * 256^2 + 0 * 256^1 + 1 * 256^0

= 65537

The whole point of "base x" is that any number in the range 0 .. x^1 is 
represented with a single characterisation, otherwise you don't have 
"base x".

This is the same fundamental issue as the OP is failing to understand - 
base x notation is a human readability and representation thing, not an 
inherent feature of numbers.

-- 
Denis McMahon, denismfmcmahon@gmail.com

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

#88679

Le mercredi 8 avril 2015 19:28:34 UTC+2, Denis McMahon a écrit :
> On Tue, 07 Apr 2015 23:18:14 -0700, wxjmfauth wrote:
> 
> > Le mercredi 8 avril 2015 08:08:04 UTC+2, wxjm...@gmail.com a écrit :
> >> Le mercredi 8 avril 2015 00:57:27 UTC+2, Steven D'Aprano a écrit :
> >> > On Tue, 7 Apr 2015 07:44 pm, 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.
> >> > 
> >> > What digits would you use for base one-million?
> >> > 
> >> > Base 2 uses 0 1.
> >> > Base 3 uses 0 1 2.
> >> > Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> >> > Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
> >> > 
> >> > Base one million uses what?
> >> > 
> >> > How would you write down 12345 in base one-million?
> >> > 
> >> > 
> >> =========
> >> 
> >> Why should a "digit" contain a single/unique character?
> >> 
> >> Representation of the number 257 in base 256:
> >> 
> >> 257 (base 10) --> FF 02 (base 256)
> > 
> > ======
> > 
> > Oops, typo, erratum
> > 
> > *** 257 (base 10) --> 01 01 (base 256) ***
> 
> Bzzzzttttt. Wrong.
> 
> 0101(256) is 0 * 256^3 + 1 * 256^2 + 0 * 256^1 + 1 * 256^0
> 
> = 65537
> 
> The whole point of "base x" is that any number in the range 0 .. x^1 is 
> represented with a single characterisation, otherwise you don't have 
> "base x".
> 
> This is the same fundamental issue as the OP is failing to understand - 
> base x notation is a human readability and representation thing, not an 
> inherent feature of numbers.
> 
> -- 
> Denis McMahon, denismfmcmahon@gmail.com

====

No, not really.

01 01 in a *decimal* representation, a set of 10 characters.

01 01 means (should be understood as)  1 x 256**1 + 1 X 256**0 = 257

In other words, the usual "human" set of characters 0..9 with a
base != 10.

The idea is just to show, one can work with a "limited" set of chars
and it's no necessary to have the cardinal of a set of characters
corresponding to the base.

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

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

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

csiph-web