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

Groups > comp.lang.forth > #34131

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

From "Alex McDonald" <blog@rivadpm.com>
Newsgroups comp.lang.forth
Subject Optimal comparisons for m maximums from n items (was Re: revisiting a prgramming problem)
Date 2014-10-24 16:29 +0100
Organization A noiseless patient Spider
Message-ID <m2dr99$60s$1@dont-email.me> (permalink)
References <m28hte$gie$1@dont-email.me> <78081413938433@frunobulax.edu> <544a2a5e$0$6868$e4fe514c@dreader36.news.xs4all.nl>

Show all headers | View raw

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.

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web