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

Groups > comp.lang.forth > #18656 > unrolled thread

structure and interpretation of computer programs exercsie 1.3 in forth

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

Contents

  structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 04:22 -0800
    Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-11 05:47 -0800
      Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:12 -0800
        Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:18 -0800
          Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:20 -0800
        Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:19 -0800
          Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:38 -0800
            Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:51 -0800
              Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 07:10 -0800
              Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 07:58 -0800
                Re: structure and interpretation of computer programs exercsie 1.3 in forth rickman <gnuarm@gmail.com> - 2013-01-14 10:01 -0500
        Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:25 -0800
          Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:28 -0800
          Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:33 -0800
            Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:37 -0800
        Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 06:56 -0800
          Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 08:03 -0800
            Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 08:06 -0800
              Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 12:27 -0800
                Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 17:32 -0800
                  Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-13 23:21 -0800
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-13 23:41 -0800
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-13 23:43 -0800
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-14 00:02 -0800
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-14 22:43 +1300
                            Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-14 02:41 -0800
                              Re: structure and interpretation of computer programs exercsie 1.3 in forth Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-01-14 11:13 +0000
                              Re: structure and interpretation of computer programs exercsie 1.3 in forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-01-14 11:16 +0000
                                Re: structure and interpretation of computer programs exercsie 1.3 in forth mhx@iae.nl (Marcel Hendrix) - 2013-01-14 21:27 +0200
                            Re: structure and interpretation of computer programs exercsie 1.3 in forth Howerd <howerdo@yahoo.co.uk> - 2013-01-14 03:34 -0800
                            Re: structure and interpretation of computer programs exercsie 1.3  in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-14 12:53 +0000
                              Re: structure and interpretation of computer programs exercsie 1.3  in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-17 17:31 +1300
                            Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-21 19:35 -0800
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-14 02:55 -0800
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth rickman <gnuarm@gmail.com> - 2013-01-14 10:14 -0500
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Bernd Paysan <bernd.paysan@gmx.de> - 2013-01-14 20:04 +0100
                            Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-21 19:57 -0800
                              Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-21 23:19 -0800
                                Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-24 18:58 -0800
                                  Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-25 15:46 -0800
                                    Re: structure and interpretation of computer programs exercsie 1.3 in forth Pablo Hugo Reda <pabloreda@gmail.com> - 2013-01-25 19:09 -0800
                                      Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-26 01:12 -0800
                                  Re: structure and interpretation of computer programs exercsie 1.3 in forth mhx@iae.nl (Marcel Hendrix) - 2013-01-26 12:58 +0200
                                    Re: structure and interpretation of computer programs exercsie 1.3 in forth Alex McDonald <blog@rivadpm.com> - 2013-01-26 04:42 -0800
                                    Re: structure and interpretation of computer programs exercsie 1.3 in forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-01-26 14:35 +0000
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:38 -0800
              Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 12:36 -0800
                Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 17:33 -0800
                  Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-14 22:46 +1300
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth rickman <gnuarm@gmail.com> - 2013-01-14 10:20 -0500
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-14 10:41 -0600
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-17 17:34 +1300
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:48 -0800
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:49 -0800
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-21 23:55 -0800
                  Re: structure and interpretation of computer programs exercsie 1.3 in forth "Ed" <invalid@nospam.com> - 2013-01-18 12:50 +1100
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth Bernd Paysan <bernd.paysan@gmx.de> - 2013-01-18 23:31 +0100
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth "Ed" <invalid@nospam.com> - 2013-01-20 12:42 +1100
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <markrobertwills@yahoo.co.uk> - 2013-01-20 01:24 -0800
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-20 15:51 -0800
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-21 22:14 +1300
                            Re: structure and interpretation of computer programs exercsie 1.3 in forth Hugh Aguilar <hughaguilar96@yahoo.com> - 2013-01-21 19:14 -0800
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth "A. K." <akk@nospam.org> - 2013-01-20 11:13 +0100
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-20 02:45 -0800
                            Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-21 17:14 +0000
                              Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-23 01:52 -0800
                                Re: structure and interpretation of computer programs exercsie 1.3 in forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-23 04:25 -0600
                                Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-23 15:20 +0000
                                  Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-23 09:29 -0800
                                    Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-23 17:40 +0000
                                      Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-23 22:03 -0800
                                        Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-24 22:13 +1300
                                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-24 02:57 -0800
                                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-26 13:49 -0800
                                            Re: structure and interpretation of computer programs exercsie 1.3 in forth "Elizabeth D. Rather" <erather@forth.com> - 2013-01-26 12:40 -1000
                                              Re: structure and interpretation of computer programs exercsie 1.3 in forth Paul Rubin <no.email@nospam.invalid> - 2013-01-26 23:20 -0800
                                                Re: structure and interpretation of computer programs exercsie 1.3 in forth mhx@iae.nl (Marcel Hendrix) - 2013-01-27 09:52 +0200
                                    Re: structure and interpretation of computer programs exercsie 1.3 in forth "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2013-01-23 23:05 +0000
                          Re: structure and interpretation of computer programs exercsie 1.3  in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-21 17:05 +0000
                            Re: structure and interpretation of computer programs exercsie 1.3  in forth "A. K." <akk@nospam.org> - 2013-01-21 19:28 +0100
                              Re: structure and interpretation of computer programs exercsie 1.3   in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-22 17:43 +0000
                              Re: structure and interpretation of computer programs exercsie 1.3 in forth "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2013-01-22 19:12 +0000
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth stephenXXX@mpeforth.com (Stephen Pelc) - 2013-01-21 12:13 +0000
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-21 17:28 +0000
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-01-22 18:06 +0000
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth Bernd Paysan <bernd.paysan@gmx.de> - 2013-01-22 19:30 +0100
                Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 23:06 -0800
                  Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-22 02:20 -0800
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-22 03:36 -0800
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-22 06:51 -0800
                  Re: structure and interpretation of computer programs exercsie 1.3 in forth marko <marko@marko.marko> - 2013-01-24 22:14 +1100
                    Re: structure and interpretation of computer programs exercsie 1.3 in forth the_gavino_himself <visphatesjava@gmail.com> - 2013-01-27 20:39 -0800
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth marko <marko@marko.marko> - 2013-02-01 22:07 +1100
                      Re: structure and interpretation of computer programs exercsie 1.3 in forth marko <marko@marko.marko> - 2013-02-01 22:53 +1100
                        Re: structure and interpretation of computer programs exercsie 1.3 in forth the_gavino_himself <visphatesjava@gmail.com> - 2013-02-08 19:50 -0800
                          Re: structure and interpretation of computer programs exercsie 1.3 in forth Elizabeth D Rather <erather@forth.com> - 2013-02-08 19:22 -1000
        Re: structure and interpretation of computer programs exercsie 1.3 in forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-01-11 11:44 -0600
          Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-11 12:34 -0800
      Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-11 06:18 -0800
    Re:structure and interpretation of computer programs exercsie 1.3 in forth Hans Bezemer <the.beez.speaks@gmail.com> - 2013-01-14 00:13 +0100
      Re: structure and interpretation of computer programs exercsie 1.3 in forth Doug Hoffman <glidedog@gmail.com> - 2013-01-13 19:12 -0500
        Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 18:26 -0800
        Re: structure and interpretation of computer programs exercsie 1.3 in forth Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2013-01-14 08:29 +0000
          Re: structure and interpretation of computer programs exercsie 1.3 in forth Hans Bezemer <the.beez.speaks@gmail.com> - 2013-01-14 23:52 +0100
      Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-13 18:31 -0800
      Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-13 23:19 -0800
        Re: structure and interpretation of computer programs exercsie 1.3 in forth gavino_himself <visploveslisp@gmail.com> - 2013-01-21 22:46 -0800
          Re: structure and interpretation of computer programs exercsie 1.3 in forth Mark Wills <forthfreak@gmail.com> - 2013-01-21 23:40 -0800

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

#18744

On Jan 14, 1:32 am, gavino_himself <visplovesl...@gmail.com> wrote:
> On Friday, January 11, 2013 12:27:34 PM UTC-8, M.R.W Wills wrote:
> > On Jan 11, 4:06 pm, gavino_himself <visplovesl...@gmail.com> wrote:
>
> > > On Friday, January 11, 2013 8:03:13 AM UTC-8, gavino_himself wrote:
>
> > > > On Friday, January 11, 2013 6:56:35 AM UTC-8, M.R.W Wills wrote:
>
> > > > > On Jan 11, 2:12 pm, Mark Wills <forthfr...@gmail.com> wrote:
>
> > > > > > On Jan 11, 1:47 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
> > > > > > > On Jan 11, 12:22 pm, gavino_himself <visplovesl...@gmail.com> wrote:
>
> > > > > > > > Exercise 1.3.  Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
>
> > > > > > > > Please post a forth solution.
>
> > > > > > > First you should post how you might go about doing it by hand.
>
> > > > > > > Describe how you might take 3 numbers and work out the sum of the
>
> > > > > > > squares of the two larger numbers.
>
> > > > > > Alex,
>
> > > > > > I hear you, but there's no chance of Gavino being able to concentrate
>
> > > > > > on *anything* for that long. I'd be surprised if he can piss while
>
> > > > > > standing up!
>
> > > > > > Nicely factored:
>
> > > > > > : swap? ( n1 n2 -- n1 n2 | n2 n1)
>
> > > > > >         2dup < if swap then ;
>
> > > > > > : gavino ( n1 n2 n3 - n)
>
> > > > > >         swap? rot swap? drop   dup * swap dup * + ;
>
> > > > > Actually, this is possibly "better" in the sense that it's smaller and
>
> > > > > more efficient:
>
> > > > > : gavino ( n1 n2 n3 - n)
>
> > > > >         2dup < if swap then rot max   dup *  swap dup *  + ;
>
> > > > say you have 1 2 3
>
> > > > can you describe what this does?
>
> > > > I am having trouble because < must be compiled following what happens.
>
> > > >    2dup < if swap then ;
>
> > > I guess it goes 1 2 3
>
> > > then has 1 2 3 2 3
>
> > > then < sees that 2 is less than 3 in the top 2, consuming them in the process, and executes swap, to produce
>
> > > 1 3 2
>
> > > ok wow
>
> > > this takes a little getting used to
>
> > > I was confusing myself thinking that < too 3 off the top and made 3 < 2
>
> > That's exactly right. You got it.
>
> > If you execute the following in Forth:
>
> > 5 9 <
>
> > What you are asking is "is 5 less than 9?". The answer is yes, so a
>
> > TRUE flag will be left on the stack. Note also that < "consumes" its
>
> > arguments (5 and 9 in this example) which is why you need a 2dup.
>
> Mr Willis you have taught me some forth!!!
> I salute you.
> AWESOME
> I have not failed to notice how the forth solution is in fewer lines than the lisp solution!!
> I am now motivated to finish starting forth and read thinking forth.
> You have single handedly ressurected my motivation to explore forth!- Hide quoted text -
>
> - Show quoted text -

Why thank you, sir. And it's Wills, not Willis ;-)

(If I had a pound...!)

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

#18745

On Jan 14, 7:21 am, Mark Wills <forthfr...@gmail.com> wrote:
> On Jan 14, 1:32 am, gavino_himself <visplovesl...@gmail.com> wrote:
>
>
>
>
>
> > On Friday, January 11, 2013 12:27:34 PM UTC-8, M.R.W Wills wrote:
> > > On Jan 11, 4:06 pm, gavino_himself <visplovesl...@gmail.com> wrote:
>
> > > > On Friday, January 11, 2013 8:03:13 AM UTC-8, gavino_himself wrote:
>
> > > > > On Friday, January 11, 2013 6:56:35 AM UTC-8, M.R.W Wills wrote:
>
> > > > > > On Jan 11, 2:12 pm, Mark Wills <forthfr...@gmail.com> wrote:
>
> > > > > > > On Jan 11, 1:47 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
> > > > > > > > On Jan 11, 12:22 pm, gavino_himself <visplovesl...@gmail.com> wrote:
>
> > > > > > > > > Exercise 1.3.  Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.
>
> > > > > > > > > Please post a forth solution.
>
> > > > > > > > First you should post how you might go about doing it by hand.
>
> > > > > > > > Describe how you might take 3 numbers and work out the sum of the
>
> > > > > > > > squares of the two larger numbers.
>
> > > > > > > Alex,
>
> > > > > > > I hear you, but there's no chance of Gavino being able to concentrate
>
> > > > > > > on *anything* for that long. I'd be surprised if he can piss while
>
> > > > > > > standing up!
>
> > > > > > > Nicely factored:
>
> > > > > > > : swap? ( n1 n2 -- n1 n2 | n2 n1)
>
> > > > > > >         2dup < if swap then ;
>
> > > > > > > : gavino ( n1 n2 n3 - n)
>
> > > > > > >         swap? rot swap? drop   dup * swap dup * + ;
>
> > > > > > Actually, this is possibly "better" in the sense that it's smaller and
>
> > > > > > more efficient:
>
> > > > > > : gavino ( n1 n2 n3 - n)
>
> > > > > >         2dup < if swap then rot max   dup *  swap dup *  + ;
>
> > > > > say you have 1 2 3
>
> > > > > can you describe what this does?
>
> > > > > I am having trouble because < must be compiled following what happens.
>
> > > > >    2dup < if swap then ;
>
> > > > I guess it goes 1 2 3
>
> > > > then has 1 2 3 2 3
>
> > > > then < sees that 2 is less than 3 in the top 2, consuming them in the process, and executes swap, to produce
>
> > > > 1 3 2
>
> > > > ok wow
>
> > > > this takes a little getting used to
>
> > > > I was confusing myself thinking that < too 3 off the top and made 3 < 2
>
> > > That's exactly right. You got it.
>
> > > If you execute the following in Forth:
>
> > > 5 9 <
>
> > > What you are asking is "is 5 less than 9?". The answer is yes, so a
>
> > > TRUE flag will be left on the stack. Note also that < "consumes" its
>
> > > arguments (5 and 9 in this example) which is why you need a 2dup.
>
> > Mr Willis you have taught me some forth!!!
> > I salute you.
> > AWESOME
> > I have not failed to notice how the forth solution is in fewer lines than the lisp solution!!
> > I am now motivated to finish starting forth and read thinking forth.
> > You have single handedly ressurected my motivation to explore forth!- Hide quoted text -
>
> > - Show quoted text -
>
> Why thank you, sir. And it's Wills, not Willis ;-)
>
> (If I had a pound...!)- Hide quoted text -
>
> - Show quoted text -

I also spent a while looking at doing it without conditionals, and
eventually concluded that it couldn't be done. Well, okay, if there is
a word like n SORT which sorted the top n elements on the stack, then
yes it could be "done" without a conditional, but you've just hidden
the conditional, that's all.

As far as I can see, the simplest way is to sort the stack first in
order to drop the lowest of the three numbers. That requires at least
one comparison and a conditional. The second time it can be done with
MAX (which is also a conditional, it's abstracted ;-) ).

Thus: 2dup < if swap then rot max

My system has OnTrue: and OnFalse:, so I could write it like this:

2dup < OnTrue: swap  rot max

OnTrue: executes the next word if flag is true, otherwise it jumps
over it. It has to be used with caution though, as it simply adds 1
cell to the IP if flag is true, therefore, an immediate compiling
word, or a literal, shouldn't follow an OnTrue: or OnFalse: .

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

#18746

Mark Wills <forthfreak@gmail.com> writes:
> I also spent a while looking at doing it without conditionals, and
> eventually concluded that it couldn't be done. 

: sq dup * ;
: g { a b c -- n } a sq b sq + c sq + a b c min min sq - ;

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

#18748

On Jan 14, 7:43 am, Paul Rubin <no.em...@nospam.invalid> wrote:
> Mark Wills <forthfr...@gmail.com> writes:
> > I also spent a while looking at doing it without conditionals, and
> > eventually concluded that it couldn't be done.
>
> : sq dup * ;
> : g { a b c -- n } a sq b sq + c sq + a b c min min sq - ;

Well, okay, I stand corrected! Nice job.

The fact that it needs locals, and computes all the squares is a bit
of an "ouch"! But hey nice job. Long way to go to avoid an IF...THEN
but hey, each to their own ;-)

I take your point, though!

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

#18750

On 1/14/13 9:02 PM, Mark Wills wrote:
> On Jan 14, 7:43 am, Paul Rubin <no.em...@nospam.invalid> wrote:
>> Mark Wills <forthfr...@gmail.com> writes:
>>> I also spent a while looking at doing it without conditionals, and
>>> eventually concluded that it couldn't be done.
>>
>> : sq dup * ;
>> : g { a b c -- n } a sq b sq + c sq + a b c min min sq - ;
>
> Well, okay, I stand corrected! Nice job.
>
> The fact that it needs locals, and computes all the squares is a bit
> of an "ouch"! But hey nice job. Long way to go to avoid an IF...THEN
> but hey, each to their own ;-)
>
> I take your point, though!
>

Aren't you ignoring the fact that there's a conditional in min? Why so 
important to avoid a conditional?

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

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

#18753

"Elizabeth D. Rather" <erather@forth.com> writes:
> Aren't you ignoring the fact that there's a conditional in min? 

: min ( a b -- n ) 2dup <= >r 2dup > and swap r> and or ;

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

#18756

On 14/01/2013 10:41, Paul Rubin wrote:
> "Elizabeth D. Rather" <erather@forth.com> writes:
>> Aren't you ignoring the fact that there's a conditional in min?
>
> : min ( a b -- n ) 2dup <= >r 2dup > and swap r> and or ;
>

Or
: min 2dup < 1+ roll drop ;

Or, if you don't like ROLL

: min 2dup > 1+ pick nip nip ;

-- 
Gerry

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

#18757

In article <7xk3rgt5ay.fsf@ruckus.brouhaha.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>"Elizabeth D. Rather" <erather@forth.com> writes:
>> Aren't you ignoring the fact that there's a conditional in min?
>
>: min ( a b -- n ) 2dup <= >r 2dup > and swap r> and or ;

Not to forget that one some processors MIN is a code word without jumps.
(Like ARM)

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]

#18778

albert@spenarnc.xs4all.nl (Albert van der Horst) writes Re: structure and interpretation of computer programs exercsie 1.3 in forth

> In article <7xk3rgt5ay.fsf@ruckus.brouhaha.com>,
> Paul Rubin  <no.email@nospam.invalid> wrote:
>>"Elizabeth D. Rather" <erather@forth.com> writes:
>>> Aren't you ignoring the fact that there's a conditional in min?
>>
>>: min ( a b -- n ) 2dup <= >r 2dup > and swap r> and or ;

>Not to forget that one some processors MIN is a code word without jumps.
>(Like ARM)
[..]

Assuming your Forth has a free stack (like iForth):

: m2 ( n -- n^2 | 0 ) ( S: 3min -- ) dup S <> and dup * ;
: g ( a b c -- n ) 
	3dup min min >S
	rot  m2   ( -- b c a^2 )
	rot  m2 + ( -- c a^2+b^2 )
	swap m2 + 
	-S ;

[ I could have kept 3min and the VALUE, but the LOCALs in g 
produced ugly code. ]

FORTH> ' g idis
$01402ACA  pop           rbx
$01402ACB  pop           rdi
$01402ACC  mov           rax, [rsp] qword
$01402AD0  push          rdi
$01402AD1  push          rbx
$01402AD2  push          rax
$01402AD3  mov           rcx, rdi
$01402AD6  cmp           rbx, rcx
$01402AD9  cmovg         rbx, rcx
$01402ADD  pop           rcx
$01402ADE  cmp           rbx, rcx
$01402AE1  cmovg         rbx, rcx
$01402AE5  pop           rdi
$01402AE6  pop           rax
$01402AE7  pop           rdx
$01402AE8  cmp           rbx, rdx
$01402AEB  setne         cl
$01402AEF  movzx         rcx, cl
$01402AF3  neg           rcx
$01402AF6  and           rdx, rcx
$01402AF9  imul          rdx, rdx
$01402AFD  cmp           rbx, rax
$01402B00  setne         cl
$01402B04  movzx         rcx, cl
$01402B08  neg           rcx
$01402B0B  and           rax, rcx
$01402B0E  imul          rax, rax
$01402B12  lea           r9, [rdx rax*1] qword
$01402B16  cmp           rbx, rdi
$01402B19  setne         cl
$01402B1D  movzx         rcx, cl
$01402B21  neg           rcx
$01402B24  and           rdi, rcx
$01402B27  imul          rdi, rdi
$01402B2B  lea           rbx, [r9  rdi*1] qword
$01402B2F  push          rbx
$01402B30  ;

Branchless.


Andrew's:

: GodHelpedUsAll ( n1 n2 n3 -- n )  2dup max >r min max  dup * r> dup * + ;  

$01402BC0  : [trashed]
$01402BCA  pop           rbx
$01402BCB  mov           rdi, [rsp] qword
$01402BCF  push          rbx
$01402BD0  mov           rcx, rdi
$01402BD3  cmp           rbx, rcx
$01402BD6  cmovl         rbx, rcx
$01402BDA  lea           rbp, [rbp -8 +] qword
$01402BDE  mov           [rbp 0 +] qword, rbx
$01402BE2  pop           rbx
$01402BE3  pop           rcx
$01402BE4  cmp           rbx, rcx
$01402BE7  cmovg         rbx, rcx
$01402BEB  pop           rcx
$01402BEC  cmp           rbx, rcx
$01402BEF  cmovl         rbx, rcx
$01402BF3  imul          rbx, rbx
$01402BF7  mov           rdi, [rbp 0 +] qword
$01402BFB  lea           rbp, [rbp 8 +] qword
$01402BFF  imul          rdi, rdi
$01402C03  lea           rbx, [rbx rdi*1] qword
$01402C07  push          rbx
$01402C08  ;

.. turns out branchless and small.


Howerd's: 

: min ( n n -- n )   2dup - abs - + 2 / ;      \ without conditionals
: max ( n n -- n )   2dup + >r min r> swap - ; \ without conditionals
\ returns the sum of the squares of the two larger values
: GodHelpUsAll ( n1 n2 n3 -- n )  2dup max >r min max  dup * r> dup * + ;  

FORTH> ' GodHelpUsAll idis
$01402CC0  : [trashed]
$01402CCA  pop           rbx
$01402CCB  pop           rdi
$01402CCC  mov           rax, rdi
$01402CCF  sub           rax, rbx
$01402CD2  mov           rdx, rax
$01402CD5  sar           rdx, #63 b#
$01402CD9  xor           rax, rdx
$01402CDC  sub           rax, rdx
$01402CDF  sub           rax, rbx
$01402CE2  neg           rax
$01402CE5  lea           rax, [rdi rax*1] qword
$01402CE9  lea           rdx, [rdi rbx*1] qword
$01402CED  lea           rbp, [rbp -8 +] qword
$01402CF1  mov           [rbp 0 +] qword, rdx
$01402CF5  push          rdi
$01402CF6  mov           rcx, rbx
$01402CF9  mov           rbx, rax
$01402CFC  sar           rbx, 1 b#
$01402D00  mov           rdi, [rbp 0 +] qword
$01402D04  lea           rbp, [rbp 8 +] qword
$01402D08  sub           rdi, rbx
$01402D0B  lea           rbp, [rbp -8 +] qword
$01402D0F  mov           [rbp 0 +] qword, rdi
$01402D13  pop           rbx
$01402D14  mov           rdi, rbx
$01402D17  sub           rdi, rcx
$01402D1A  mov           rax, rdi
$01402D1D  sar           rax, #63 b#
$01402D21  xor           rdi, rax
$01402D24  sub           rdi, rax
$01402D27  sub           rcx, rdi
$01402D2A  lea           rbx, [rbx rcx*1] qword
$01402D2E  sar           rbx, 1 b#
$01402D32  pop           rdi
$01402D33  mov           rax, rdi
$01402D36  sub           rax, rbx
$01402D39  mov           rdx, rax
$01402D3C  sar           rdx, #63 b#
$01402D40  xor           rax, rdx
$01402D43  sub           rax, rdx
$01402D46  sub           rax, rbx
$01402D49  neg           rax
$01402D4C  lea           rax, [rdi rax*1] qword
$01402D50  lea           rdx, [rdi rbx*1] qword
$01402D54  lea           rbp, [rbp -8 +] qword
$01402D58  mov           [rbp 0 +] qword, rdx
$01402D5C  mov           rbx, rax
$01402D5F  sar           rbx, 1 b#
$01402D63  mov           rdi, [rbp 0 +] qword
$01402D67  lea           rbp, [rbp 8 +] qword
$01402D6B  sub           rdi, rbx
$01402D6E  imul          rdi, rdi
$01402D72  mov           rbx, [rbp 0 +] qword
$01402D76  lea           rbp, [rbp 8 +] qword
$01402D7A  imul          rbx, rbx
$01402D7E  lea           rbx, [rdi rbx*1] qword
$01402D82  push          rbx
$01402D83  ;

Branchless but full of gas.

-marcel

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

#18758

Hi Elizabeth,

There is something elegant about not having two paths for the program execution.

Googling up a version of  min  without using an if, and extending it to  max  gives :

: min ( n n -- n )   2dup - abs - + 2 / ;      \ without conditionals
: max ( n n -- n )   2dup + >r min r> swap - ; \ without conditionals
\ returns the sum of the squares of the two larger values
: GodHelpUsAll ( n1 n2 n3 -- n )  2dup max >r min max  dup * r> dup * + ;  

Thanks to Gerry/The Beez for the neat solution, and to Andrew for the name ;-)

Best regards,
Howerd

PS keep up the good work Gavino...


On Monday, January 14, 2013 10:43:04 AM UTC+1, Elizabeth D. Rather wrote:
> On 1/14/13 9:02 PM, Mark Wills wrote:
> 
> > On Jan 14, 7:43 am, Paul Rubin <no.em...@nospam.invalid> wrote:
> 
> >> Mark Wills <forthfr...@gmail.com> writes:
> 
> >>> I also spent a while looking at doing it without conditionals, and
> 
> >>> eventually concluded that it couldn't be done.
> 
> >>
> 
> >> : sq dup * ;
> 
> >> : g { a b c -- n } a sq b sq + c sq + a b c min min sq - ;
> 
> >
> 
> > Well, okay, I stand corrected! Nice job.
> 
> >
> 
> > The fact that it needs locals, and computes all the squares is a bit
> 
> > of an "ouch"! But hey nice job. Long way to go to avoid an IF...THEN
> 
> > but hey, each to their own ;-)
> 
> >
> 
> > I take your point, though!
> 
> >
> 
> 
> 
> Aren't you ignoring the fact that there's a conditional in min? Why so 
> 
> important to avoid a conditional?
> 
> 
> 
> Cheers,
> 
> Elizabeth
> 
> 
> 
> -- 
> 
> ==================================================
> 
> Elizabeth D. Rather   (US & Canada)   800-55-FORTH
> 
> FORTH Inc.                         +1 310.999.6784
> 
> 5959 West Century Blvd. Suite 700
> 
> Los Angeles, CA 90045
> 
> http://www.forth.com
> 
> 
> 
> "Forth-based products and Services for real-time
> 
> applications since 1973."
> 
> ==================================================

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

#18759 — Re: structure and interpretation of computer programs exercsie 1.3 in forth

"Elizabeth D. Rather" <erather@forth.com> writes:
>Aren't you ignoring the fact that there's a conditional in min? Why so 
>important to avoid a conditional?

It's a good idea to avoid conditional branches, for several reasons:

1) On the CPU level, conditional branches can be expensive, especially
if they are hard to predict.  A word like MIN can be implemented with
a (often cheaper) conditional move.

2) On the programming and testing level, each conditonal branch
increases the number of test cases that have to be used in checking
the result.  E.g., for Forth, if the stack management in one of the
branches is ok, there could still be a stack depth bug (among others)
in the other branch.

Of course, like many rules, this one has to be balanced.  if you have
to add too much complication for avoiding a conditional branch, it's
not a good idea.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2012: http://www.euroforth.org/ef12/

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

#18869 — Re: structure and interpretation of computer programs exercsie 1.3 in forth

On 1/15/13 1:53 AM, Anton Ertl wrote:
> "Elizabeth D. Rather" <erather@forth.com> writes:
>> Aren't you ignoring the fact that there's a conditional in min? Why so
>> important to avoid a conditional?
>
> It's a good idea to avoid conditional branches, for several reasons:
>
> 1) On the CPU level, conditional branches can be expensive, especially
> if they are hard to predict.  A word like MIN can be implemented with
> a (often cheaper) conditional move.
>
> 2) On the programming and testing level, each conditonal branch
> increases the number of test cases that have to be used in checking
> the result.  E.g., for Forth, if the stack management in one of the
> branches is ok, there could still be a stack depth bug (among others)
> in the other branch.
>
> Of course, like many rules, this one has to be balanced.  if you have
> to add too much complication for avoiding a conditional branch, it's
> not a good idea.

Which seems to be the case with some of the substitutes people just 
offered :-)

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

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

#18978

On Jan 14, 2:43 am, "Elizabeth D. Rather" <erat...@forth.com> wrote:
> Aren't you ignoring the fact that there's a conditional in min? Why so
> important to avoid a conditional?
>
> Cheers,
> Elizabeth

Elizabeth Rather doesn't know about the CMOVcc instructions in x86
assembly language! This tells me that she doesn't know anything about
the modern x86 processors, and she would not be able to write even a
simple function such as MIN or MAX in assembly language. Also, she
asks: "Why so important to avoid a conditional?" This tells me that
she doesn't know anything about any x86 processor, all the way back to
the 8088 (see Abrash's first book for a lengthy discussion of how
branches empty out the prefetch queue on the 8088).

This is an abysmal level of ignorance! Branching has been an issue on
all processors, for the last 30 years! To find a processor that
branching wasn't an issue on, you have to go back to things like the
65c02 and the Z80 (and the PDP-11 afaik) that didn't do any look-ahead
at all, but just executed each opcode one after the other, with each
taking a fixed number of clock cycles. That world hasn't existed since
I was a teenager.

I don't consider Elizabeth Rather to be a programmer at all. When she
says that my code "sucks," she is speaking as a Forth Inc.
salesperson, and not as a technical person. She really knows nothing
about the subject --- except that she wants people to spend $500 on
SwiftForth --- but she doesn't have any technical knowledge.

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

#18754

Mark Wills <forthfreak@gmail.com> writes:
> The fact that it needs locals,

It doesn't really "need" them, they just make the code easier.

> and computes all the squares is a bit of an "ouch"!

0 value 3min
: 3set ( a b c -- ) min min to 3min ;
: m2 ( n -- n^2 | 0 ) dup 3min <> and dup * ;
: g { a b c -- n }  a b c 3set a m2 b m2 + c m2 + ;

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

#18766

On 1/14/2013 3:02 AM, Mark Wills wrote:
> On Jan 14, 7:43 am, Paul Rubin<no.em...@nospam.invalid>  wrote:
>> Mark Wills<forthfr...@gmail.com>  writes:
>>> I also spent a while looking at doing it without conditionals, and
>>> eventually concluded that it couldn't be done.
>>
>> : sq dup * ;
>> : g { a b c -- n } a sq b sq + c sq + a b c min min sq - ;
>
> Well, okay, I stand corrected! Nice job.
>
> The fact that it needs locals, and computes all the squares is a bit
> of an "ouch"! But hey nice job. Long way to go to avoid an IF...THEN
> but hey, each to their own ;-)
>
> I take your point, though!

You can *always* do logic without conditionals.  Boolean logic is just a 
form of math and math can be done with adds and multiplies.  I do that 
often in spread sheets when I don't want to type the awkward format for 
a conditional.  1*x = x, 0*x = 0, same as a conditional.  Subtracting 
from 1 can give you inversion, multiplying is an AND so now you have a 
functionally complete Boolean logic.

Not that it is relevant to this conversation, but it is a well known 
fact that you can replace OR with XOR and still have a functionally 
complete algebra.  Some FPGA families have done that in an attempt to 
minimize the size of the logic block while efficiently supporting sums. 
  In fact, the OR of a set of AND terms is called, "sum of products". 
Most people aren't used to XOR based logic and so reject the idea as 
"alien" or "unintuitive".  It's all a matter of what you have learned. 
Ask Chuck Moore.

Rick

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

#18770

Mark Wills wrote:

> On Jan 14, 7:43 am, Paul Rubin <no.em...@nospam.invalid> wrote:
>> Mark Wills <forthfr...@gmail.com> writes:
>> > I also spent a while looking at doing it without conditionals, and
>> > eventually concluded that it couldn't be done.
>>
>> : sq dup * ;
>> : g { a b c -- n } a sq b sq + c sq + a b c min min sq - ;
> 
> Well, okay, I stand corrected! Nice job.

There are other ways:

: sq ( n -- n² ) dup * ;
: g ( a b c -- n )  2dup max sq >r min max sq r> + ;

> The fact that it needs locals, and computes all the squares is a bit
> of an "ouch"!

Yes.  The solution without locals and without squaring all three numbers 
is shorter.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#18979

On Jan 14, 12:04 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
> : sq ( n -- n² ) dup * ;
> : g ( a b c -- n )  2dup max sq >r min max sq r> + ;

That is the way that I would write it. This is perhaps the first time
in which Paysan has written code that I thought was good.

This solution reminds me somewhat of that puzzle in which the guy is
transporting a cannibal, a Christian and a bag of sugar across a
river. If left alone, the cannibal will eat the Christian, and the
Christian will eat the sugar, but the cannibal won't eat the sugar.

It occurs to me that it might be useful in Strate Forth if I had a
primitive called MINMAX that does this:

: minmax ( a b -- min max )
    2dup min -rot  max ;

Being a standard part of the language however, it would be written in
assembly language. I could have this standardized, but not provide MIN
and MAX as part of the language, as they can easily be written in
terms of MINMAX (using DROP or NIP to get rid of the unwanted part).
I'm trying to make Strate Forth significantly smaller than ANS-Forth,
so reducing the number of primitive words is a good thing. In this
case, I not only reduce the number of primitives, but I provide a
primitive MINMAX that is useful in it own right.

This is MINMAX in VFX:

see minmax
MINMAX
( 004C7AD0    8B5500 )                MOV       EDX, [EBP]
( 004C7AD3    3BD3 )                  CMP       EDX, EBX
( 004C7AD5    0F4FD3 )                CMOVNLE/G EDX, EBX
( 004C7AD8    8B4D00 )                MOV       ECX, [EBP]
( 004C7ADB    3BD9 )                  CMP       EBX, ECX
( 004C7ADD    0F4CD9 )                CMOVL/NGE EBX, ECX
( 004C7AE0    895500 )                MOV       [EBP], EDX
( 004C7AE3    C3 )                    NEXT,
( 20 bytes, 8 instructions )

That is pretty impressive optimization! If I were writing by hand, I
wouldn't have used the ECX register, but would have just used [EBP]
--- that would have been slightly shorter. Another possibility would
be to load ECX from EDX at the beginning, to avoid a memory access,
which might be slightly faster. Anyway, what VFX generated was pretty
close to optimal, so I'm impressed.

I would be interested in seeing what SwiftForth generates. LOL

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

#18985

On Jan 22, 3:57 am, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> On Jan 14, 12:04 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
>
> > : sq ( n -- n² ) dup * ;
> > : g ( a b c -- n )  2dup max sq >r min max sq r> + ;
>
> That is the way that I would write it. This is perhaps the first time
> in which Paysan has written code that I thought was good.
>
> This solution reminds me somewhat of that puzzle in which the guy is
> transporting a cannibal, a Christian and a bag of sugar across a
> river. If left alone, the cannibal will eat the Christian, and the
> Christian will eat the sugar, but the cannibal won't eat the sugar.
>
> It occurs to me that it might be useful in Strate Forth if I had a
> primitive called MINMAX that does this:
>
> : minmax ( a b -- min max )
>     2dup min -rot  max ;
>
> Being a standard part of the language however, it would be written in
> assembly language. I could have this standardized, but not provide MIN
> and MAX as part of the language, as they can easily be written in
> terms of MINMAX (using DROP or NIP to get rid of the unwanted part).
> I'm trying to make Strate Forth significantly smaller than ANS-Forth,
> so reducing the number of primitive words is a good thing. In this
> case, I not only reduce the number of primitives, but I provide a
> primitive MINMAX that is useful in it own right.
>
> This is MINMAX in VFX:
>
> see minmax
> MINMAX
> ( 004C7AD0    8B5500 )                MOV       EDX, [EBP]
> ( 004C7AD3    3BD3 )                  CMP       EDX, EBX
> ( 004C7AD5    0F4FD3 )                CMOVNLE/G EDX, EBX
> ( 004C7AD8    8B4D00 )                MOV       ECX, [EBP]
> ( 004C7ADB    3BD9 )                  CMP       EBX, ECX
> ( 004C7ADD    0F4CD9 )                CMOVL/NGE EBX, ECX
> ( 004C7AE0    895500 )                MOV       [EBP], EDX
> ( 004C7AE3    C3 )                    NEXT,
> ( 20 bytes, 8 instructions )
>
> That is pretty impressive optimization! If I were writing by hand, I
> wouldn't have used the ECX register, but would have just used [EBP]
> --- that would have been slightly shorter. Another possibility would
> be to load ECX from EDX at the beginning, to avoid a memory access,
> which might be slightly faster. Anyway, what VFX generated was pretty
> close to optimal, so I'm impressed.
>
> I would be interested in seeing what SwiftForth generates. LOL

Wouldn't the following be potentially more efficient at run-time:

: minmax ( a b -- min max) 2dup > if swap then ;

What I'm thinking is, where a is already < b no stack manipulation
(via min -rot and max) takes place. In the case where a > b then a
simple swap is executed.

I can imagine that the above might lead to a longer assembly code
definition than your example, but if instrumented, I have a hunch the
second example might be a little faster (though I know very little
about the internal optimisations and machinations that take place deep
within modern x86 processors, which is damned clever stuff -
alchemy!). Certainly on my toy system, I'm sure the second example
would be faster in all cases.

Just thinkin' out loud...!

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

#19111

On Jan 22, 12:19 am, Mark Wills <forthfr...@gmail.com> wrote:
> On Jan 22, 3:57 am, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
>
>
>
>
>
>
>
>
> > On Jan 14, 12:04 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
>
> > > : sq ( n -- n² ) dup * ;
> > > : g ( a b c -- n )  2dup max sq >r min max sq r> + ;
>
> > That is the way that I would write it. This is perhaps the first time
> > in which Paysan has written code that I thought was good.
>
> > This solution reminds me somewhat of that puzzle in which the guy is
> > transporting a cannibal, a Christian and a bag of sugar across a
> > river. If left alone, the cannibal will eat the Christian, and the
> > Christian will eat the sugar, but the cannibal won't eat the sugar.
>
> > It occurs to me that it might be useful in Strate Forth if I had a
> > primitive called MINMAX that does this:
>
> > : minmax ( a b -- min max )
> >     2dup min -rot  max ;
>
> > Being a standard part of the language however, it would be written in
> > assembly language. I could have this standardized, but not provide MIN
> > and MAX as part of the language, as they can easily be written in
> > terms of MINMAX (using DROP or NIP to get rid of the unwanted part).
> > I'm trying to make Strate Forth significantly smaller than ANS-Forth,
> > so reducing the number of primitive words is a good thing. In this
> > case, I not only reduce the number of primitives, but I provide a
> > primitive MINMAX that is useful in it own right.
>
> > This is MINMAX in VFX:
>
> > see minmax
> > MINMAX
> > ( 004C7AD0    8B5500 )                MOV       EDX, [EBP]
> > ( 004C7AD3    3BD3 )                  CMP       EDX, EBX
> > ( 004C7AD5    0F4FD3 )                CMOVNLE/G EDX, EBX
> > ( 004C7AD8    8B4D00 )                MOV       ECX, [EBP]
> > ( 004C7ADB    3BD9 )                  CMP       EBX, ECX
> > ( 004C7ADD    0F4CD9 )                CMOVL/NGE EBX, ECX
> > ( 004C7AE0    895500 )                MOV       [EBP], EDX
> > ( 004C7AE3    C3 )                    NEXT,
> > ( 20 bytes, 8 instructions )
>
> > That is pretty impressive optimization! If I were writing by hand, I
> > wouldn't have used the ECX register, but would have just used [EBP]
> > --- that would have been slightly shorter. Another possibility would
> > be to load ECX from EDX at the beginning, to avoid a memory access,
> > which might be slightly faster. Anyway, what VFX generated was pretty
> > close to optimal, so I'm impressed.
>
> > I would be interested in seeing what SwiftForth generates. LOL
>
> Wouldn't the following be potentially more efficient at run-time:
>
> : minmax ( a b -- min max) 2dup > if swap then ;
>
> What I'm thinking is, where a is already < b no stack manipulation
> (via min -rot and max) takes place. In the case where a > b then a
> simple swap is executed.
>
> I can imagine that the above might lead to a longer assembly code
> definition than your example, but if instrumented, I have a hunch the
> second example might be a little faster (though I know very little
> about the internal optimisations and machinations that take place deep
> within modern x86 processors, which is damned clever stuff -
> alchemy!). Certainly on my toy system, I'm sure the second example
> would be faster in all cases.
>
> Just thinkin' out loud...!

Here is a version of MINMAX in traditional assembly language:

minmax:                 ; a b -- min max
        mov edx, [ebp]
        cmp edx, ebx
        mov ecx, edx
        cmovg edx, ebx
        cmovg ebx, ecx
        mov [ebp], edx
        next

This is only 6 instructions, rather than 7, and it has only 2 memory
accesses, rather than 3 --- so it should be slightly more efficient
than what VFX generated --- but VFX was still pretty impressive.

I haven't tested this, because I haven't yet figured out how the
assembler works in VFX. I just wrote this in traditional assembly
format. I'm assuming that EBP is the parameter stack pointer and EBX
is the top value of the stack --- afaik, that is how VFX is
implemented.

Your method would be written like this:

minmax:                 ; a b -- min max
        cmp [ebp], ebx
        jg swap
        next

swap:                   ; a b -- b a
        xchg [ebp], ebx
        next

It is shorter not longer on the x86. It is also slower not faster
(because of the jump, which the branch-predictor will get wrong 50% of
the time).

On a 1980s-vintage processor such as your Forth system uses, this
shorter simpler method would be the best way (I wouldn't spend two
seconds considering anything else). Those processors don't have branch-
prediction --- life was a lot simpler in those days!

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

#19158

On Jan 25, 2:58 am, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> On Jan 22, 12:19 am, Mark Wills <forthfr...@gmail.com> wrote:
>
>
>
>
>
>
>
>
>
> > On Jan 22, 3:57 am, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
>
> > > On Jan 14, 12:04 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
>
> > > > : sq ( n -- n² ) dup * ;
> > > > : g ( a b c -- n )  2dup max sq >r min max sq r> + ;
>
> > > That is the way that I would write it. This is perhaps the first time
> > > in which Paysan has written code that I thought was good.
>
> > > This solution reminds me somewhat of that puzzle in which the guy is
> > > transporting a cannibal, a Christian and a bag of sugar across a
> > > river. If left alone, the cannibal will eat the Christian, and the
> > > Christian will eat the sugar, but the cannibal won't eat the sugar.
>
> > > It occurs to me that it might be useful in Strate Forth if I had a
> > > primitive called MINMAX that does this:
>
> > > : minmax ( a b -- min max )
> > >     2dup min -rot  max ;
>
> > > Being a standard part of the language however, it would be written in
> > > assembly language. I could have this standardized, but not provide MIN
> > > and MAX as part of the language, as they can easily be written in
> > > terms of MINMAX (using DROP or NIP to get rid of the unwanted part).
> > > I'm trying to make Strate Forth significantly smaller than ANS-Forth,
> > > so reducing the number of primitive words is a good thing. In this
> > > case, I not only reduce the number of primitives, but I provide a
> > > primitive MINMAX that is useful in it own right.
>
> > > This is MINMAX in VFX:
>
> > > see minmax
> > > MINMAX
> > > ( 004C7AD0    8B5500 )                MOV       EDX, [EBP]
> > > ( 004C7AD3    3BD3 )                  CMP       EDX, EBX
> > > ( 004C7AD5    0F4FD3 )                CMOVNLE/G EDX, EBX
> > > ( 004C7AD8    8B4D00 )                MOV       ECX, [EBP]
> > > ( 004C7ADB    3BD9 )                  CMP       EBX, ECX
> > > ( 004C7ADD    0F4CD9 )                CMOVL/NGE EBX, ECX
> > > ( 004C7AE0    895500 )                MOV       [EBP], EDX
> > > ( 004C7AE3    C3 )                    NEXT,
> > > ( 20 bytes, 8 instructions )
>
> > > That is pretty impressive optimization! If I were writing by hand, I
> > > wouldn't have used the ECX register, but would have just used [EBP]
> > > --- that would have been slightly shorter. Another possibility would
> > > be to load ECX from EDX at the beginning, to avoid a memory access,
> > > which might be slightly faster. Anyway, what VFX generated was pretty
> > > close to optimal, so I'm impressed.
>
> > > I would be interested in seeing what SwiftForth generates. LOL
>
> > Wouldn't the following be potentially more efficient at run-time:
>
> > : minmax ( a b -- min max) 2dup > if swap then ;
>
> > What I'm thinking is, where a is already < b no stack manipulation
> > (via min -rot and max) takes place. In the case where a > b then a
> > simple swap is executed.
>
> > I can imagine that the above might lead to a longer assembly code
> > definition than your example, but if instrumented, I have a hunch the
> > second example might be a little faster (though I know very little
> > about the internal optimisations and machinations that take place deep
> > within modern x86 processors, which is damned clever stuff -
> > alchemy!). Certainly on my toy system, I'm sure the second example
> > would be faster in all cases.
>
> > Just thinkin' out loud...!
>
> Here is a version of MINMAX in traditional assembly language:
>
> minmax:                 ; a b -- min max
>         mov edx, [ebp]
>         cmp edx, ebx
>         mov ecx, edx
>         cmovg edx, ebx
>         cmovg ebx, ecx
>         mov [ebp], edx
>         next
>
> This is only 6 instructions, rather than 7, and it has only 2 memory
> accesses, rather than 3 --- so it should be slightly more efficient
> than what VFX generated --- but VFX was still pretty impressive.
>
> I haven't tested this, because I haven't yet figured out how the
> assembler works in VFX. I just wrote this in traditional assembly
> format. I'm assuming that EBP is the parameter stack pointer and EBX
> is the top value of the stack --- afaik, that is how VFX is
> implemented.
>
> Your method would be written like this:
>
> minmax:                 ; a b -- min max
>         cmp [ebp], ebx
>         jg swap
>         next
>
> swap:                   ; a b -- b a
>         xchg [ebp], ebx
>         next
>
> It is shorter not longer on the x86. It is also slower not faster
> (because of the jump, which the branch-predictor will get wrong 50% of
> the time).

But by far and away the killer is the XCHG, which is horrendously slow
as it has an implied LOCK due to the memory reference.

>
> On a 1980s-vintage processor such as your Forth system uses, this
> shorter simpler method would be the best way (I wouldn't spend two
> seconds considering anything else). Those processors don't have branch-
> prediction --- life was a lot simpler in those days!

XCHG is a huge latency; the P4 takes in excess of 100 cycles. It
exceeds the cost of a jump by at least an order of magnitude.
http://www.agner.org/optimize/instruction_tables.pdf

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

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

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

csiph-web