DevPinoy.org
A Filipino Developers Community
Forums » Community Central » The Lounge » Programming Trivia's » Trivia for the weekend: MIN and MAX without conditional statements
   

Trivia for the weekend: MIN and MAX without conditional statements

rated by 0 users
This post has 23 Replies | 0 Followers

Top 10 Contributor
Posts 2,038
Points 42,030
Reply
keithrull replied on 02-20-2006 7:59 PM

I had to admit, that exercise mad me think.. although i didn't get the correct answer! but still, its one of those 'rust-busters' you tend to like! thanks for the trivia/puzzle chris!

Lets setup the point system! also.. prizes anyone? any local sponsors?

devpinoy sig

  • | Post Points: 5
Top 10 Contributor
Posts 545
Points 8,945
Reply
cvega replied on 02-20-2006 8:05 PM

I didn't use Math.Abs since I think it uses conditionals, just like Array.Sort. Anyone ILDASM'ed this?

UPDATE: Here's the relevant decompiled code, from .NET Reflector:

public static int Abs(int value)
{
      if (value >= 0)
      {
            return value;
      }
      return Math.AbsHelper(value);
}

private static int AbsHelper(int value)
{
      if (value >= 0)
      {
            return value;
      }
      if (value == -2147483648)
      {
            throw new OverflowException(Environment.GetResourceString("Overflow_NegateTwosCompNum"));
      }
      return -value;
}

Mapapaaway ba ako dito? Just in the interest of correctness. Stick out tongue [:P]
The concept of absolute number is to get the distance of a number from zero, hence making the number as always positive number, i.e., 99 and -99 is 99 far from zero, thus both are equivalent with each other in absolute concept.

The decompilation of Math.Abs has a conditional statement because of two's complement's way of reversing all the bits when it is negative, but of course we can also write a function that can get rid of sign of a number without conditional statement as a replcement for Math.Abs function Smile [:)]

-chris
Chris Vega This posting is provided "AS IS" with no warranties, and confers no rights My Weblog|Visit MSDN Community
  • | Post Points: 20
Top 10 Contributor
Posts 2,038
Points 42,030
Reply
keithrull replied on 02-20-2006 8:06 PM

punzie wrote:
I didn't use Math.Abs since I think it uses conditionals, just like Array.Sort. Anyone ILDASM'ed this?

UPDATE: Here's the relevant decompiled code, from .NET Reflector:

public static int Abs(int value)
{
      if (value >= 0)
      {
            return value;
      }
      return Math.AbsHelper(value);
}

private static int AbsHelper(int value)
{
      if (value >= 0)
      {
            return value;
      }
      if (value == -2147483648)
      {
            throw new OverflowException(Environment.GetResourceString("Overflow_NegateTwosCompNum"));
      }
      return -value;
}

Mapapaaway ba ako dito? Just in the interest of correctness. Stick out tongue [:P]

hehehe Stick out tongue [:P] i was supposed to post this! heheh! nice one punzie!

devpinoy sig

  • | Post Points: 20
Top 10 Contributor
Posts 545
Points 8,945
Reply
cvega replied on 02-20-2006 8:36 PM
keithrull wrote:
hehehe Stick out tongue [:P] i was supposed to post this! heheh! nice one punzie!

There are two formula in the solution, the second formula didn't used the Math.Abs() function and it is purely done using basic arithmetic and bit manipulations.

In any case, Math.Abs, Array.Sort and Array.GetItem (indexing) are all using conditional statements internally, and Math.Abs is the only function that didn't use loop, hence making the second approach as the only accurate solution if we include conditional statement intenally Smile [:)]

-chris
Chris Vega This posting is provided "AS IS" with no warranties, and confers no rights My Weblog|Visit MSDN Community
  • | Post Points: 5
Top 50 Contributor
Posts 50
Points 815
Reply
punzie replied on 02-20-2006 8:38 PM
cvega wrote:

I didn't use Math.Abs since I think it uses conditionals, just like Array.Sort. Anyone ILDASM'ed this?

UPDATE: Here's the relevant decompiled code, from .NET Reflector:

public static int Abs(int value)
{
      if (value >= 0)
      {
            return value;
      }
      return Math.AbsHelper(value);
}

private static int AbsHelper(int value)
{
      if (value >= 0)
      {
            return value;
      }
      if (value == -2147483648)
      {
            throw new OverflowException(Environment.GetResourceString("Overflow_NegateTwosCompNum"));
      }
      return -value;
}

Mapapaaway ba ako dito? Just in the interest of correctness. Stick out tongue [:P]
The concept of absolute number is to get the distance of a number from zero, hence making the number as always positive number, i.e., 99 and -99 is 99 far from zero, thus both are equivalent with each other in absolute concept.

The decompilation of Math.Abs has a conditional statement because of two's complement's way of reversing all the bits when it is negative, but of course we can also write a function that can get rid of sign of a number without conditional statement as a replcement for Math.Abs function Smile [:)]

-chris


Yes it's possible, but it's not an obvious implementation like just zeroing the sign-bit (as in one's complement). The one presenting the solution using Math.Abs should probably also present proof that it can be implemented without conditionals? Maybe as the next puzzle? Smile [:)]


  • | Post Points: 20
Top 25 Contributor
Posts 98
Points 1,415
Reply
CryptoKnight replied on 02-20-2006 8:51 PM
we can implement the Abs function this way...

    int MyAbs(int a)
    {
       return (int)Math.Sqrt(a*a);
    }

or...

    (int)Math.Pow(a * a, .5);

I was supposed to use Math.Sign() but after looking it up through reflector, it also uses conditional expressions.
  • | Post Points: 20
Top 50 Contributor
Posts 50
Points 815
Reply
punzie replied on 02-20-2006 9:39 PM
int MyAbs(int x)
{
    int signBit = (x >> 31) & 1;
    // When sign bit is 0 (positive), returns same number
    // When sign bit is 1 (negative), returns 2's complement
    // (i.e. gets negative of negative number = positive number)
    return (x ^ -signBit) + signBit;
}

  • | Post Points: 20
Top 10 Contributor
Posts 545
Points 8,945
Reply
cvega replied on 02-20-2006 10:39 PM

That's nice one punzie, mine is identical to your approach:

int abs(int v)
{
    int sbit = v >> 31;
    return (v ^ sbit) - sbit;
}

And below is from the book "Bits and Bytes":

int abs(int v)
{
    return v * sign(v);
}

int sign(int v)
{
    // I was thinking why the author of the book uses
    // v ^ ~v when it always returns -1, and then
    // multiply it back again to -1?
    //
    // return -1 * ( ( v ^ ~v ) - ( ( v >> 31 ) * 2) );

    // So I revised it, it's much simplier this way:
    return 1 + ( ( v >> 31 ) * 2 );
}

-chris

Chris Vega This posting is provided "AS IS" with no warranties, and confers no rights My Weblog|Visit MSDN Community
  • | Post Points: 20
Top 25 Contributor
Posts 98
Points 1,415
Reply
CryptoKnight replied on 02-20-2006 11:04 PM
hmm... i'll go for readability & maintainability... as they say... simplicity is beauty... Stick out tongue [:P]
good thing there's Min, Max, etc.
  • | Post Points: 5
Previous | Next
Page 2 of 2 (24 items) < Previous 1 2 | RSS
Copyright DevPinoy 2005-2008