find out the problem

Discussion in 'C Programming' started by sabarish, Aug 1, 2005.

  1. sabarish

    sabarish Guest

    Hi to all. find out the biggest among two numbers without using any
    conditional statements and any relational operators.
    sabarish, Aug 1, 2005
    #1
    1. Advertising

  2. sabarish

    Eric Sosman Guest

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


    This cannot be done, not even by using non-portable
    trickery. The reason is simple: there is no such thing
    as the "biggest" of just two numbers. The superlative
    form of an adjective implies three or more alternatives.

    Had you written "bigger" the answer might have been
    different -- but that would have made the question sound
    like homework, and we can't have that, can we?

    --
    Eric Sosman, Aug 1, 2005
    #2
    1. Advertising

  3. sabarish

    Richard Bos Guest

    Eric Sosman <> wrote:

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

    >
    > This cannot be done, not even by using non-portable
    > trickery. The reason is simple: there is no such thing
    > as the "biggest" of just two numbers. The superlative
    > form of an adjective implies three or more alternatives.


    No, they don't. Check the OED. What you describe is merely customary in
    some circles, but not the only correct usage.

    Richard
    Richard Bos, Aug 1, 2005
    #3
  4. sabarish wrote:
    >
    > Hi to all. find out the biggest among two numbers without using any
    > conditional statements and any relational operators.


    So, how many open NNTP proxies do you have access to?

    --
    +-------------------------+--------------------+-----------------------------+
    | Kenneth J. Brody | www.hvcomputer.com | |
    | kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------------+
    Don't e-mail me at: <mailto:>
    Kenneth Brody, Aug 1, 2005
    #4
  5. sabarish

    Guest

    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
    , Aug 1, 2005
    #5
  6. In article <>,
    <> wrote:
    >result=(x-y) //subtract y from x
    > //if x>y result is +ve else -ve


    Why would the result be negative if the two values are equal?
    --
    This signature intentionally left... Oh, darn!
    Walter Roberson, Aug 1, 2005
    #6
  7. sabarish

    Ben Pfaff Guest

    "sabarish" <> writes:

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


    This question has been beaten to death over the years. Try
    searching the archives.
    --
    "To get the best out of this book, I strongly recommend that you read it."
    --Richard Heathfield
    Ben Pfaff, Aug 1, 2005
    #7
  8. sabarish

    Eric Sosman Guest

    [OT] Re: find out the problem

    Richard Bos wrote:
    > Eric Sosman <> wrote:
    >
    >
    >>sabarish wrote:
    >>
    >>>Hi to all. find out the biggest among two numbers without using any
    >>>conditional statements and any relational operators.

    >>
    >> This cannot be done, not even by using non-portable
    >>trickery. The reason is simple: there is no such thing
    >>as the "biggest" of just two numbers. The superlative
    >>form of an adjective implies three or more alternatives.

    >
    >
    > No, they don't. Check the OED.


    No thanks; I've got other uses for $295.

    > What you describe is merely customary in
    > some circles, but not the only correct usage.


    "Some circles" meaning "Those who value English," I
    guess ...

    Does the OED list "irregardless?" Does it list "verb"
    as a transitive verb? Does it endorse the sportscasters'
    monstrous misuse of the present indicative for the subjunctive
    ("If I'm Alex Rodriguez I'm looking fast ball here")? We're
    down to the old prescriptive vs. descriptive debate, and I for
    one choose not use a description of other people's bad usage
    as a prescription for my own. Harrumph!

    --
    Eric Sosman, Aug 1, 2005
    #8
  9. sabarish

    akarl Guest

    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


    August
    akarl, Aug 1, 2005
    #9
  10. 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.

    --
    Keith Thompson (The_Other_Keith) <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.
    Keith Thompson, Aug 1, 2005
    #10
  11. sabarish

    Eric Sosman Guest

    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).

    --
    Eric Sosman, Aug 1, 2005
    #11
  12. "sabarish" <> 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) <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.
    Keith Thompson, Aug 1, 2005
    #12
  13. sabarish

    akarl Guest

    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
    akarl, Aug 1, 2005
    #13
  14. "Keith Thompson" <> wrote in message
    news:...
    > 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
    Alexei A. Frounze, Aug 1, 2005
    #14
  15. sabarish

    Jack Klein Guest

    On 1 Aug 2005 09:01:02 -0700, 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


    Complaint about missing ;

    > 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/~ajo/docs/FAQ-acllc.html
    Jack Klein, Aug 2, 2005
    #15
  16. Alexei A. Frounze wrote:
    > "Keith Thompson" <> wrote in message
    > news:...
    > > 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
    Krishanu Debnath, Aug 2, 2005
    #16
  17. "Krishanu Debnath" <> wrote in message
    news:...
    ....
    > > 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
    Alexei A. Frounze, Aug 2, 2005
    #17
  18. >> > 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
    Gordon Burditt, Aug 2, 2005
    #18
  19. Gordon Burditt sade:
    > 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.
    Tobias Blomkvist, Aug 2, 2005
    #19
  20. "Gordon Burditt" <> wrote in message
    news:...
    ....
    > 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
    Alexei A. Frounze, Aug 2, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wybo Dekker
    Replies:
    1
    Views:
    341
    Yukihiro Matsumoto
    Nov 15, 2005
  2. Stuart Clarke

    Slow Find.find - real problem

    Stuart Clarke, Sep 4, 2010, in forum: Ruby
    Replies:
    7
    Views:
    136
    Stuart Clarke
    Sep 6, 2010
  3. vdvorkin
    Replies:
    0
    Views:
    389
    vdvorkin
    Feb 10, 2011
  4. vdvorkin
    Replies:
    3
    Views:
    799
    vdvorkin
    Feb 14, 2011
  5. oldyork90

    find it, cut it out, find next

    oldyork90, Jan 16, 2012, in forum: Perl Misc
    Replies:
    5
    Views:
    376
    John W. Krahn
    Jan 22, 2012
Loading...

Share This Page