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

#88639

jonas.thornvall@gmail.com wrote:
> No i don't i say the operations assume base ten other wise INT A=7,B=4
> Calculate C=A+B would not yield 11 as an answer.

The answer, when converted to base 10, will still be
11 regardless of the base in which the arithmetic is
performed.

For example, in base 2:

A = 0111   (decimal 7)
B = 0100   (decimal 4)
     ----
C = 1011

Now convert binary 1011 to decimal and see what
you get.

-- 
Greg

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

#88622

On Wed, 8 Apr 2015 12:36 am, jonas.thornvall@gmail.com wrote:

> Bullshit declare two integers in any language one 7 and one 4 and then
> write x=7+4; if you find a programming language where that does not yield
> 11 tell me.

In Forth, you can set the base to any arbitrary integer (within reason).

steve@orac:/home/steve$ gforth
Gforth 0.7.0, Copyright (C) 1995-2008 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
7 4 + . 11  ok
hex  ok
7 4 + . B  ok
7 4 +   ok
2 base !  ok
. 1011  ok


The dot . prints the value on the top of the stack. In Python terms, the
closest equivalent would be:

print (7 + 4)  # prints 11 by default
# set the base to hex
print (7 + 4)  # prints B
x = 7 + 4
# set the base to 2
print (x)  # prints 1011


except that Python doesn't allow you to change the base used by ints, it is
always decimal.

In Forth, however, setting the base doesn't just change the *display* of
integers, it also changes how you enter them:

3
:7: Undefined word
>>>3<<<
Backtrace:
$B7252EDC throw
$B725F638 no.extensions
$B7253054 interpreter-notfound1
  ok


So in base 2 mode, it doesn't recognise 3 as a number. If I want to enter
three, I have to enter it in binary:

11  ok
decimal  ok
. 3  ok



> Integers are internally assumed to be base 10 otherwise you could not
> calculate without giving the base.


That is *absolutely not* the case in Forth. It's not even the case in
Python: integers are actually stored in either binary (base 2) or some very
large base, I think equivalent to base 256, depending on the version of
Python and the size of the int. 


> All operations on integers addition, subtraction, multiplication and
> division assume base 10.

That's just ridiculous.

In Python, like most other languages, the only thing which assumes base 10
is entry and printing of integers.




-- 
Steven

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

#88624

On 08Apr2015 08:36, Steven D'Aprano <steve+comp.lang.python@pearwood.info> wrote:
>On Wed, 8 Apr 2015 12:36 am, jonas.thornvall@gmail.com wrote:
>> Bullshit declare two integers in any language one 7 and one 4 and then
>> write x=7+4; if you find a programming language where that does not yield
>> 11 tell me.
>
>In Forth, you can set the base to any arbitrary integer (within reason).
[...snip...]

In dc also (UNIX's reverse polish arbitrary precision "decimal calculator").  
You can set the input and output representation bases, and proceed without 
leading base indicators.

Cheers,
Cameron Simpson <cs@zip.com.au>

Hofstadter's Law: It always takes longer than you expect, even when you take
into account Hofstadter's Law.
- Douglas Hosfstadter, Godel, Escher, Bach: an Eternal Golden Braid

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

#88633

On Tue, 07 Apr 2015 11:04:37 -0400, Dave Angel <davea@davea.name> declaimed
the following:

>
>There have been machines where that was true, but I haven't worked on 
>such for about 30 years.  On any machines I've programmed lately, the 
>arithmetic is done in binary by default, and only converted to decimal 
>for printing.
>
	And then there is...
http://en.wikipedia.org/wiki/Bi-quinary_coded_decimal
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

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

#89131

In article <fd544688-5e9c-418e-9ca9-11b9bcb83186@googlegroups.com>,
 <jonas.thornvall@gmail.com> wrote:
>Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
>> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
>>
>> > On 04/07/2015 05:44 AM, 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.
>>
>> > How do you know the baseconversion is the bottleneck, if you haven't
>> > written any Python code yet?
>>
>> He doesn't. He doesn't comprehend that as far as a computer is concerned
>> an integer has no specific 'base', it's only when presented in a form for
>> humans to read that it gets base information added in the representation.
>>
>> He's making these and other similar errors in the javascript groups too.
>>
>> I suspect he's one of those people that spends his time thinking up
>> elaborate solutions that he has no idea how to implement as a response to
>> dreamt up non existent problems.
>>
>> --
>> Denis McMahon, denismfmcmahon@gmail.com
>
>Bullshit declare two integers in any language one 7 and one 4 and then
>write x=7+4; if you find a programming language where that does not
>yield 11 tell me.
>
>Integers are internally assumed to be base 10 otherwise you could not
>calculate without giving the base.
>
>All operations on integers addition, subtraction, multiplication and
>division assume base 10.

Fire up a lowlevel interpreter like Forth. (e.g. gforth)

7 CONSTANT A    4 CONSTANT B
A B + PAD !

PAD now contains the sum of A and B.

Now inspect the actual computer memory:

PAD 100 DUMP

You will see the bytes, represented in base 16, but PAD
just contains 11

PAD ?

11 OK

In forth you can change the number base. That doesn't affect PAD
but the output is different

HEX
PAD ?

B OK
DECIMAL

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#89148

On Sun, 19 Apr 2015 04:08 am, Albert van der Horst wrote:

> Fire up a lowlevel interpreter like Forth. (e.g. gforth)

Yay! I'm not the only one who uses or likes Forth!

Have you tried Factor? I'm wondering if it is worth looking at, as a more
modern and less low-level version of Forth.


-- 
Steven

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

#89156

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

> Yay! I'm not the only one who uses or likes Forth!

Out of interest, is Forth different from PostScript? I have done some
small-time programming in PostScript but nothing in Forth.


Marko

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

#89158

On Sunday 19 April 2015 10:56:49 Marko Rauhamaa wrote:
> Steven D'Aprano <steve+comp.lang.python@pearwood.info>:
> > Yay! I'm not the only one who uses or likes Forth!
>
> Out of interest, is Forth different from PostScript? I have done some
> small-time programming in PostScript but nothing in Forth.
>
>
> Marko

No relationship detectable Marko.

Cheers, Gene Heskett
-- 
"There are four boxes to be used in defense of liberty:
 soap, ballot, jury, and ammo. Please use in that order."
-Ed Howdershelt (Author)
Genes Web page <http://geneslinuxbox.net:6309/gene>

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

#89191

On Mon, 20 Apr 2015 12:56 am, Marko Rauhamaa wrote:

> Steven D'Aprano <steve+comp.lang.python@pearwood.info>:
> 
>> Yay! I'm not the only one who uses or likes Forth!
> 
> Out of interest, is Forth different from PostScript? I have done some
> small-time programming in PostScript but nothing in Forth.


Both Forth and PostScript are concatenative stack-based languages with a
reverse Polish notation syntax. Other than that, I imagine that they are
very different. I have zero experience with Postscript and only a little
with Forth (enough to know that I like it more in principle than practice),
so the following is mostly inferred rather than from experience.

Postscript is interpreted, with strong dynamic typing, Lisp-like data
structures, and garbage collection. It is designed for generating vector
images. It can be used for general purpose programming, but that's not its
strong suit.

Technically, Forth is also interpreted, but that may be misleading if you
think of it in traditional terms. The runtime interpreter (virtual machine)
may be as simple as a handful of commands to follow a linked list of
subroutines calling each one in turn.

One of the design principles of Forth is that compiled code is extremely
compact and fast, which makes it ideal for running at a very low level on
constrained hardware.

Older Forths are untyped. All data is a machine word on a stack. Arrays and
equivalent are implemented by dropping the address of the array on the
stack and then using redirection to access the array, which makes it rather
like C.

Unlike C, Forth puts the book-keeping related to function calls on a
separate stack, which simplifies the runtime significantly.

Newer Forths added a third stack for floating point values.


The two classic Forth books back in the 80s were Starting Forth and Thinking
Forth, by Leo Brodie:

http://www.forth.com/starting-forth/

http://thinking-forth.sourceforge.net/


They're a bit old, and the Starting Forth book in particular has a level of
whimsy which feels a bit odd to many people, but you can browse them to get
a feel for the language.



-- 
Steven

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

#89169

On 04/19/2015 09:02 AM, Steven D'Aprano wrote:
> On Sun, 19 Apr 2015 04:08 am, Albert van der Horst wrote:
>
>> Fire up a lowlevel interpreter like Forth. (e.g. gforth)
>
> Yay! I'm not the only one who uses or likes Forth!
>
> Have you tried Factor? I'm wondering if it is worth looking at, as a more
> modern and less low-level version of Forth.
>

I also like Forth (since 83), but haven't done much in the last decade.

I was newsletter editor for our local FIG for many years.

I have met and debated with Elizabeth Rather, and been a "third hand" 
for Chuck Moore when he was re-soldering wires on his prototype Forth board.

You can see my name in the X3J14 standard:
    https://www.taygeta.com/forth/dpans1.htm#x3j14.membership


I'd be interested in a "more modern" Forth, but naturally, as a member 
of band of rugged individualists, I wonder if it can possibly satisfy 
more than one of us.

<googling...>
http://factorcode.org/

That site is my first time I recall seeing "concatenative" as a type of 
language.  Interesting way of thinking of it.  I just call it RPN, and 
relate it to the original HP35 calculator ($400, in about 1972).

 From the overview, it looks like they're at least aiming at what I 
envisioned as the next Forth I wanted to use.  Instead of putting ints 
and addresses on the stack, you put refs to objects, in the Python 
sense.  Those objects are also gc'ed.  I don't know yet whether 
everything is an object, or whether (like Java), you have boxed and 
unboxed thingies.

Sounds interesting, and well worth investigating.  thanks for pointing 
it out.

-- 
DaveA

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

#89174

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
> Have you tried Factor? I'm wondering if it is worth looking at, as a
> more modern and less low-level version of Forth.

Factor is basically Lisp with Forth-based syntax, from what I can tell.
Tagged objects, garbage collection, etc.

Forth is traditionally a self-hosted low level language with a
minimalistic spirit.  It uses native machine words containing numbers or
machine pointers like assembly language does, with no typechecking of
any sort.  I'd say there is a rather big cultural and technical divide
between Forth and Factor, despite some surface similarities.

The comp.lang.forth newsgroup is actually quite lively and interesting
and I'm a semi-regular there, though I use Forth only sort of casually,
mostly for the change of perspective it brings to programming, rather
than because I see it as a good way to deliver an end result.

This article is critical of Forth and somewhat unpopular on the Forth
newsgroup but it describes Forth's flavor from the "other side":

http://yosefk.com/blog/my-history-with-forth-stack-machines.html

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

#89391

In article <5533a77d$0$12993$c3e8da3$5496439d@news.astraweb.com>,
Steven D'Aprano  <steve+comp.lang.python@pearwood.info> wrote:
>On Sun, 19 Apr 2015 04:08 am, Albert van der Horst wrote:
>
>> Fire up a lowlevel interpreter like Forth. (e.g. gforth)
>
>Yay! I'm not the only one who uses or likes Forth!

I'm an author of half a dozen implementations, brand is called
ciforth. Just last Thursday an elaborate test session in Apple.
Expect release 5.2 for Linux Windows and Apple in a few weeks.

I've also published a minimalistic system called yourforth.

>
>Have you tried Factor? I'm wondering if it is worth looking at, as a more
>modern and less low-level version of Forth.

Chuck Moore has build a 100+ processor chip. I've experimented with
a parallel sieve for primes on the chip. Later Leon Konings and I have
run the same program on a simulator for the greenarray's chip
with 144 processors. Leon has written the simulator in Factor, it is
called Arrayforth. So I've seen some Factor from close up.
I think the system is practical and reliable. The runtime environment
however is a bit unwieldy. Leon is enthusiastic (but he always is)
about the documentation and general working. Factor has a lot of
protection,

It is nothing like ciforth however, most faulty ciforth programs end
in "segmentation fault". For 60K (+ 300K library) ciforth buys you an
interpreter, a scripter and a compiler. Unlike most Forth's you can do
    lina -c hello.frt
and then ship the hello program. ( And yes, hello.frt is a one liner
with just one definition, no boilerplate.)
I've solved hundreds of Euler project problems with it, but if
you need really abstract things (like representing "situations"
and counting them using a dict) I generally use Python.

ciforth arrayforth and yourforth are googleable.

>--
>Steven
>

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#88605

Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
> 
> > On 04/07/2015 05:44 AM, 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.
> 
> > How do you know the baseconversion is the bottleneck, if you haven't
> > written any Python code yet?
> 
> He doesn't. He doesn't comprehend that as far as a computer is concerned 
> an integer has no specific 'base', it's only when presented in a form for 
> humans to read that it gets base information added in the representation.
> 
> He's making these and other similar errors in the javascript groups too.
> 
> I suspect he's one of those people that spends his time thinking up 
> elaborate solutions that he has no idea how to implement as a response to 
> dreamt up non existent problems.
> 
> -- 
> Denis McMahon, denismfmcmahon@gmail.com

Well Denis if it hasn't a base then how can you add integers, the integer operations assume base 10. 

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

#88581

On Tue, Apr 7, 2015 at 3:44 AM,  <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.
>
> I need the fastest algorithm to find the relation to a decimal number.
> Digmult is an instance of base at a digitplace (base^x) what i try to find is the digit for the below condition is true and the loop break.
>
>
> *********************************
> for (digit=0;digit<=base;digit++) {
>        if((digit+1)*digmult>decNumber)break;
> }
> *********************************
>
> So i am looking for the digit where following condition true.
>
> if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then BREAK;

I'm not sure that I understand what it is that you're trying to
accomplish. Are you trying to find the digits without using division
because "division is slow"? If that's the case, then let me show you
something.

$ python -m timeit -s "n = 1523837293" "n // 1000000"
1000000 loops, best of 3: 0.286 usec per loop

$ python -m timeit -s "n = 1523" "n * 1000000; (n+1) * 1000000"
1000000 loops, best of 3: 0.455 usec per loop

In Python, one addition and two multiplications are already slower
than a single division. The only way you're going to beat division by
using trial multiplication is if the first digit that you try is
always correct. To do that, you would need an oracle feeding your
search algorithm, and then you might as well just use the oracle.

> One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?

Do you mean binary search? That would be an improvement over the
linear search algorithm you've shown. Whether a trinary search might
be faster would depend on the distribution of the numbers you expect.
If they're evenly distributed, it will be slower.

> I Think also i remember that if the search space so big that at least 22 or 23 guesses, needed.A random Oracle may even faster?
>
> Just pick up a number and get lucky, is it any truth to that?

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

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

#88596

Den tisdag 7 april 2015 kl. 16:32:56 UTC+2 skrev Ian:
> On Tue, Apr 7, 2015 at 3:44 AM,  <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.
> >
> > I need the fastest algorithm to find the relation to a decimal number.
> > Digmult is an instance of base at a digitplace (base^x) what i try to find is the digit for the below condition is true and the loop break.
> >
> >
> > *********************************
> > for (digit=0;digit<=base;digit++) {
> >        if((digit+1)*digmult>decNumber)break;
> > }
> > *********************************
> >
> > So i am looking for the digit where following condition true.
> >
> > if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then BREAK;
> 
> I'm not sure that I understand what it is that you're trying to
> accomplish. Are you trying to find the digits without using division
> because "division is slow"? If that's the case, then let me show you
> something.
> 
> $ python -m timeit -s "n = 1523837293" "n // 1000000"
> 1000000 loops, best of 3: 0.286 usec per loop
> 
> $ python -m timeit -s "n = 1523" "n * 1000000; (n+1) * 1000000"
> 1000000 loops, best of 3: 0.455 usec per loop
> 
> In Python, one addition and two multiplications are already slower
> than a single division. The only way you're going to beat division by
> using trial multiplication is if the first digit that you try is
> always correct. To do that, you would need an oracle feeding your
> search algorithm, and then you might as well just use the oracle.
> 
> > One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?
> 
> Do you mean binary search? That would be an improvement over the
> linear search algorithm you've shown. Whether a trinary search might
> be faster would depend on the distribution of the numbers you expect.
> If they're evenly distributed, it will be slower.
> 
> > I Think also i remember that if the search space so big that at least 22 or 23 guesses, needed.A random Oracle may even faster?
> >
> > Just pick up a number and get lucky, is it any truth to that?
> 
> On average, a random Oracle with a search space of 1000000 will need
> 1000000 guesses.

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. 

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.

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

#88606

On 04/07/2015 11:40 AM, jonas.thornvall@gmail.com wrote:
> Den tisdag 7 april 2015 kl. 16:32:56 UTC+2 skrev Ian:
>> On Tue, Apr 7, 2015 at 3:44 AM,  <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.
>>>
>>> I need the fastest algorithm to find the relation to a decimal number.
>>> Digmult is an instance of base at a digitplace (base^x) what i try to find is the digit for the below condition is true and the loop break.
>>>
>>>
>>> *********************************
>>> for (digit=0;digit<=base;digit++) {
>>>         if((digit+1)*digmult>decNumber)break;
>>> }
>>> *********************************
>>>
    <snip>
>>
>>> One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?
>>
>> Do you mean binary search? That would be an improvement over the
>> linear search algorithm you've shown. Whether a trinary search might
>> be faster would depend on the distribution of the numbers you expect.
>> If they're evenly distributed, it will be slower.
>>
>>> I Think also i remember that if the search space so big that at least 22 or 23 guesses, needed.A random Oracle may even faster?
>>>
>>> Just pick up a number and get lucky, is it any truth to that?
>>
>> On average, a random Oracle with a search space of 1000000 will need
>> 1000000 guesses.
>
> 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.
>
> 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.
>

Once again, there's no point in doing a search, when a simple integer 
divide can give you the exact answer.  And there's probably no point in 
going left to right when right to left would yield a tiny, fast program.

I haven't seen one line of Python from you yet, so perhaps you're just 
yanking our chain.  I'm not here to optimize Javascript code.

Using only Python 3.4 and builtin functions, this function can be 
implemented straightforwardly in 7 lines, assuming number is nonnegative 
integer, and base is positive integer.  It definitely could be done 
smaller, but then the code might be more confusing.

-- 
DaveA

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

#88607

Den tisdag 7 april 2015 kl. 18:34:32 UTC+2 skrev Dave Angel:
> On 04/07/2015 11:40 AM, jonas.thornvall@gmail.com wrote:
> > Den tisdag 7 april 2015 kl. 16:32:56 UTC+2 skrev Ian:
> >> On Tue, Apr 7, 2015 at 3:44 AM,  <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.
> >>>
> >>> I need the fastest algorithm to find the relation to a decimal number.
> >>> Digmult is an instance of base at a digitplace (base^x) what i try to find is the digit for the below condition is true and the loop break.
> >>>
> >>>
> >>> *********************************
> >>> for (digit=0;digit<=base;digit++) {
> >>>         if((digit+1)*digmult>decNumber)break;
> >>> }
> >>> *********************************
> >>>
>     <snip>
> >>
> >>> One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?
> >>
> >> Do you mean binary search? That would be an improvement over the
> >> linear search algorithm you've shown. Whether a trinary search might
> >> be faster would depend on the distribution of the numbers you expect.
> >> If they're evenly distributed, it will be slower.
> >>
> >>> I Think also i remember that if the search space so big that at least 22 or 23 guesses, needed.A random Oracle may even faster?
> >>>
> >>> Just pick up a number and get lucky, is it any truth to that?
> >>
> >> On average, a random Oracle with a search space of 1000000 will need
> >> 1000000 guesses.
> >
> > 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.
> >
> > 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.
> >
> 
> Once again, there's no point in doing a search, when a simple integer 
> divide can give you the exact answer.  And there's probably no point in 
> going left to right when right to left would yield a tiny, fast program.
> 
> I haven't seen one line of Python from you yet, so perhaps you're just 
> yanking our chain.  I'm not here to optimize Javascript code.
> 
> Using only Python 3.4 and builtin functions, this function can be 
> implemented straightforwardly in 7 lines, assuming number is nonnegative 
> integer, and base is positive integer.  It definitely could be done 
> smaller, but then the code might be more confusing.
> 
> -- 
> DaveA

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

Using base 429496729?

How long time did it take to find it?

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

#88608

On Tue, Apr 7, 2015 at 11:07 AM,  <jonas.thornvall@gmail.com> wrote:
> Den tisdag 7 april 2015 kl. 18:34:32 UTC+2 skrev Dave Angel:
>> Once again, there's no point in doing a search, when a simple integer
>> divide can give you the exact answer.  And there's probably no point in
>> going left to right when right to left would yield a tiny, fast program.
>>
>> I haven't seen one line of Python from you yet, so perhaps you're just
>> yanking our chain.  I'm not here to optimize Javascript code.
>>
>> Using only Python 3.4 and builtin functions, this function can be
>> implemented straightforwardly in 7 lines, assuming number is nonnegative
>> integer, and base is positive integer.  It definitely could be done
>> smaller, but then the code might be more confusing.
>>
>> --
>> DaveA
>
> So you can tell me the first (higest) digit of the integer 2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490
>
> Using base 429496729?

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

> How long time did it take to find it?

About 15 microseconds.

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

#88638

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

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

#88642

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.

If the array is always a multiple of four bytes, then that is logically
equivalent to using base 4294967296 with 32-bit digits:

\x0\x0\x0\x0 \x0\x0\x0\x1 \x0\x0\x0\x2 ... \xFF\xFF\xFF\xFF

(in decimal, 0 to 4294967295). It's still fundamentally binary though, but I
suppose it's not entirely pointless to talk about base 2**32 or base 2**64
numbers, in the context of a high-performance Big Num implementation. But
it wouldn't be practical to use *arbitrary bases* up to 2**32 or 2**64, and
it certainly isn't practical to have human beings read or write numbers in
such large bases. 


-- 
Steven

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

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

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

csiph-web