Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: max of 3
Date: Sat, 29 Aug 2020 05:19:38 -0700
Organization: A noiseless patient Spider
Lines: 127
Message-ID: <861rjpabl1.fsf@linuxsc.com>
References: <da872028-3be4-4d30-8617-3a3c74c9e97fn@googlegroups.com> <7d71a0a9-5db4-44ea-b2e7-50a41bd846dao@googlegroups.com> <86h7srbv7p.fsf@linuxsc.com> <2bdc9afb-769d-4bce-a6f3-372cc0c22f30o@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="fa701d7c3dfeeb40f6257600f67e6301"; logging-data="16695"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Lg43od07whHG+6JiUF7DD6Lv1Lj80Zgs="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:uIEAtyvZeLm3FhNgBHxF5dhEDRc= sha1:PF3OslHKPsi2ukPVHtNPnODUIIs=
Xref: csiph.com comp.lang.c:154168

luser droog <luser.droog@gmail.com> writes:

> On Monday, August 24, 2020 at 4:16:55 PM UTC-5, Tim Rentsch wrote:
>
>> luser droog <luser.droog@gmail.com> writes:
>>
>>> On Saturday, August 22, 2020 at 4:12:26 AM UTC-5, axel porin wrote:
>>>
>>>> hi
>>>> why it doesn't work
>>>>
>>>> int max3(int a,int b,int c){
>>>>     if(a<b)
>>>>     if(b<c)
>>>>     return c;
>>>>     else
>>>>     return b;
>>>> }
>>>>
>>>> int main(){
>>>>     int a=2,b=-4,c=6;
>>>>    printf("%d ",max3(a,b,c));
>>>> }
>>>>
>>>> output:
>>>> 2
>>>
>>> One way to approach this kind of function is to break it up into
>>> cases and make sure each case is covered.  The obvious cases here
>>> (to me) is whether to return a, b, or c.  So that leads directly to
>>> pseudocode:
>>>
>>>   if <a is the max>
>>>       return a;
>>>   if <b is the max>
>>>       return b;
>>>   if <c is the max>
>>>       return c;
>>>
>>> Since there branches are returning, I'm leaving out the 'else's so
>>> the top level structure is simpler.
>>>
>>> Then all that's needed is appropriate tests
>>>
>>> <a is the max>=
>>>   ( a > b && a < c )
>>>
>>> <b is the max>=
>>>   ( b > c )     /* we've already covered a */
>>>
>>> <c is the max>=
>>>   ( 1 )          /* we've already covered a and b */
>>>
>>> So that's how I recommend structuring your tests.  Nesting
>>> the expressions makes it harder to make sure all the
>>> possibilities are covered.  The code can certainly be
>>> simplified from there, but I think this gives a methodology
>>> to get these sort of functions written correctly.
>>
>> This approach seems the wrong way round.  It can do more
>> comparisons than it has to (at most two are needed), and that is
>> more evident if we consider larger problems of four or five, etc,
>> inputs.  The predicate "a is the answer" needs a global test.  In
>> contrast, the predicate "a is obviously not the answer" can be
>> done with a simple local test.  That insight helps construct a
>> solution.
>>
>> First we do the easy case, starting at the bottom.  With just one
>> input, the answer is the input:
>>
>>     int
>>     max1( int a ){  return  a;  }
>>
>> With two inputs, if a < b then the answer can't be a (and so it
>> must be b), but otherwise it can be a:
>>
>>     int
>>     max2( int a, int b ){  return  a < b ? b : a;  }
>>
>> With three inputs, a, b, and c, reduce three inputs to two by
>> doing one comparison.  If a < b, then the answer can't be a, and
>> so must be either b or c;  otherwise, the answer can choose
>> between a and c.  We know how to do tests for two inputs, so three
>> inputs is a simple step up from that:
>>
>>     int
>>     max3( int a, int b, int c ){
>>         return
>>             a < b
>>               ?    b < c ? c : b
>>               :    a < c ? c : a
>>         ;
>>     }
>>
>> or if max2() is present
>>
>>     int
>>     max3( int a, int b, int c ){
>>         return  a < b  ? max2( b, c )  : max2( a, c );
>>     }
>>
>> This approach scales easily, and linearly, for any fixed number
>> of inputs.
>
> Marvelous!  I think my tendency has been to code bottom up, and then
> you beat me with top down design.  Here I tried to be top down, and
> you beat me with mathematical induction.

Yes, in fact I noticed the irony when I was writing the response.

Another way to view the difference is this.  Both of our solutions
are top down, but they reduce the problem by looking at opposite
ends of the spectrum.  My scheme (even though the answer is
explained in a bottom-up way) reduces the problem by slicing off
as little of the problem as it can:  if a < b then we know the
answer cannot be a, etc.  In contrast, your scheme starts by
slicing off a big piece, in the sense that the test for "a being
the answer" is a more elaborate test.  As a general rule in
decomposing a problem it often helps to narrow the problem just a
little bit at a time, and let subsequent refinements take care of
the rest.  A common mistake (and I too am guilty of this at times)
is to try to do too much in the first refinement, leading to code
that is overly complicated, or hard to understand, or both.  Here
is a rule of thumb to counteract this tendency:  when you notice a
function starting to be too large or complicated, take a step back
and slice off just a little piece in the current function, leaving
the rest of the problem for the next level of refinement.