Re: 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	Re: Optimal comparisons for m maximums from n items (was Re: revisiting a prgramming problem)
Date	2014-10-25 18:54 +0100
Organization	A noiseless patient Spider
Message-ID	<m2go4t$ppc$1@dont-email.me> (permalink)
References	<m28hte$gie$1@dont-email.me> <78081413938433@frunobulax.edu> <544a2a5e$0$6868$e4fe514c@dreader36.news.xs4all.nl> <m2dr99$60s$1@dont-email.me> <544b5ef4$0$15934$e4fe514c@dreader35.news.xs4all.nl>

Show all headers | View raw

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.

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