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

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

revisiting a prgramming problem

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

Contents

  revisiting a prgramming problem gavino_himself <visploveslisp@gmail.com> - 2014-10-14 15:55 -0700
    Re: revisiting a prgramming problem hughaguilar96@yahoo.com - 2014-10-14 18:52 -0700
      Re: revisiting a prgramming problem Hans Bezemer <the.beez.speaks@gmail.com> - 2014-10-21 17:58 +0200
        Re: revisiting a prgramming problem Paul Rubin <no.email@nospam.invalid> - 2014-10-21 09:09 -0700
          Re: revisiting a prgramming problem Hans Bezemer <the.beez.speaks@gmail.com> - 2014-10-21 22:18 +0200
            Re: revisiting a prgramming problem rickman <gnuarm@gmail.com> - 2014-10-23 15:44 -0400
              Re: revisiting a prgramming problem "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-23 17:01 -0400
              Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-11-08 21:33 -0800
                Re: revisiting a prgramming problem rickman <gnuarm@gmail.com> - 2014-11-29 20:40 -0500
                  Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-12-01 22:43 -0800
                    Re: revisiting a prgramming problem rickman <gnuarm@gmail.com> - 2014-12-02 02:47 -0500
                      Re: revisiting a prgramming problem Paul E Bennett <Paul_E.Bennett@topmail.co.uk> - 2014-12-02 11:53 +0000
                      Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-12-02 05:23 -0800
                        Re: revisiting a prgramming problem rickman <gnuarm@gmail.com> - 2014-12-02 09:01 -0500
          Re: revisiting a prgramming problem Hans Bezemer <the.beez.speaks@gmail.com> - 2014-10-21 22:25 +0200
            Re: revisiting a prgramming problem Paul Rubin <no.email@nospam.invalid> - 2014-10-21 16:10 -0700
              Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-11-08 21:41 -0800
          Re: revisiting a prgramming problem Hans Bezemer <the.beez.speaks@gmail.com> - 2014-10-21 22:30 +0200
            Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-12-01 22:45 -0800
          Re: revisiting a prgramming problem Hans Bezemer <the.beez.speaks@gmail.com> - 2014-10-21 23:04 +0200
        Re: revisiting a prgramming problem Mark Wills <markwills1970@gmail.com> - 2014-10-21 10:17 -0700
          Re: revisiting a prgramming problem "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-22 02:13 -0400
            Re: revisiting a prgramming problem Paul Rubin <no.email@nospam.invalid> - 2014-10-21 23:26 -0700
              Re: revisiting a prgramming problem "Alex McDonald" <blog@rivadpm.com> - 2014-10-22 16:18 +0100
                Re: revisiting a prgramming problem mhx@iae.nl (Marcel Hendrix) - 2014-10-22 21:27 +0200
                  Re: revisiting a prgramming problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-24 10:30 +0000
                    Optimal comparisons for m maximums from n items  (was Re: revisiting a prgramming problem) "Alex McDonald" <blog@rivadpm.com> - 2014-10-24 16:29 +0100
                      Re: Optimal comparisons for m maximums from n items  (was Re: revisiting a prgramming problem) albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-25 08:27 +0000
                        Re: Optimal comparisons for m maximums from n items (was Re: revisiting a prgramming problem) "Alex McDonald" <blog@rivadpm.com> - 2014-10-25 18:54 +0100
                    Re: revisiting a prgramming problem mhx@iae.nl (Marcel Hendrix) - 2014-10-25 13:28 +0200
                    Re: revisiting a prgramming problem mhx@iae.nl (Marcel Hendrix) - 2014-10-25 14:28 +0200
                    Re: revisiting a prgramming problem mhx@iae.nl (Marcel Hendrix) - 2014-10-25 15:17 +0200
              Re: revisiting a prgramming problem Gerry Jackson <spam@qlikz.org> - 2014-10-22 21:57 +0100
                Re: revisiting a prgramming problem Paul Rubin <no.email@nospam.invalid> - 2014-10-22 14:06 -0700
                  Re: revisiting a prgramming problem Bernd Paysan <bernd.paysan@gmx.de> - 2014-10-23 00:03 +0200
                  Re: revisiting a prgramming problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-23 14:46 +0000
                    Re: revisiting a prgramming problem Paul Rubin <no.email@nospam.invalid> - 2014-10-23 08:16 -0700
                    Re: revisiting a prgramming problem "Alex McDonald" <blog@rivadpm.com> - 2014-10-23 19:21 +0100
                      Re: revisiting a prgramming problem "Alex McDonald" <blog@rivadpm.com> - 2014-10-23 20:02 +0100
                        Re: revisiting a prgramming problem albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-10-23 20:29 +0000
                    Re: revisiting a prgramming problem Coos Haak <chforth@hccnet.nl> - 2014-10-23 22:23 +0200
                Re: revisiting a prgramming problem awegel@arcor.de (Alexander Wegel) - 2014-10-23 00:36 +0200
                  Re: revisiting a prgramming problem Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-10-24 10:44 +0100
                Re: revisiting a prgramming problem hughaguilar96@yahoo.com - 2014-10-22 17:26 -0700
                  Re: revisiting a prgramming problem Michael Barry <barrym95838@yahoo.com> - 2014-10-23 00:02 -0700
            Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-11-08 23:10 -0800
          Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-11-08 21:42 -0800
    Re: revisiting a prgramming problem Roger Levy <roger.levy@gmail.com> - 2014-10-15 08:18 -0700
      Re: revisiting a prgramming problem Roger Levy <roger.levy@gmail.com> - 2014-10-15 08:18 -0700
        Re: revisiting a prgramming problem november.nihal@gmail.com - 2014-10-15 08:57 -0700
        Re: revisiting a prgramming problem Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-10-15 17:10 +0100
        Re: revisiting a prgramming problem "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-17 21:53 -0400
      Re: revisiting a prgramming problem Roger Levy <roger.levy@gmail.com> - 2014-10-15 08:19 -0700
    Re: revisiting a prgramming problem awegel@arcor.de (Alexander Wegel) - 2014-10-22 00:30 +0200
      Re: revisiting a prgramming problem hughaguilar96@yahoo.com - 2014-10-21 16:07 -0700
        Re: revisiting a prgramming problem awegel@arcor.de (Alexander Wegel) - 2014-10-22 03:23 +0200
          Re: revisiting a prgramming problem "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-22 02:15 -0400
            Re: revisiting a prgramming problem awegel@arcor.de (Alexander Wegel) - 2014-10-22 12:52 +0200
          Re: revisiting a prgramming problem hughaguilar96@yahoo.com - 2014-10-22 17:19 -0700
            Re: revisiting a prgramming problem awegel@arcor.de (Alexander Wegel) - 2014-10-23 16:10 +0200
        Re: revisiting a prgramming problem "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-22 02:14 -0400
        Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-11-08 23:21 -0800
        Re: revisiting a prgramming problem "WJ" <w_a_x_man@yahoo.com> - 2014-12-06 02:34 +0000
        Re: revisiting a prgramming problem "WJ" <w_a_x_man@yahoo.com> - 2014-12-27 08:00 +0000
          Re: revisiting a prgramming problem Mark Wills <markwills1970@gmail.com> - 2014-12-27 05:15 -0800
    Re: revisiting a prgramming problem "WJ" <w_a_x_man@yahoo.com> - 2014-11-29 17:20 +0000
      Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-11-29 12:00 -0800
      Re: revisiting a prgramming problem "WJ" <w_a_x_man@yahoo.com> - 2014-12-02 16:15 +0000
    Re: revisiting a prgramming problem Paul Sephton <prsephton@gmail.com> - 2014-12-02 05:06 -0800
      Re: revisiting a prgramming problem Paul Sephton <prsephton@gmail.com> - 2014-12-02 05:14 -0800
      Re: revisiting a prgramming problem the_gavino_himself <visphatesjava@gmail.com> - 2014-12-02 05:24 -0800

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

#34063

On Tuesday, 21 October 2014 16:57:19 UTC+1, The Beez  wrote:
After you have this first program written, and everybody is cheering for
you, write another program that takes *2* numbers and squares each of them,
adding the products together. Then you are done!
> 
> Duh.. : sumofsquare over max dup * >r max dup * r> + ;
> 
> 
> 
> Hans Bezemer

That's not how I interpret Hugh's challenge. It says take two numbers, not the highest two of three. Perhaps I'm reading it wrong...

: sos ( a b -- n ) dup * >r dup * r> + ;

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

#34082

On Tue, 21 Oct 2014 13:17:45 -0400, Mark Wills <markwills1970@gmail.com>  
wrote:
> On Tuesday, 21 October 2014 16:57:19 UTC+1, The Beez  wrote:

<HA>
> After you have this first program written, and everybody is cheering
> for you, write another program that takes *2* numbers and squares
> each of them, adding the products together. Then you are done!
</HA>

>>
>> Duh.. : sumofsquare over max dup * >r max dup * r> + ;
>>
> That's not how I interpret Hugh's challenge. It says take two numbers,  
> not the highest two of three. Perhaps I'm reading it wrong...
>
> : sos ( a b -- n ) dup * >r dup * r> + ;

Hugh broke the problem into two parts:

1) maximum two of three
2) sum of squares of results of #1

That was his brain teaser. #1 really needs to be 2 parts.

AISI, it's really a three part problem because the three
values really need to be sorted first, largest to smallest,
to _safely_ remove or drop the smallest, thereby leaving
the two largest.

: 2SORT 2DUP < IF SWAP THEN ;
: 2MAX 2SORT ROT 2SORT DROP ;
: SQSUM 2MAX DUP * SWAP DUP * + ;

Expanded, it's only a hair longer longer than the one
of Beez' which I think works correctly.  It doesn't need
the return stack.  And, you might be able to work MAX in
for one of the 2SORTS that way, shortening it to the same
length or thereabouts.


Rod Pemberton

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

#34086

"Rod Pemberton" <buzzoff@nonamewhichexists.cmm> writes:
> : 2SORT 2DUP < IF SWAP THEN ;
> : 2MAX 2SORT ROT 2SORT DROP ;
> : SQSUM 2MAX DUP * SWAP DUP * + ;
> It doesn't need the return stack.  And, you might be able to work MAX
> in for one of the 2SORTS that way

MAX of course wraps a conditional, and ROT is most straightforwardly
implemented with something like

  : rot ( a b c -- b c a ) >r swap r> swap ;

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

#34089

on 22/10/2014 07:25:58, Paul Rubin wrote:
> "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> writes:
>> : 2SORT 2DUP < IF SWAP THEN ;
>> : 2MAX 2SORT ROT 2SORT DROP ;
>> : SQSUM 2MAX DUP * SWAP DUP * + ;
>> It doesn't need the return stack.  And, you might be able to work MAX
>> in for one of the 2SORTS that way
> 
> MAX of course wraps a conditional, and ROT is most straightforwardly
> implemented with something like
> 
> : rot ( a b c -- b c a ) >r swap r> swap ;
> 

Or (annoying several others in the process)

: rot {: a b c :} b c a ;

Optimization should turn both into the same code; it's maxiamlly 4 moves
and minimally none if moves are optimised away.

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

#34092

"Alex McDonald" writes Re: revisiting a prgramming problem
[..]
> Or (annoying several others in the process)

> : rot {: a b c :} b c a ;

> Optimization should turn both into the same code; it's maxiamlly 4 moves
> and minimally none if moves are optimised away.

The moves would be dropped when ROT is used, not in ROT itself.

Hopefully annoying all trolls and a few local-haters ...

-marcel

-- -----------
ANEW -optims 

     \ *** note equivalent code 

: rot2 ( a b c -- b c a ) >r swap r> swap ;
FORTH> ' rot2 idis
$01221480  : rot2
$0122148A  pop           rbx
$0122148B  pop           rdi
$0122148C  pop           rax
$0122148D  push          rdi
$0122148E  push          rbx
$0122148F  push          rax
$01221490  ;

: rot3 ( a b c -- b c a ) PARAMS| a b c |  b c a ;
FORTH> ' rot3 idis
$01223D00  : rot3
$01223D0A  pop           rbx
$01223D0B  pop           rdi
$01223D0C  pop           rax
$01223D0D  push          rdi
$01223D0E  push          rbx
$01223D0F  push          rax
$01223D10  ;

      \ *** various sum-of-squares proposals

      \ 28 ins, 2 compares

: 2SORT 2DUP < IF SWAP THEN ;
: 2MAX 2SORT ROT 2SORT DROP ;
: SQSUM 2MAX DUP * SWAP DUP * + ;

FORTH> ' SQSUM idis
$01223EC0  : SQSUM
$01223ECA  pop           rbx
$01223ECB  pop           rdi
$01223ECC  cmp           rbx, rdi
$01223ECF  push          rdi
$01223ED0  jle           $01223EDE offset NEAR
$01223ED6  pop           rdi
$01223ED7  mov           rcx, rbx
$01223EDA  mov           rbx, rdi
$01223EDD  push          rcx
$01223EDE  pop           rdi
$01223EDF  pop           rax
$01223EE0  cmp           rax, rbx
$01223EE3  push          rdi
$01223EE4  push          rbx
$01223EE5  mov           rbx, rcx
$01223EE8  mov           rcx, rax
$01223EEB  mov           rbx, rcx
$01223EEE  jle           $01223EFC offset NEAR
$01223EF4  pop           rdi
$01223EF5  mov           rcx, rbx
$01223EF8  mov           rbx, rdi
$01223EFB  push          rcx
$01223EFC  pop           rbx
$01223EFD  imul          rbx, rbx
$01223F01  pop           rdi
$01223F02  imul          rdi, rdi
$01223F06  lea           rbx, [rbx rdi*1] qword
$01223F0A  push          rbx
$01223F0B  ;

      \ 30 ins, 2 jumps

: ?swap ( a b -- smaller bigger ) 2dup > if swap then ;
: 2biggest ( a b c -- n n ) ?swap >r ?swap nip r> ;
: ^2 ( n -- n ) dup * ;
: sos ( a b c -- n ) 2biggest ^2 swap ^2 + ; \ Paul Rubin

FORTH> ' sos idis
$01224140  : sos
$0122414A  pop           rbx
$0122414B  pop           rdi
$0122414C  cmp           rbx, rdi
$0122414F  push          rdi
$01224150  jge           $0122415E offset NEAR
$01224156  pop           rdi
$01224157  mov           rcx, rbx
$0122415A  mov           rbx, rdi
$0122415D  push          rcx
$0122415E  pop           rdi
$0122415F  pop           rax
$01224160  cmp           rdi, rax
$01224163  lea           rbp, [rbp -8 +] qword
$01224167  mov           [rbp 0 +] qword, rbx
$0122416B  push          rax
$0122416C  mov           rbx, rcx
$0122416F  mov           rcx, rdi
$01224172  mov           rbx, rcx
$01224175  jge           $01224183 offset NEAR
$0122417B  pop           rdi
$0122417C  mov           rcx, rbx
$0122417F  mov           rbx, rdi
$01224182  push          rcx
$01224183  pop           rdi
$01224184  mov           rdi, [rbp 0 +] qword
$01224188  lea           rbp, [rbp 8 +] qword
$0122418C  imul          rdi, rdi
$01224190  imul          rbx, rbx
$01224194  lea           rbx, [rdi rbx*1] qword
$01224198  push          rbx
$01224199  ;

      \ 26 ins, 1 jump

: sumofsquare 2dup > if swap then over max dup * >r max dup * r> + ; \ Beez
FORTH> ' sumofsquare idis
$01224200  : sumofsquare
$0122420A  pop           rbx
$0122420B  pop           rdi
$0122420C  cmp           rbx, rdi
$0122420F  push          rdi
$01224210  jge           $0122421E offset NEAR
$01224216  pop           rdi
$01224217  mov           rcx, rbx
$0122421A  mov           rbx, rdi
$0122421D  push          rcx
$0122421E  mov           rdi, [rsp] qword
$01224222  mov           rcx, rbx
$01224225  mov           rbx, rdi
$01224228  cmp           rbx, rcx
$0122422B  cmovl         rbx, rcx
$0122422F  imul          rbx, rbx
$01224233  lea           rbp, [rbp -8 +] qword
$01224237  mov           [rbp 0 +] qword, rbx
$0122423B  pop           rbx
$0122423C  pop           rcx
$0122423D  cmp           rbx, rcx
$01224240  cmovl         rbx, rcx
$01224244  imul          rbx, rbx
$01224248  mov           rdi, [rbp 0 +] qword
$0122424C  lea           rbp, [rbp 8 +] qword
$01224250  lea           rbx, [rbx rdi*1] qword
$01224254  push          rbx
$01224255  ;

: msquare ( n -- d )  \ mixed-precision integer square
  dup m* ;

: minmax ( n1 n2 -- n1 n2 | n2 n1 )  \ bigger comes out atop
  2dup > if swap then ;

: msum_of_squares ( n1 n2 n3 -- d )  \ mixed-precision solution
  minmax >r        \ move bigger of n2 and n3 to r-stack
  max              \ discard smaller (=smallest overall) number
  msquare r> msquare d+  \ calculate result
; \ Alexander Wegel

      \ 35 ins, 1 jump and double precision output

FORTH> ' msum_of_squares idis
$012243C0  : msum_of_squares
$012243CA  pop           rbx
$012243CB  pop           rdi
$012243CC  cmp           rbx, rdi
$012243CF  push          rdi
$012243D0  jge           $012243DE offset NEAR
$012243D6  pop           rdi
$012243D7  mov           rcx, rbx
$012243DA  mov           rbx, rdi
$012243DD  push          rcx
$012243DE  lea           rbp, [rbp -8 +] qword
$012243E2  mov           [rbp 0 +] qword, rbx
$012243E6  pop           rbx
$012243E7  pop           rcx
$012243E8  cmp           rbx, rcx
$012243EB  cmovl         rbx, rcx
$012243EF  mov           rax, rbx
$012243F2  mov           rdi, rbx
$012243F5  xchg          rdx, rdi
$012243F8  imul          rdx
$012243FB  xchg          rdx, rdi
$012243FE  mov           rbx, [rbp 0 +] qword
$01224402  lea           rbp, [rbp 8 +] qword
$01224406  push          rax
$01224407  push          rdi
$01224408  mov           rcx, rbx
$0122440B  mov           rax, rcx
$0122440E  imul          rbx
$01224411  mov           rbx, rdx
$01224414  mov           rcx, rax
$01224417  pop           rdi
$01224418  pop           rax
$01224419  add           rax, rcx
$0122441C  adc           rbx, rdi
$0122441F  push          rax
$01224420  push          rbx
$01224421  ;

But the 'best' (defined as: no jumps/compares) is of course:

      \ 22 ins, 0 jumps

: sqr ( a -- a^2 ) dup * ;
: suosq ( a b c -- d ) 
  sqr swap sqr rot sqr 3dup ( -- a^2 b^2 c^2 a^2 b^2 c^2 )
  + >r + r> max 
    >r + r> max ;

FORTH> ' suosq idis
$01224E40  : suosq
$01224E4A  pop           rbx
$01224E4B  imul          rbx, rbx
$01224E4F  pop           rdi
$01224E50  imul          rdi, rdi
$01224E54  pop           rax
$01224E55  imul          rax, rax
$01224E59  push          rbx
$01224E5A  push          rdi
$01224E5B  lea           rbx, [rax rbx*1] qword
$01224E5F  push          rbx
$01224E60  lea           rbx, [rdi rax*1] qword
$01224E64  pop           rcx
$01224E65  cmp           rbx, rcx
$01224E68  cmovl         rbx, rcx
$01224E6C  pop           rdi
$01224E6D  pop           rax
$01224E6E  lea           rdi, [rax rdi*1] qword
$01224E72  push          rdi
$01224E73  pop           rcx
$01224E74  cmp           rbx, rcx
$01224E77  cmovl         rbx, rcx
$01224E7B  push          rbx
$01224E7C  ;

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

#34129

In article <78081413938433@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl> wrote:
<SNIP>
>
>But the 'best' (defined as: no jumps/compares) is of course:
>
>      \ 22 ins, 0 jumps
>
>: sqr ( a -- a^2 ) dup * ;
>: suosq ( a b c -- d )
>  sqr swap sqr rot sqr 3dup ( -- a^2 b^2 c^2 a^2 b^2 c^2 )
>  + >r + r> max
>    >r + r> max ;

Correct me of I'm wrong, but getting the squares first,
seems to fail if any of the numbers is negative.

>
>FORTH> ' suosq idis
>$01224E40  : suosq
>$01224E4A  pop           rbx
>$01224E4B  imul          rbx, rbx
>$01224E4F  pop           rdi
>$01224E50  imul          rdi, rdi
>$01224E54  pop           rax
>$01224E55  imul          rax, rax
>$01224E59  push          rbx
>$01224E5A  push          rdi
>$01224E5B  lea           rbx, [rax rbx*1] qword
>$01224E5F  push          rbx
>$01224E60  lea           rbx, [rdi rax*1] qword
>$01224E64  pop           rcx
>$01224E65  cmp           rbx, rcx
>$01224E68  cmovl         rbx, rcx
>$01224E6C  pop           rdi
>$01224E6D  pop           rax
>$01224E6E  lea           rdi, [rax rdi*1] qword
>$01224E72  push          rdi
>$01224E73  pop           rcx
>$01224E74  cmp           rbx, rcx
>$01224E77  cmovl         rbx, rcx
>$01224E7B  push          rbx
>$01224E7C  ;
>
>
>

As is usual with your benchmarks the conclusion fails.

What is your opinion, impression or advice based on all the
work you've done. (Not that it is not appreciated that you
present results in great detail, and be specific about
the Forth it runs on. )
-- 
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]

#34131 — Optimal comparisons for m maximums from n items (was Re: revisiting a prgramming problem)

on 24/10/2014 11:30:54,  wrote:
> In article <78081413938433@frunobulax.edu>, Marcel Hendrix
> <mhx@iae.nl> wrote: <SNIP>
>>
>>But the 'best' (defined as: no jumps/compares) is of course:
>>
>>      \ 22 ins, 0 jumps
>>
>>: sqr ( a -- a^2 ) dup * ;
>>: suosq ( a b c -- d )
>>  sqr swap sqr rot sqr 3dup ( -- a^2 b^2 c^2 a^2 b^2 c^2 )
>>  + >r + r> max
>>    >r + r> max ;
> 
> Correct me of I'm wrong, but getting the squares first,
> seems to fail if any of the numbers is negative.

I was expecting Marcel to express the sum of two squares so that the
double multiply x*x+y*y could be factored out to (x +iy)*(x-iy). That he
didn't find a way of expressing an imaginary number with the Intel
instruction set comes as a great disappointment. 

I am only kidding of course. 

Of more interest to me was the code that produced maximum 2 of 3 items.
This required 2 compares. For selecting the maximum 2 from 4 items, what
is the minimum number of compares?

And so on; for fn(n,m)=c where n=items, m=maximums and c=compares we have
fn(3,2)=2. Is there a general formula for fn (n,m) that gives an optimal
number of comparisons? Since it appears a modified form of a network
sort, I suspect the answer is no, since there's no method for generating
optimal network sorts.

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

#34133 — Re: Optimal comparisons for m maximums from n items (was Re: revisiting a prgramming problem)

In article <m2dr99$60s$1@dont-email.me>,
Alex McDonald <blog@rivadpm.com> wrote:
>on 24/10/2014 11:30:54,  wrote:
>> In article <78081413938433@frunobulax.edu>, Marcel Hendrix
>> <mhx@iae.nl> wrote: <SNIP>
>>>
>>>But the 'best' (defined as: no jumps/compares) is of course:
>>>
>>>      \ 22 ins, 0 jumps
>>>
>>>: sqr ( a -- a^2 ) dup * ;
>>>: suosq ( a b c -- d )
>>>  sqr swap sqr rot sqr 3dup ( -- a^2 b^2 c^2 a^2 b^2 c^2 )
>>>  + >r + r> max
>>>    >r + r> max ;
>>
>> Correct me of I'm wrong, but getting the squares first,
>> seems to fail if any of the numbers is negative.
>
>I was expecting Marcel to express the sum of two squares so that the
>double multiply x*x+y*y could be factored out to (x +iy)*(x-iy). That he
>didn't find a way of expressing an imaginary number with the Intel
>instruction set comes as a great disappointment.
>
>I am only kidding of course.
>
>Of more interest to me was the code that produced maximum 2 of 3 items.
>This required 2 compares. For selecting the maximum 2 from 4 items, what
>is the minimum number of compares?
>
>And so on; for fn(n,m)=c where n=items, m=maximums and c=compares we have
>fn(3,2)=2. Is there a general formula for fn (n,m) that gives an optimal
>number of comparisons? Since it appears a modified form of a network
>sort, I suspect the answer is no, since there's no method for generating
>optimal network sorts.
>

As usual this question has been asked before. Knuth TAO has a whole
section on this.

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]

#34138 — Re: Optimal comparisons for m maximums from n items (was Re: revisiting a prgramming problem)

on 25/10/2014 09:27:30,  wrote:
> In article <m2dr99$60s$1@dont-email.me>,
> Alex McDonald <blog@rivadpm.com> wrote:
>>on 24/10/2014 11:30:54,  wrote:
>>> In article <78081413938433@frunobulax.edu>, Marcel Hendrix
>>> <mhx@iae.nl> wrote: <SNIP>
>>>>
>>>>But the 'best' (defined as: no jumps/compares) is of course:
>>>>
>>>>      \ 22 ins, 0 jumps
>>>>
>>>>: sqr ( a -- a^2 ) dup * ;
>>>>: suosq ( a b c -- d )
>>>>  sqr swap sqr rot sqr 3dup ( -- a^2 b^2 c^2 a^2 b^2 c^2 )
>>>>  + >r + r> max
>>>>    >r + r> max ;
>>>
>>> Correct me of I'm wrong, but getting the squares first,
>>> seems to fail if any of the numbers is negative.
>>
>>I was expecting Marcel to express the sum of two squares so that the
>>double multiply x*x+y*y could be factored out to (x +iy)*(x-iy). That he
>>didn't find a way of expressing an imaginary number with the Intel
>>instruction set comes as a great disappointment.
>>
>>I am only kidding of course.
>>
>>Of more interest to me was the code that produced maximum 2 of 3 items.
>>This required 2 compares. For selecting the maximum 2 from 4 items, what
>>is the minimum number of compares?
>>
>>And so on; for fn(n,m)=c where n=items, m=maximums and c=compares we have
>>fn(3,2)=2. Is there a general formula for fn (n,m) that gives an optimal
>>number of comparisons? Since it appears a modified form of a network
>>sort, I suspect the answer is no, since there's no method for generating
>>optimal network sorts.
>>
> 
> As usual this question has been asked before. Knuth TAO has a whole
> section on this.
> 
> Groetjes Albert

Thanks for the reminder. Vol 3 Sorting & Searching 5.3.3 Minimum
comparison selection.

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

#34134

m.a.m.hendrix@tue.nl writes Re: The magical number seven (was: Tiny regular expressions code)
[..]
>> >Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
[..]
>> An informal examination of one of Moore's applications shows that he
>> averages seven references, including both words and numbers, per
>> definition.

> I'll have a look in 'Footsteps in an empty valley' and/or the Weasel 
> manual (full kernel), tonight. This should be easy to (dis)prove.

'Footsteps in an empty valley'

-DIGIT \ 27 words
NUMBER \ 53 words
WORD   \ 48 words
QUIT   \ 14 words
BAUD   \ 17 words
SPACES \ 13 words 
M/MOD  \ 10 words
FILL   \ 15 words
SCAN   \ 12 words
THRU   \ 12 words
]      \ 46 words
@      \ 11 words ( optimized)

( here I stopped )

I can't find any trace of words that are obviously factored out of larger
definitions. All words perform a definite function.
Not all words have a stack picture. No words have empty stack pictures. Only
the data stack is commented, input stream and rack are not.

I counted ':', "name" and ';' as words.

The listing I used for counting was the  metacompiler for the NOVIX.
I didn't count the very long optimizer words (50 .. 72 words, 
unfactored :-), and also not artefacts of metacompiling like : @ @ ; .

-marcel

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

#34135

albert@spenarnc.xs4all.nl (Albert van der Horst) writes Re: revisiting a prgramming problem

> In article <78081413938433@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl> wrote:
> <SNIP>

>>But the 'best' (defined as: no jumps/compares) is of course:

>>      \ 22 ins, 0 jumps
>>
>>: sqr ( a -- a^2 ) dup * ;
>>: suosq ( a b c -- d )
>>  sqr swap sqr rot sqr 3dup ( -- a^2 b^2 c^2 a^2 b^2 c^2 )
>>  + >r + r> max
>>    >r + r> max ;

> Correct me of I'm wrong, but getting the squares first,
> seems to fail if any of the numbers is negative.

Who specified that? Anyway, it is only three instructions more:

: suosq ( z y x -- a )
  2dup 
  MAX SQR -rot ( -- z u^2 y x )
  MIN rot  
  MAX SQR + ;

\ 25 ins, no jumps
FORTH> ' suosq idis
$01229480  : sumsq
$0122948A  pop           rbx
$0122948B  mov           rdi, [rsp] qword
$0122948F  push          rbx
$01229490  mov           rcx, rdi
$01229493  cmp           rbx, rcx
$01229496  cmovl         rbx, rcx
$0122949A  imul          rbx, rbx
$0122949E  pop           rdi
$0122949F  pop           rax
$012294A0  push          rbx
$012294A1  mov           rbx, rdi
$012294A4  mov           rcx, rax
$012294A7  cmp           rbx, rcx
$012294AA  cmovg         rbx, rcx
$012294AE  pop           rdi
$012294AF  pop           rax
$012294B0  push          rdi
$012294B1  mov           rcx, rbx
$012294B4  mov           rbx, rax
$012294B7  cmp           rbx, rcx
$012294BA  cmovl         rbx, rcx
$012294BE  imul          rbx, rbx
$012294C2  pop           rdi
$012294C3  lea           rbx, [rdi rbx*1] qword
$012294C7  push          rbx
$012294C8  ;


> As is usual with your benchmarks the conclusion fails.

> What is your opinion, impression or advice based on all the
> work you've done. (Not that it is not appreciated that you
> present results in great detail, and be specific about
> the Forth it runs on. )

My advice is to write critical code as straightforward and clearly as 
possible. Current Forth compilers use all the tricks in the book 
(as demonstrated - remove all stack words, remove branches, remove flags). 
You can't beat these compilers with a CODE definition unless your first 
name is Terje. 
However, always try a few algorithms and check the output of the compiler 
for critical work. For example, I rejected a few algorithms that used 
locals because there were more items than the current iForth compiler 
can handle.

The basic assumption up to now has been that conditional jumps are 
bad for the run-time. I didn't test that here, and it might very well be
wrong. Anyway, I suspect the difference will be so small that it only 
matters for those that are using optimizing compilers (and then in only 
extreme cases).

-marcel

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

#34136

mhx@iae.nl (Marcel Hendrix) wrote Re: revisiting a prgramming problem

> albert@spenarnc.xs4all.nl (Albert van der Horst) writes Re: revisiting a prgramming problem
[..]
> The basic assumption up to now has been that conditional jumps are 
> bad for the run-time. I didn't test that here, and it might very well be
> wrong. Anyway, I suspect the difference will be so small that it only 
> matters for those that are using optimizing compilers (and then in only 
> extreme cases).

Testing tells me it is a real effect, and a biggie for our snippet.

ANEW -sumsq

: SQR ( u -- u^2 ) DUP * ;

: suosq ( z y x -- a )
  2dup 
  MAX SQR -rot ( -- z u^2 y x )
  MIN rot  
  MAX SQR + ;

: 2SORT 2DUP < IF SWAP THEN ;
: 2MAX 2SORT ROT 2SORT DROP ;
: SQSUM 2MAX DUP * SWAP DUP * + ;

#1000000000 VALUE #times
: BENCH ( -- )
	1 2 3 LOCALS| z y x |
	CR ." suosq random : "  TIMER-RESET #times 0 DO  RANDOM TO x RANDOM TO y RANDOM TO z  x y z suosq drop  LOOP .ELAPSED
	CR ." suosq fixed  : "  TIMER-RESET #times 0 DO  RANDOM drop RANDOM drop RANDOM drop  x y z suosq drop  LOOP .ELAPSED
	CR ." sqsum random : "  TIMER-RESET #times 0 DO  RANDOM TO x RANDOM TO y RANDOM TO z  x y z sqsum drop  LOOP .ELAPSED 
	CR ." sqsum fixed  : "  TIMER-RESET #times 0 DO  RANDOM drop RANDOM drop RANDOM drop  x y z sqsum drop  LOOP .ELAPSED ;

FORTH> bench cr bench cr bench
suosq random : 10.135 seconds elapsed.
suosq fixed  : 7.043 seconds elapsed.
sqsum random : 13.461 seconds elapsed.
sqsum fixed  : 7.031 seconds elapsed.

suosq random : 7.498 seconds elapsed.
suosq fixed  : 7.043 seconds elapsed.
sqsum random : 13.464 seconds elapsed.
sqsum fixed  : 7.026 seconds elapsed.

suosq random : 7.501 seconds elapsed.
suosq fixed  : 7.040 seconds elapsed.
sqsum random : 13.469 seconds elapsed.
sqsum fixed  : 7.085 seconds elapsed. ok

After the cache warms up, the branchless code (suosq) runs at ~7 seconds, 
independent from it being fed unpredictable or predictable data. The 
branching code (sqsum) is about twice slower with random data and the 
same speed as suosq for predictable data.

-marcel

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

#34095

On 22/10/2014 07:26, Paul Rubin wrote:
> "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> writes:
>> : 2SORT 2DUP < IF SWAP THEN ;
>> : 2MAX 2SORT ROT 2SORT DROP ;
>> : SQSUM 2MAX DUP * SWAP DUP * + ;
>> It doesn't need the return stack.  And, you might be able to work MAX
>> in for one of the 2SORTS that way
>
> MAX of course wraps a conditional

'Of course'? In practice you are almost certainly correct but MAX (and 
MIN) can be implemented in ANS Forth without an IF. For amusement I 
wondered how many ways it could be done and came up with the following, 
all using a boolean as a number e.g.

: max 2dup < 1+ pick nip nip ;

: max 2dup > 1+ roll drop ;

: selxt does> cell+ swap cells + @ execute ;
create minmax ' drop , ' nip , selxt
: max 2dup > minmax ;
: min 2dup < minmax ;

: max s" swap drop" 2over > -4 * /string evaluate ;

2variable n2n1
: max 2dup n2n1 2! > negate cells n2n1 + @ ;

Any more?

I'm not saying these are better than the usual definition just 
demonstrating what's possible.

It's worth looking at chapter 8 of Thinking Forth.


-- 
Gerry

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

#34096

Gerry Jackson <spam@qlikz.org> writes:
>> MAX of course wraps a conditional
> 'Of course'? In practice you are almost certainly correct but MAX (and
> MIN) can be implemented in ANS Forth without an IF...
> : max 2dup < 1+ pick nip nip ;

How do you think < works?

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

#34099

Paul Rubin wrote:

> Gerry Jackson <spam@qlikz.org> writes:
>>> MAX of course wraps a conditional
>> 'Of course'? In practice you are almost certainly correct but MAX (and
>> MIN) can be implemented in ANS Forth without an IF...
>> : max 2dup < 1+ pick nip nip ;
> 
> How do you think < works?

Many CPUs have instructions to set flags in registers - these instructions 
don't have the same problem as a branch, as they just set this single 
register, but don't alter the control flow.  Early Forths had

: < ( a b -- flag ) - s>d nip ;
: > swap < ;

This is a wraparound <, so it's not working for the entire number space, but 
it's certainly branch-less, as long as you can implement s>d branchless (you 
often can).

Next: use mux to select branchless:

: mux ( a b bitmap -- muxed )
  tuck invert and >r and r> or ;
: max ( a b -- max ) 2dup > mux ;

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

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

#34111

In article <7xoat37r0s.fsf@ruckus.brouhaha.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>Gerry Jackson <spam@qlikz.org> writes:
>>> MAX of course wraps a conditional
>> 'Of course'? In practice you are almost certainly correct but MAX (and
>> MIN) can be implemented in ANS Forth without an IF...
>> : max 2dup < 1+ pick nip nip ;
>
>How do you think < works?

Typical code for 32 bits Pentium (from yourforth):

     header  _less_,   _less_+5*cw, 0, 0, lastlink, "<"
         pop     edx
         pop     ebx
         xor     eax,eax
         cmp     ebx,edx
         setl    al       ; Set bit to "less"
         neg     eax
         push    eax
         next

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]

#34114

albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
>          cmp     ebx,edx
>          setl    al       ; Set bit to "less"

Oh, good point.  Thanks.

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

#34117

on 23/10/2014 15:46:13,  wrote:
> In article <7xoat37r0s.fsf@ruckus.brouhaha.com>,
> Paul Rubin  <no.email@nospam.invalid> wrote:
>>Gerry Jackson <spam@qlikz.org> writes:
>>>> MAX of course wraps a conditional
>>> 'Of course'? In practice you are almost certainly correct but MAX (and
>>> MIN) can be implemented in ANS Forth without an IF...
>>> : max 2dup < 1+ pick nip nip ;
>>
>>How do you think < works?
> 
> Typical code for 32 bits Pentium (from yourforth):
> 
> header  _less_,   _less_+5*cw, 0, 0, lastlink, "<"
> pop     edx
> pop     ebx
> xor     eax,eax
> cmp     ebx,edx
> setl    al       ; Set bit to "less"
> neg     eax
> push    eax
> next
> 
> Groetjes Albert

This requires only 2 registers & 5 instructions. It may be faster.

                pop     ebx
                or      eax, -1
                cmp     [esp], ebx
                mov     [esp], 0
                cmovl   [esp], eax

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

#34118

on 23/10/2014 19:21:12, "Alex McDonald" wrote:
> on 23/10/2014 15:46:13,  wrote:
>> In article <7xoat37r0s.fsf@ruckus.brouhaha.com>,
>> Paul Rubin  <no.email@nospam.invalid> wrote:
>>>Gerry Jackson <spam@qlikz.org> writes:
>>>>> MAX of course wraps a conditional
>>>> 'Of course'? In practice you are almost certainly correct but MAX (and
>>>> MIN) can be implemented in ANS Forth without an IF...
>>>> : max 2dup < 1+ pick nip nip ;
>>>
>>>How do you think < works?
>>
>> Typical code for 32 bits Pentium (from yourforth):
>>
>> header  _less_,   _less_+5*cw, 0, 0, lastlink, "<"
>> pop     edx
>> pop     ebx
>> xor     eax,eax
>> cmp     ebx,edx
>> setl    al       ; Set bit to "less"
>> neg     eax
>> push    eax
>> next
>>
>> Groetjes Albert
> 
> This requires only 2 registers & 5 instructions. It may be faster.
> 
> pop     ebx
> or      eax, -1
> cmp     [esp], ebx
> mov     [esp], 0
> cmovl   [esp], eax

Sorry, due to a cut/paste/modify of code where the target operand of the
CMOVL was cached in a register, the above is wrong. CMOVxx can't take a
target memory operand. It should be

                pop     ebx
                or      eax, -1
                xor     ecx, ecx
                cmp     [esp], ebx
                cmovl   ecx, eax
                mov     [esp], ecx

which is a much less interesting 3 registers and 6 instructions.

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

#34121

In article <m2bjcd$cs1$1@dont-email.me>,
Alex McDonald <blog@rivadpm.com> wrote:
>on 23/10/2014 19:21:12, "Alex McDonald" wrote:
>> on 23/10/2014 15:46:13,  wrote:
>>> In article <7xoat37r0s.fsf@ruckus.brouhaha.com>,
>>> Paul Rubin  <no.email@nospam.invalid> wrote:
>>>>Gerry Jackson <spam@qlikz.org> writes:
>>>>>> MAX of course wraps a conditional
>>>>> 'Of course'? In practice you are almost certainly correct but MAX (and
>>>>> MIN) can be implemented in ANS Forth without an IF...
>>>>> : max 2dup < 1+ pick nip nip ;
>>>>
>>>>How do you think < works?
>>>
>>> Typical code for 32 bits Pentium (from yourforth):
>>>
>>> header  _less_,   _less_+5*cw, 0, 0, lastlink, "<"
>>> pop     edx
>>> pop     ebx
>>> xor     eax,eax
>>> cmp     ebx,edx
>>> setl    al       ; Set bit to "less"
>>> neg     eax
>>> push    eax
>>> next
>>>
>>> Groetjes Albert
>>
>> This requires only 2 registers & 5 instructions. It may be faster.
>>
>> pop     ebx
>> or      eax, -1
>> cmp     [esp], ebx
>> mov     [esp], 0
>> cmovl   [esp], eax
>
>Sorry, due to a cut/paste/modify of code where the target operand of the
>CMOVL was cached in a register, the above is wrong. CMOVxx can't take a
>target memory operand. It should be
>
>                pop     ebx
>                or      eax, -1
>                xor     ecx, ecx
>                cmp     [esp], ebx
>                cmovl   ecx, eax
>                mov     [esp], ecx
>
>which is a much less interesting 3 registers and 6 instructions.

More important to me is:
1. I count pop's and pushes to derive the stack effect
2. cmovxx instructions require a special skill set,
  which my Pentium 90 has not.

On modern processors CMOV is of course the way to go.
(DEC Alpha , ARM, and nowadays the i86 )

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]

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

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

csiph-web