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

Groups > comp.lang.c > #142868 > 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 Richard Damon <Richard@Damon-Family.org> - 2019-04-06 14:23 -0400
    Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-09 04:35 -0700
      Re: Application Exercises Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-09 13:29 +0100
        Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-09 08:02 -0700
      Re: Application Exercises Richard Damon <Richard@Damon-Family.org> - 2019-04-09 22:15 -0400
        Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-09 20:55 -0700
          Re: Application Exercises Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-04-09 22:21 -0600
            Re: Application Exercises Richard Damon <Richard@Damon-Family.org> - 2019-04-10 06:31 -0400
            Re: Application Exercises James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-10 07:43 -0400
          Re: Application Exercises Richard Damon <Richard@Damon-Family.org> - 2019-04-10 06:40 -0400
            Re: Application Exercises Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-04-10 08:15 -0700
        Re: Application Exercises James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-10 07:37 -0400

#142868 — Re: Application Exercises

On 4/6/19 2:01 PM, Stefan Ram wrote:
>   Disclaimer: I might have posted about the same programming
>   problem some years ago. But then it was my own invention,
>   while now I read about it in a book.
> 
>   In a book about the job application as a programmer, I found
>   a paragraph, were they say that application exercises often
>   enforce arbitrary restrictions, which do not make sense
>   according to the author of this book, but the exercises have
>   to be done nevertheless. As an example he gave:
> 
> |Write a function to detect whether two integral numbers are
> |equal without using any comparison operators.
> 
>   . As a hint he wrote: "Think of bit operators.".
> 
>   Ok, I have an idea how I might do this, which I might post
>   later. I am not sure whether my idea is correct. I need to
>   write a test. Or maybe a proof?
> 
>   The book did not refer to C, but C is the most popular
>   programming language (or may be at least one of the most
>   popular programming languages), and the book mentioned
>   "bit operators".
> 
> 

The one thought I had was if (i^j), you could also use if(i-j)

To detect something, you need some form of test, but if, or conversion
to bool have an implied comparison to zero, which isn't considered a
comparison operator.

[toc] | [next] | [standalone]

#142918

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

> On 4/6/19 2:01 PM, Stefan Ram wrote:
>
>> |Write a function to detect whether two integral numbers are
>> |equal without using any comparison operators.
>>
>>   . As a hint he wrote:  "Think of bit operators.".
>>
>>   Ok, I have an idea how I might do this, which I might post
>>   later.  I am not sure whether my idea is correct.  I need to
>>   write a test.  Or maybe a proof?
>>
>>   The book did not refer to C, but C is the most popular
>>   programming language (or may be at least one of the most
>>   popular programming languages), and the book mentioned
>>   "bit operators".
>
> The one thought I had was if (i^j), you could also use if(i-j)
>
> To detect something, you need some form of test, but if, or
> conversion to bool have an implied comparison to zero, which
> isn't considered a comparison operator.

Challenge problem:  write a signed-integer equality determiner
without using any comparisons:  no comparison operators, no
conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
or while()'s, and (the sneaky one) no switch()'s.  A nice
little problem.  The gold standard is a solution that works
on any conforming implementation.

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

#142919

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Challenge problem:  write a signed-integer equality determiner
> without using any comparisons:  no comparison operators, no
> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
> or while()'s, and (the sneaky one) no switch()'s.  A nice
> little problem.  The gold standard is a solution that works
> on any conforming implementation.

... and presumably no !.

-- 
Ben.

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

#142923

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> Challenge problem:  write a signed-integer equality determiner
>> without using any comparisons:  no comparison operators, no
>> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
>> or while()'s, and (the sneaky one) no switch()'s.  A nice
>> little problem.  The gold standard is a solution that works
>> on any conforming implementation.
>
> ... and presumably no !.

Right.  I had thought of that but when I wrote the posting
I forgot to mention it.

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

#142940

On 4/9/19 7:35 AM, Tim Rentsch wrote:
> Challenge problem:  write a signed-integer equality determiner
> without using any comparisons:  no comparison operators, no
> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
> or while()'s, and (the sneaky one) no switch()'s.  A nice
> little problem.  The gold standard is a solution that works
> on any conforming implementation.
> 

Presumably, +0 should be equal to -0? (of course, this only applies if
you don't have a two's complement machine.

I have a thought for a solution, but have the question if you are
allowed comparisons in pre-processor directives, so the only comparisons
are at compile time and not at execution time (with the assumption the
values are execution time values). The issue is that I want to convert a
non-zero value to 1, which I can do without any comparisons, as long as
I know how many cycles of reduction to run, which needs preprocessor
comparisons, or hard wiring in knowledge of the number of bits in a
signed int.

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

#142941

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

> On 4/9/19 7:35 AM, Tim Rentsch wrote:
>
>> Challenge problem:  write a signed-integer equality determiner
>> without using any comparisons:  no comparison operators, no
>> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
>> or while()'s, and (the sneaky one) no switch()'s.  A nice
>> little problem.  The gold standard is a solution that works
>> on any conforming implementation.
>
> Presumably, +0 should be equal to -0?  (of course, this only applies if
> you don't have a two's complement machine.

Yes, that is my operating assumption:  the result should be the
same as 'a == b', which AFAIK gives +0 == -0.

> I have a thought for a solution, but have the question if you are
> allowed comparisons in pre-processor directives, so the only comparisons
> are at compile time and not at execution time (with the assumption the
> values are execution time values).  The issue is that I want to convert a
> non-zero value to 1, which I can do without any comparisons, as long as
> I know how many cycles of reduction to run, which needs preprocessor
> comparisons, or hard wiring in knowledge of the number of bits in a
> signed int.

The code I wrote has one pre-processor comparison, to allow the
code to work in different versions of C.  The test is this:

    #if __STDC_VERSION__ > 199900

The code does not assume any particular values or bounds for the
number of bits in a signed int (or in intmax_t, which is the
type used when compiling as C99 or later).

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

#142942

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Richard Damon <Richard@Damon-Family.org> writes:
>
>> On 4/9/19 7:35 AM, Tim Rentsch wrote:
>>
>>> Challenge problem:  write a signed-integer equality determiner
>>> without using any comparisons:  no comparison operators, no
>>> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
>>> or while()'s, and (the sneaky one) no switch()'s.  A nice
>>> little problem.  The gold standard is a solution that works
>>> on any conforming implementation.
>>
>> Presumably, +0 should be equal to -0?  (of course, this only applies if
>> you don't have a two's complement machine.
>
> Yes, that is my operating assumption:  the result should be the
> same as 'a == b', which AFAIK gives +0 == -0.

I didn't find it in the C standard in a quick search, but at least in
the case of the CDC 6000 series of computers -0 != +0, but the only way
to generate a -0 was to explicitly create it.  Any sequence of
arithmetic operations resulting in 0 resulted in +0.

>> I have a thought for a solution, but have the question if you are
>> allowed comparisons in pre-processor directives, so the only comparisons
>> are at compile time and not at execution time (with the assumption the
>> values are execution time values).  The issue is that I want to convert a
>> non-zero value to 1, which I can do without any comparisons, as long as
>> I know how many cycles of reduction to run, which needs preprocessor
>> comparisons, or hard wiring in knowledge of the number of bits in a
>> signed int.
>
> The code I wrote has one pre-processor comparison, to allow the
> code to work in different versions of C.  The test is this:
>
>     #if __STDC_VERSION__ > 199900
>
> The code does not assume any particular values or bounds for the
> number of bits in a signed int (or in intmax_t, which is the
> type used when compiling as C99 or later).

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

#142952

On 4/10/19 12:21 AM, Joe Pfeiffer wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> 
>> Richard Damon <Richard@Damon-Family.org> writes:
>>
>>> On 4/9/19 7:35 AM, Tim Rentsch wrote:
>>>
>>>> Challenge problem:  write a signed-integer equality determiner
>>>> without using any comparisons:  no comparison operators, no
>>>> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
>>>> or while()'s, and (the sneaky one) no switch()'s.  A nice
>>>> little problem.  The gold standard is a solution that works
>>>> on any conforming implementation.
>>>
>>> Presumably, +0 should be equal to -0?  (of course, this only applies if
>>> you don't have a two's complement machine.
>>
>> Yes, that is my operating assumption:  the result should be the
>> same as 'a == b', which AFAIK gives +0 == -0.
> 
> I didn't find it in the C standard in a quick search, but at least in
> the case of the CDC 6000 series of computers -0 != +0, but the only way
> to generate a -0 was to explicitly create it.  Any sequence of
> arithmetic operations resulting in 0 resulted in +0.
> 

Later version of the Standard explicitly describe -0, and for
sign-magnitude and one's complement explicitly allow (but don't require)
it to be able to be generated by the bit manipulation operations.
Earlier versions are less explicit.

The comparison operators are defined as working on the VALUES of
objects, so while not explicitly defined, +0 and -0 are both
mathematically the same value so should compare equal.

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

#142956

On 4/10/19 12:21 AM, Joe Pfeiffer wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> 
>> Richard Damon <Richard@Damon-Family.org> writes:
...
>>> Presumably, +0 should be equal to -0?  (of course, this only applies if
>>> you don't have a two's complement machine.
>>
>> Yes, that is my operating assumption:  the result should be the
>> same as 'a == b', which AFAIK gives +0 == -0.
> 
> I didn't find it in the C standard in a quick search, but at least in
> the case of the CDC 6000 series of computers -0 != +0, ...

A conforming implementation of C for such a platform would have to
implement signed integer comparisons with special-case handling to
correct that - they're supposed to compare equal.

> ... but the only way
> to generate a -0 was to explicitly create it.  Any sequence of
> arithmetic operations resulting in 0 resulted in +0.

" If the implementation supports negative zeros, they shall be generated
only by:
— the &, |, ^, ~, <<, and >> operators with arguments that produce such
a value;
— the +, -, *, /, and % operators where one argument is a negative zero
and the result is zero;
— compound assignment operators based on the above cases.
It is unspecified whether these cases actually generate a negative zero
or a normal zero, and whether a negative zero becomes a normal zero when
stored in an object." (6.2.6.2p3).

"If the implementation does not support negative zeros, the behavior of
the &, |, ^, ~, <<, and >> operators with arguments that would produce
such a value is undefined." (6.2.6.2p4).

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

#142954

On 4/9/19 11:55 PM, Tim Rentsch wrote:
> Richard Damon <Richard@Damon-Family.org> writes:
> 
>> On 4/9/19 7:35 AM, Tim Rentsch wrote:
>>
>>> Challenge problem:  write a signed-integer equality determiner
>>> without using any comparisons:  no comparison operators, no
>>> conversions to bool, no &&, ||, or ?:, no if()'s, for()'s,
>>> or while()'s, and (the sneaky one) no switch()'s.  A nice
>>> little problem.  The gold standard is a solution that works
>>> on any conforming implementation.
>>
>> Presumably, +0 should be equal to -0?  (of course, this only applies if
>> you don't have a two's complement machine.
> 
> Yes, that is my operating assumption:  the result should be the
> same as 'a == b', which AFAIK gives +0 == -0.
> 
>> I have a thought for a solution, but have the question if you are
>> allowed comparisons in pre-processor directives, so the only comparisons
>> are at compile time and not at execution time (with the assumption the
>> values are execution time values).  The issue is that I want to convert a
>> non-zero value to 1, which I can do without any comparisons, as long as
>> I know how many cycles of reduction to run, which needs preprocessor
>> comparisons, or hard wiring in knowledge of the number of bits in a
>> signed int.
> 
> The code I wrote has one pre-processor comparison, to allow the
> code to work in different versions of C.  The test is this:
> 
>     #if __STDC_VERSION__ > 199900
> 
> The code does not assume any particular values or bounds for the
> number of bits in a signed int (or in intmax_t, which is the
> type used when compiling as C99 or later).
> 

Thinking about it a bit more, I think I can figure out how to do this
differently without needing the size of an int. I guess that you need
the __STDC_VERSION__ test to know a name for the largest signed type and
not assuming you are dealing with an int, but some arbitrary integer type.

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

#142964

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

> On 4/9/19 11:55 PM, Tim Rentsch wrote:
>
>> The code I wrote has one pre-processor comparison, to allow the
>> code to work in different versions of C.  The test is this:
>>
>>     #if __STDC_VERSION__ > 199900
>>
>
> I guess that you need the __STDC_VERSION__ test to know a name for
> the largest signed type and not assuming you are dealing with an
> int, but some arbitrary integer type.

Yes.  I wanted one routine for all signed types.  The natural
type for that is intmax_t, but that isn't available in pre-C99
environments, hence the pre-processor test.

> Thinking about it a bit more, I think I can figure out how to
> do this differently without needing the size of an int.

Great!  Reading your comments also has given me an idea for
an improvement to my previous solution.

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

#142955

On 4/9/19 10:15 PM, Richard Damon wrote:
...
> Presumably, +0 should be equal to -0? (of course, this only applies if
> you don't have a two's complement machine.

"If the sign bit is zero, it shall not affect the resulting value. If
the sign bit is one, the value shall be modified in one of the following
ways:
— the corresponding value with sign bit 0 is negated (sign and magnitude);
— the sign bit has the value −(2^N ) (two’s complement);
— the sign bit has the value −(2^N − 1) (ones’ complement ).
Which of these applies is implementation-defined, as is whether the
value with sign bit 1 and all value bits zero (for the first two), or
with sign bit and all value bits 1 (for ones’ complement), is a trap
representation or a normal value. In the case of sign and magnitude and
ones’ complement, if this representation is a normal value it is called
a negative zero." (6.2.6.2p2).

For sign and magnitude, if a negative zero is supported, it has the same
value as a zero, negated, which is still 0.

For one's complement the sign bit has a value which is exactly equal and
opposite to the sum of the values of all of the value bits. Therefore,
if a negative zero is supported, it's value is the sum of the values of
all of the sign and value bits, which is 0.

[toc] | [prev] | [standalone]

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

csiph-web