Velocity Reviews > find out the problem

# find out the problem

Eric Sosman
Guest
Posts: n/a

 08-01-2005

akarl wrote:
> sabarish wrote:
>
>>Hi to all. find out the biggest among two numbers without using any
>>conditional statements and any relational operators.

>
>
> It's simple as well as off topic (since it's not C specific):
>
> max(x, y) = (x + y + |x - y|) / 2

Try it with x = LDBL_MAX and y = -LDBL_MAX, and tell us
again just how "simple" it is.

Do other such misbehaving pairs exist? Oh yes, oh yes,
they most definitely do. I ran a simple test on a million
pairs of randomly-generated[*] `double' values, on which
akarl's formula delivered the right answer 596230 times --
and gave a wrong answer the other 403770 times. If you can
tolerate error rates of 40% or so, by all means use akarl's
"simple" formula.
[*] Not from a uniform distribution. I wanted a wide
spread of magnitudes, so I used tan(rand() * PI / RAND_MAX).

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

Keith Thompson
Guest
Posts: n/a

 08-01-2005
"sabarish" <(E-Mail Removed)> writes:
> Hi to all. find out the biggest among two numbers without using any
> conditional statements and any relational operators.

Use relational operators. That's what they're for.

If there's some reason you need to do this without using the features
of the language designed for that purpose, you should explain why if
you expect any help.

If the reason is that it's a homework assignment (which is the only
explanation I can think of), do it yourself.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

akarl
Guest
Posts: n/a

 08-01-2005
Eric Sosman wrote:
>
> akarl wrote:
>
>>sabarish wrote:
>>
>>
>>>Hi to all. find out the biggest among two numbers without using any
>>>conditional statements and any relational operators.

>>
>>
>>It's simple as well as off topic (since it's not C specific):
>>
>> max(x, y) = (x + y + |x - y|) / 2

>
>
> Try it with x = LDBL_MAX and y = -LDBL_MAX, and tell us
> again just how "simple" it is.
>
> Do other such misbehaving pairs exist? Oh yes, oh yes,
> they most definitely do. I ran a simple test on a million
> pairs of randomly-generated[*] `double' values, on which
> akarl's formula delivered the right answer 596230 times --
> and gave a wrong answer the other 403770 times. If you can
> tolerate error rates of 40% or so, by all means use akarl's
> "simple" formula.
>
>[*] Not from a uniform distribution. I wanted a wide
> spread of magnitudes, so I used tan(rand() * PI / RAND_MAX).

Note that I've only presented a mathematical formula, not a C
implementation However the whole matter is more of theoretical
interest; Why would anyone want to implement it without relational
operators?

August

Alexei A. Frounze
Guest
Posts: n/a

 08-01-2005
"Keith Thompson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> (E-Mail Removed) writes:
> > result=(x-y) //subtract y from x
> > //if x>y result is +ve else -ve
> >
> > result=result >>31 //get the sign bit to last bit
> > result=result&0x01 //mask the last bit
> >
> > return x*result + y*(~result & 0x1)
> >
> > if result =1 x will be returned as ~result&0x1 would be 0

>
> That has so many portability problems I'm not going to bother to
> decide whether it's correct.

The correct would be (on a 2's complemented target where the right shift
operator performed on a signed value keeps the MSBit/sign bit, aka Shift
Right Arithmetic):

#include <stdio.h>

/* BITS_IN_LONG says how many bits are in long, can be computed (at run time
but then it'll be a variable not macro) or if exists such a define somewhere
in the std libc headers, can be taken right from there: */
#define BITS_IN_LONG 32

long Max(long x, long y)
{
long res;
res = (x-y) >> BITS_IN_LONG; /* res=0 (all zeroes) or -1 (all ones) */
res = (x & ~res) | (y & res); /* depending on prev value of res, we just
select/multiplex x or y by means of bitwise masking */
return res;
}

int main()
{
printf ("%ld\n", Max(-1,-1));
printf ("%ld\n", Max(-1, 0));
printf ("%ld\n", Max(-1, 1));
printf ("%ld\n", Max( 0,-1));
printf ("%ld\n", Max( 0, 0));
printf ("%ld\n", Max( 0, 1));
printf ("%ld\n", Max( 1,-1));
printf ("%ld\n", Max( 1, 0));
printf ("%ld\n", Max( 1, 1));
return 0;
}
Gives as expected:
-1
0
1
0
0
1
1
1
1

I'd suggest the newbies learn boolean stuff and digital logic better (or at
all if never studied before). I know that the above thing has a limited use,
but the limit is many millions of CPUs where it would work just fine.
And honestly, fixed point math (where people often use similar tricks) is
much more portable than floating point. It will yield the same result (if
coded properly, of course) on all targets and compilers, whereas floating
point will almost always give different LSBit (due to optimization,
operation reordering or because of simply being not IE754 compliant or using
shorter floating types) and since the errors tend to accumulate, the
difference can be bigger.

There're a few great docs on the subjects:
Sun's Numerical Computation Guide / What Every Computer Scientist Should
Know About Floating-Point Arithmetic by Goldberg
and
Algorithms For Programmers ideas and source code by Arndt

HTH
Alex

Jack Klein
Guest
Posts: n/a

 08-02-2005
On 1 Aug 2005 09:01:02 -0700, (E-Mail Removed) wrote in
comp.lang.c:

Your decision to use the broken Google interface DOES NOT entitle you
to inflict the bad manners of responses with NO CONTEXT. LEARN HOW TO
QUOTE PROPERLY.

Hmmm...

double return_larger(double x, double y)
{
double result;
/* so far so good */

> result=(x-y) //subtract y from x
> //if x>y result is +ve else -ve

> result=result >>31 //get the sign bit to last bit
> result=result&0x01 //mask the last bit
>
> return x*result + y*(~result & 0x1)
>
> if result =1 x will be returned as ~result&0x1 would be 0

....just a few messages from an unhappy compiler.

Now as the OP's original question was:

> > Hi to all. find out the biggest among two numbers without using any
> > conditional statements and any relational operators.

....where did he say integer types?

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

Krishanu Debnath
Guest
Posts: n/a

 08-02-2005

Alexei A. Frounze wrote:
> "Keith Thompson" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
> > (E-Mail Removed) writes:

[snip]
>
> The correct would be (on a 2's complemented target where the right shift
> operator performed on a signed value keeps the MSBit/sign bit, aka Shift
> Right Arithmetic):
>
> #include <stdio.h>
>
> /* BITS_IN_LONG says how many bits are in long, can be computed (at run time
> but then it'll be a variable not macro) or if exists such a define somewhere
> in the std libc headers, can be taken right from there: */
> #define BITS_IN_LONG 32
>
> long Max(long x, long y)
> {
> long res;
> res = (x-y) >> BITS_IN_LONG; /* res=0 (all zeroes) or -1 (all ones) */

It invokes UB. C99 6.5.7p3

"If the value of the right operand is negative or is greater than or
equal to the width of the promoted left operand, the behavior is
undefined."

> res = (x & ~res) | (y & res); /* depending on prev value of res, we just
> select/multiplex x or y by means of bitwise masking */
> return res;
> }
>

Krishanu

--
"What we need is less people running around and telling everyone else
what to do and more people actually writing code."
--Linus Torvalds

Alexei A. Frounze
Guest
Posts: n/a

 08-02-2005
"Krishanu Debnath" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) ups.com...
....
> > long Max(long x, long y)
> > {
> > long res;
> > res = (x-y) >> BITS_IN_LONG; /* res=0 (all zeroes) or -1 (all ones) */

>
> It invokes UB. C99 6.5.7p3
>
> "If the value of the right operand is negative or is greater than or
> equal to the width of the promoted left operand, the behavior is
> undefined."

I know it's undefined *by standard*. But it's pretty much well defined by so
many compilers out there... Can one name a compiler that issues an error at
that shift operator or yields garbage or freaks out? Can anyone name one
that doesn't extend/propagate the sign bit to the right? I'm asking out of
curiousity, since 6 or 7 compilers that I know would handle that just right
(on about 5 entirely different CPUs, ix86 and several non-ix86).

Alex

Gordon Burditt
Guest
Posts: n/a

 08-02-2005
>> > long res;
>> > res = (x-y) >> BITS_IN_LONG; /* res=0 (all zeroes) or -1 (all ones) */

>>
>> It invokes UB. C99 6.5.7p3
>>
>> "If the value of the right operand is negative or is greater than or
>> equal to the width of the promoted left operand, the behavior is
>> undefined."

>
>I know it's undefined *by standard*. But it's pretty much well defined by so
>many compilers out there... Can one name a compiler that issues an error at
>that shift operator or yields garbage or freaks out? Can anyone name one

There are a number of assembly languages where the shift count can
be a variable but only a small number of bits are used. Higher-order
bits in the count are ignored. (Typically a shift of the number
of bits in the word is equivalent to a shift of 0 (no change) rather
than filling the entire word with the sign bit or with zeroes.)

Compilers typically take the shift count, stuff it in a register,
and use the register for the shift count in a shift instruction.
If the shift count is out of range for the instruction, let the
nasal demons fly where they may.

For a specific example: Intel Pentium, gcc 3.4.2 on FreeBSD. A
shift of N bits of an int or long (32 bits in this case) to the
right seems to be treated the same as a shift of (N%32) bits to the
right *WHEN THE SHIFT COUNT IS VARIABLE*. This is "wrong" according
to what people would expect a shift to do. You get different results
sometimes if the shift amount is a constant rather than a variable.

>that doesn't extend/propagate the sign bit to the right? I'm asking out of
>curiousity, since 6 or 7 compilers that I know would handle that just right
>(on about 5 entirely different CPUs, ix86 and several non-ix86).

The code:

#include <stdio.h>
int x(int a)
{
printf("%d: %lx\n", a, 0x12345678 >> a);
return 0;
}
int main(void)
{
x(36);
x(32);
x(0);
return 0;
}

The output (annotated to the right):
36: 1234567 Same as a shift of 4
32: 12345678 Same as no shift at all
0: 12345678

Gordon L. Burditt

Tobias Blomkvist
Guest
Posts: n/a

 08-02-2005
> For a specific example: Intel Pentium, gcc 3.4.2 on FreeBSD. A

[snippy-snip]

> int main(void)
> {
> x(36);
> x(32);

On all IA-32 processors starting with Intel 286, the shift count
is masked to 5 bits, resulting in a maximum count of 31.

(IA-32 Intel Architecture Software Developer's Manual Volume 2, page 737)

Hence:

> The output (annotated to the right):
> 36: 1234567 Same as a shift of 4
> 32: 12345678 Same as no shift at all
> 0: 12345678

Tobias
--
IMPORTANT: The contents of this email and attachments are confidential
and may be subject to legal privilege and/or protected by copyright.
Copying or communicating any part of it to others is prohibited and may
be unlawful.

Alexei A. Frounze
Guest
Posts: n/a

 08-02-2005
"Gordon Burditt" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
....
> There are a number of assembly languages where the shift count can
> be a variable but only a small number of bits are used. Higher-order
> bits in the count are ignored. (Typically a shift of the number
> of bits in the word is equivalent to a shift of 0 (no change) rather
> than filling the entire word with the sign bit or with zeroes.)

Yep.

> Compilers typically take the shift count, stuff it in a register,
> and use the register for the shift count in a shift instruction.
> If the shift count is out of range for the instruction, let the
> nasal demons fly where they may.

I've seen that and was very surprised.

> For a specific example: Intel Pentium, gcc 3.4.2 on FreeBSD. A
> shift of N bits of an int or long (32 bits in this case) to the
> right seems to be treated the same as a shift of (N%32) bits to the
> right *WHEN THE SHIFT COUNT IS VARIABLE*. This is "wrong" according
> to what people would expect a shift to do. You get different results
> sometimes if the shift amount is a constant rather than a variable.
>
> The code:
>
> #include <stdio.h>
> int x(int a)
> {
> printf("%d: %lx\n", a, 0x12345678 >> a);
> return 0;
> }
> int main(void)
> {
> x(36);
> x(32);
> x(0);
> return 0;
> }
>
> The output (annotated to the right):
> 36: 1234567 Same as a shift of 4
> 32: 12345678 Same as no shift at all
> 0: 12345678

That all is correct, no doubt, however, my personal opinion is that that's
wrong to take the shift count and blindly feed it to the asm instruction
with such a limitation. It's as illogical as the need to cast one of two
integer multipliers to long integer in order to get the correct long integer
product. That strikes the math guys in the back. Anyway, I was talking about
a slightly different problem of the shift -- whether or not it's SAR-like or
something else, especially something very odd, probably not any kind of
shift at all.

Alex