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

Groups > comp.lang.c > #142881 > unrolled thread

Re: Application Exercises

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

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-06 23:55 -0700
    Re: Application Exercises mark.bluemel@gmail.com - 2019-04-08 00:33 -0700
      Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-09 04:28 -0700
        Re: Application Exercises John Forkosh <forkosh@panix.com> - 2019-04-11 13:07 +0000
          Re: Application Exercises Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-04-11 06:11 -0700
            Re: Application Exercises John Forkosh <forkosh@panix.com> - 2019-04-11 13:19 +0000
              Re: Application Exercises James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-11 06:49 -0700
                Re: Application Exercises Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-12 01:20 +0100
        Re: Application Exercises Richard Damon <Richard@Damon-Family.org> - 2019-04-11 23:36 -0400
          Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-12 19:08 -0700

#142881 — Re: Application Exercises

ram@zedat.fu-berlin.de (Stefan Ram) writes:

> |Write a function to detect whether two integral numbers are
> |equal without using any comparison operators.

I have written a solution that I believe works correctly
on any conforming implementation.

[toc] | [next] | [standalone]

#142896

On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
> ram@zedat.fu-berlin.de (Stefan Ram) writes:
> 
> > |Write a function to detect whether two integral numbers are
> > |equal without using any comparison operators.
> 
> I have written a solution that I believe works correctly
> on any conforming implementation.

But it's too large to fit in this margin?

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

#142917

mark.bluemel@gmail.com writes:

> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
>
>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>
>>> |Write a function to detect whether two integral numbers are
>>> |equal without using any comparison operators.
>>
>> I have written a solution that I believe works correctly
>> on any conforming implementation.
>
> But it's too large to fit in this margin?

Actually I wrote several solutions.  But I wasn't really
happy with any of them, they were all a bit clunky in one
way or another.  The point of my comment is just to say
a fully portable solution is possible.

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

#143008

Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> mark.bluemel@gmail.com writes:
> 
>> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
>>
>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>
>>>> |Write a function to detect whether two integral numbers are
>>>> |equal without using any comparison operators.
>>>
>>> I have written a solution that I believe works correctly
>>> on any conforming implementation.
>>
>> But it's too large to fit in this margin?
> 
> Actually I wrote several solutions.  But I wasn't really
> happy with any of them, they were all a bit clunky in one
> way or another.  The point of my comment is just to say
> a fully portable solution is possible.

Didn't anybody just write...

/* --- test whether or not two ints are equal,
   without comparisons --- */
#include <stdio.h>
#include <stdlib.h>
int main ( int argc, char *argv[] ) {
  int  i = (argc>1? atoi(argv[1]) : 1 ),
       j = (argc>2? atoi(argv[2]) : 2 );
  int  isequal();
  fprintf( stdout," %d %s %d? \n",
       i, (isequal(i,j)?"==":"=/="), j);
  } /* --- end-of-function main() --- */

int isequal ( int i, int j ) {
  return ( !( abs(i-j) ) );
  } /* --- end-of-function isequal() --- */

Works fine on my box.
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

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

#143009

On Thursday, 11 April 2019 14:08:07 UTC+1, John Forkosh  wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> > mark.bluemel@gmail.com writes:
> > 
> >> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
> >>
> >>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
> >>>
> >>>> |Write a function to detect whether two integral numbers are
> >>>> |equal without using any comparison operators.
> >>>
> >>> I have written a solution that I believe works correctly
> >>> on any conforming implementation.
> >>
> >> But it's too large to fit in this margin?
> > 
> > Actually I wrote several solutions.  But I wasn't really
> > happy with any of them, they were all a bit clunky in one
> > way or another.  The point of my comment is just to say
> > a fully portable solution is possible.
> 
> Didn't anybody just write...
> 
> /* --- test whether or not two ints are equal,
>    without comparisons --- */
> #include <stdio.h>
> #include <stdlib.h>
> int main ( int argc, char *argv[] ) {
>   int  i = (argc>1? atoi(argv[1]) : 1 ),
>        j = (argc>2? atoi(argv[2]) : 2 );
>   int  isequal();
>   fprintf( stdout," %d %s %d? \n",
>        i, (isequal(i,j)?"==":"=/="), j);
>   } /* --- end-of-function main() --- */
> 
> int isequal ( int i, int j ) {
>   return ( !( abs(i-j) ) );
>   } /* --- end-of-function isequal() --- */
> 
> Works fine on my box.
>
If both i is negative and j positive and large, this can generate an
arithmetical overflow error

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

#143010

Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> On Thursday, 11 April 2019 14:08:07 UTC+1, John Forkosh  wrote:
>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>> > mark.bluemel@gmail.com writes:
>> > 
>> >> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
>> >>
>> >>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>> >>>
>> >>>> |Write a function to detect whether two integral numbers are
>> >>>> |equal without using any comparison operators.
>> >>>
>> >>> I have written a solution that I believe works correctly
>> >>> on any conforming implementation.
>> >>
>> >> But it's too large to fit in this margin?
>> > 
>> > Actually I wrote several solutions.  But I wasn't really
>> > happy with any of them, they were all a bit clunky in one
>> > way or another.  The point of my comment is just to say
>> > a fully portable solution is possible.
>> 
>> Didn't anybody just write...
>> 
>> /* --- test whether or not two ints are equal,
>>    without comparisons --- */
>> #include <stdio.h>
>> #include <stdlib.h>
>> int main ( int argc, char *argv[] ) {
>>   int  i = (argc>1? atoi(argv[1]) : 1 ),
>>        j = (argc>2? atoi(argv[2]) : 2 );
>>   int  isequal();
>>   fprintf( stdout," %d %s %d? \n",
>>        i, (isequal(i,j)?"==":"=/="), j);
>>   } /* --- end-of-function main() --- */
>> 
>> int isequal ( int i, int j ) {
>>   return ( !( abs(i-j) ) );
>>   } /* --- end-of-function isequal() --- */
>> 
>> Works fine on my box.
>>
> If both i is negative and j positive and large, this can generate an
> arithmetical overflow error

Sheesh! I didn't think that the -extremely-bleeping-pedantic compiler
switch was the point of the exercise:)  So how about
     return ( !( abs(abs(i)-abs(j)) ) );   ???
-- 
John Forkosh  ( mailto:  j@f.com  where j=john and f=forkosh )

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

#143013

On Thursday, April 11, 2019 at 9:19:09 AM UTC-4, John Forkosh wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> > On Thursday, 11 April 2019 14:08:07 UTC+1, John Forkosh  wrote:
> >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >> > mark.bluemel@gmail.com writes:
> >> > 
> >> >> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
> >> >>
> >> >>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
> >> >>>
> >> >>>> |Write a function to detect whether two integral numbers are
> >> >>>> |equal without using any comparison operators.
...
> >> > way or another.  The point of my comment is just to say
> >> > a fully portable solution is possible.
> >> 
> >> Didn't anybody just write...
> >> 
> >> /* --- test whether or not two ints are equal,
> >>    without comparisons --- */
> >> #include <stdio.h>
> >> #include <stdlib.h>
> >> int main ( int argc, char *argv[] ) {
> >>   int  i = (argc>1? atoi(argv[1]) : 1 ),
> >>        j = (argc>2? atoi(argv[2]) : 2 );
> >>   int  isequal();
> >>   fprintf( stdout," %d %s %d? \n",
> >>        i, (isequal(i,j)?"==":"=/="), j);
> >>   } /* --- end-of-function main() --- */
> >> 
> >> int isequal ( int i, int j ) {
> >>   return ( !( abs(i-j) ) );
> >>   } /* --- end-of-function isequal() --- */
> >> 
> >> Works fine on my box.
> >>
> > If both i is negative and j positive and large, this can generate an
> > arithmetical overflow error
> 
> Sheesh! I didn't think that the -extremely-bleeping-pedantic compiler
> switch was the point of the exercise:) ...

Good, because it wasn't. However, Tim said that a fully portable
solution was possible, and (regardless of whether any compiler switches
are involved), a solution that triggers signed integer overflow can't
qualify as portable - there are fully conforming implementations of C
where such code wouldn't work as you expect it to in that case.

There's a reason why this challenge is sufficiently difficult to attract some interest.

> ... So how about
>      return ( !( abs(abs(i)-abs(j)) ) );   ???

isequal(3,-3)?

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

#143048

James Kuyper <jameskuyper@alumni.caltech.edu> writes:

> On Thursday, April 11, 2019 at 9:19:09 AM UTC-4, John Forkosh wrote:
<cut>
>> ... So how about
>>      return ( !( abs(abs(i)-abs(j)) ) );   ???
>
> isequal(3,-3)?

and ! is excluded from the rules of the game.

-- 
Ben.

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

#143057

On 4/9/19 7:28 AM, Tim Rentsch wrote:
> mark.bluemel@gmail.com writes:
> 
>> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
>>
>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>
>>>> |Write a function to detect whether two integral numbers are
>>>> |equal without using any comparison operators.
>>>
>>> I have written a solution that I believe works correctly
>>> on any conforming implementation.
>>
>> But it's too large to fit in this margin?
> 
> Actually I wrote several solutions.  But I wasn't really
> happy with any of them, they were all a bit clunky in one
> way or another.  The point of my comment is just to say
> a fully portable solution is possible.
> 

One thought I had, if we assume that x doesn't have near the absolute
full range of uintmax_t (which we can get by using trick of comparing
x/256 to y/256, and also x%256 to y%256 then, for an unsigned x

(x+2)/(x+1)-1

will have the value of 1 if x is 0 and 0 if x has any other value.

This allows you to perform the effect of a comparison to zero, giving
you the base results wanted.

it is now just a matter of using the range limitation trick once to
limit the range of the numbers so we can safely convert them to unsigned
(since it is allowed for the unsigned numbers to be a bit smaller than
the signed numbers, effctively just forcing the sign bit to 0), take the
difference as unsigned (so no overflow is possible), reduce range again
(as the subtraction might generate a maximal unsigned value) and use the
division trick to convert to an effective bool.

We will do this reduction 4 times, and we can get the product of the
result (to simulate and AND operation) to detect if the original two
numbers were numerically the same.

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

#143065

Richard Damon <Richard@Damon-Family.org> writes:

> On 4/9/19 7:28 AM, Tim Rentsch wrote:
>
>> mark.bluemel@gmail.com writes:
>>
>>> On Sunday, 7 April 2019 07:55:40 UTC+1, Tim Rentsch  wrote:
>>>
>>>> ram@zedat.fu-berlin.de (Stefan Ram) writes:
>>>>
>>>>> |Write a function to detect whether two integral numbers are
>>>>> |equal without using any comparison operators.
>>>>
>>>> I have written a solution that I believe works correctly
>>>> on any conforming implementation.
>>>
>>> But it's too large to fit in this margin?
>>
>> Actually I wrote several solutions.  But I wasn't really
>> happy with any of them, they were all a bit clunky in one
>> way or another.  The point of my comment is just to say
>> a fully portable solution is possible.
>
> One thought I had, if we assume that x doesn't have near the absolute
> full range of uintmax_t (which we can get by using trick of comparing
> x/256 to y/256, and also x%256 to y%256 then, for an unsigned x
>
> (x+2)/(x+1)-1
>
> will have the value of 1 if x is 0 and 0 if x has any other value.
>
> This allows you to perform the effect of a comparison to zero, giving
> you the base results wanted.

This division method is clever, much moreso than my original
approach.  Using this insight we can write a routine to see if an
unsigned value is zero in just a few lines (the code uses the
type names 'Smax' and 'Umax' for the largest signed and unsigned
integer types):

    int
    unsigned_is_zero( Umax a ){
        Umax   half_plus_one    =  a/2 +1;
        Umax   upper_bits_zero  =  (half_plus_one + 1)/half_plus_one  - 1;
        Umax   low_bit_zero     =  a&1 ^ 1;

        return  upper_bits_zero  &  low_bit_zero;
    }

Note by the way that the '&1' in the initializer for 'low_bit_zero'
isn't actually needed.  Because 'upper_bits_zero' is always either
zero or one we can get the '&1' for free if we want to.

> it is now just a matter of using the range limitation trick once to
> limit the range of the numbers so we can safely convert them to unsigned
> (since it is allowed for the unsigned numbers to be a bit smaller than
> the signed numbers, effctively just forcing the sign bit to 0), take the
> difference as unsigned (so no overflow is possible), reduce range again
> (as the subtraction might generate a maximal unsigned value) and use the
> division trick to convert to an effective bool.

Rather than take the difference, if we want to compare two
unsigned values for equality, that can be done with '^':

    int
    unsigneds_are_equal( Umax a, Umax b ){
        return  unsigned_is_zero( a ^ b );
    }

> We will do this reduction 4 times, and we can get the product of the
> result (to simulate and AND operation) to detect if the original two
> numbers were numerically the same.

Here I'm lost.  I don't know what reduction you mean, or why it
needs to be done four times.  Also is there some reason you want
to avoid using an '&' operator?  It doesn't do a comparison and
so should be fair game (as should '^' and '|').  To avoid the
problem of unsigned types potentially having a width one smaller
than their corresponding signed type, we can break the signed values
into parts like what you suggest:

    int
    signeds_are_equal( Smax a, Smax b ){
        return
            unsigneds_are_equal( a/256, b/256 )  &
            unsigneds_are_equal( a%256, b%256 );
    }

Alternatively, we can use divide-by-two to compare all the upper
bits, and treat the remainder mod two specially:

    int
    signeds_are_equal( Smax a, Smax b ){
        return  unsigneds_are_equal( a/2, b/2 )  &  0421 >> a%2*3 + b%2 + 4;
    }

Here we are taking advantage of the unsigneds_are_equal()
function always returning zero or one to avoid a superfluous '&1'
in the residue test.

The end result is a remarkably compact solution.  I doff my
hat to you sir.

To save a bit of face, let me give a second followup challenge
problem.  Again we want to avoid using C's built-in comparison
operations (including !, which I forgot to mention in the first
go-round).  The functionality being sought is an implementation
for (keeping it simple, let's assume C99)

    int
    is_less_or_equal( intmax_t a, intmax_t b ){
        ...
    }

where the function returns 1 if argument 'a' is less than or
equal to argument 'b', and 0 otherwise.  Ideal solution should
work on any conforming C99 implementation.

[toc] | [prev] | [standalone]

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

csiph-web