• Eliter Lamer (unregistered) in reply to mykelyk
    mykelyk:
    Maybe I'm just feeding trolls however: 
    b even a*b = (2*a)*(b/2)
b odd  a*b = a + 2*a*b/2

int c = 0;
while (b != 0) {
    if (b%2)
        c += a;
     a <<= 1;
     b >>= 1;
     
}
return c + a;

    The problem with this code is it is restriced to multiplying in base 2. We can easily generalize it to be valid for any base:

    int multiply (int a, int b, int base) {
    int result = 0;
    while (b != 0) {
        while (b % base != 0) {
            result += a;
            --b;
        }
        a *= base;
        b /= base; 
    }
    return result;
}

    Now you don't need to update your code every time you swap out your CPU for one in a different base.

  • Al H. (unregistered)

    Wouldn't simply n = -n be about the simplest, easiest to read, most language/compiler neutral and perhaps fastest way to go?

  • (cs) in reply to Al H.
    Al H.:
    Wouldn't simply n = -n be about the simplest, easiest to read, most language/compiler neutral and perhaps fastest way to go?
    n=-n => n=0
  • John Muller (unregistered) in reply to ckelloug
    ckelloug:
    People have a lot of misconceptions about processor math. Generally speaking some ops are slower than others. This table was gleaned from reading architecture manuals from Intel, AMD, MIPS, and HP PA-RISC in the course of my owrk over the last 10 years.

    Generally For double precision floating points ops processors made before this year:

    Add: 1 cycle Subtract: 1 cycle Multiply: 1 cycle Divide: 32 cycles using hardware iterative radix 2 division +FP pipe stall on x86 (No stall on newer PA-Risc) Integer Modulo: 32 cycles (uses Floating Point hardware) + FP pipe stall on x86 Square Root: 32 cycles (Executed using Divide Unit) +FP pipe stall on x86 Trig Functions: Varies up to 100-200 cycles

    Some Intel processors released in the last year use higher radix division algorithms and finish FP double divide in 16 cycles.

    Don't believe internet pundits on this topic if it matters to you. Go read the processor architecture manual and read the assembler being generated by your compiler and work it out doing timing tests if there are questions.

    That why when comparing distances between coplaner points instead of the "sqrt(a^2+b^2) > c" that I used years ago, I use "a^2 + b^2 > c^2".

    I would hope that compilers would generally optimize any divisions by a constant into a multiplication by the precomputed recipricol of the constant... but dividing by a variable would kill perf.

  • Twey (unregistered)

    I can't believe it took so much code to perform such a basic task. Every fool knows how to do simple negation of a number.

    All you have to do is implement elementary Peano numbers...

    data UnsignedInt = Zero | Succ UnsignedInt
data SignedInt = Plus UnsignedInt | Minus UnsignedInt


intToSigned :: Int -> SignedInt
intToSigned n | n < 0     = Minus mag
              | otherwise = Plus mag

  where mag = intToUnsigned $ abs n

signedToInt :: SignedInt -> Int
signedToInt (Minus mag) = (-1) * (unsignedToInt mag)
signedToInt (Plus  mag) = unsignedToInt mag

intToUnsigned :: Int -> UnsignedInt
intToUnsigned 0 = Zero
intToUnsigned n | n < 0     = error "Negative numbers not allowed"
                | otherwise = Succ (intToUnsigned $ n - 1)

unsignedToInt :: UnsignedInt -> Int
unsignedToInt Zero     = 0
unsignedToInt (Succ n) = 1 + unsignedToInt n

negateSigned :: SignedInt -> SignedInt
negateSigned (Plus  n) = Minus n
negateSigned (Minus n) = Plus  n

negateInt :: Int -> Int
negateInt n = signedToInt (negateSigned $ intToSigned n)

negateSigned :: SignedInt -> SignedInt
negateSigned (Plus  n) = Minus n
negateSigned (Minus n) = Plus  n

    Then, it's nothing more than:

    negateInt :: Int -> Int
negateInt n = signedToInt (negateSigned $ intToSigned n)

    Ah, but this isn't enterprisey enough, and besides, it doesn't have enough LoC — I'm sure no company would buy that! Let's do it in Java...

    class UnsignedInt {
    public UnsignedInt dec = null;

    private UnsignedInt() {}

    public UnsignedInt(UnsignedInt n) {
        dec = n;
    }

    public UnsignedInt succ() {
        return new UnsignedInt(this);
    }

    public int toInt() {
        UnsignedInt cur = this;
        int ret = 0;

        for (; cur != ZERO; cur = cur.dec)
            ++ret;

        return ret;
    }

    public static UnsignedInt fromInt(int n) {
        UnsignedInt ret = ZERO;

        for (; n > 0; --n)
            ret = ret.succ();

        return ret;
    }

    public static final UnsignedInt ZERO = new UnsignedInt();
}

class SignedInt {
    public enum Sign { PLUS, MINUS };
    public final Sign direction;
    public final UnsignedInt magnitude;

    public SignedInt(Sign sign, UnsignedInt num) {
        direction = sign;
        magnitude = num;
    }

    public SignedInt negate() {
        return new SignedInt(direction == Sign.PLUS ? Sign.MINUS : Sign.PLUS, magnitude);
    }

    public int toInt() {
        return magnitude.toInt() * (direction == Sign.PLUS ? 1 : -1);
    }

    public static SignedInt fromInt(int n) {
        return new SignedInt(n < 0 ? Sign.MINUS : Sign.PLUS, UnsignedInt.fromInt(n * (n < 0 ? -1 : 1)));
    }
}

    ... and to negate a number:

    int negatedNumber = SignedInt.fromInt(nonNegatedNumber).negate().toInt();

    Easy as pie. All those geniuses in professional software development, and they couldn't even think up an obvious technique like that? shakes head sadly

    P.S. Cookies to anyone who can work XML into the solution, for increased agile workflow synergy!

  • fluxythewalrus (unregistered) in reply to snoofle

    -(-LOL)

  • mgm (unregistered) in reply to eb0ny
    eb0ny:
    ciph3r:
    You're all wrong! *shakes head* over-complicating! *mumbles to self*

    dblVal = val * 2; for(int i=0;i<dblVal;i++) val--;

    THERE!

    val = -13

    What now?

    CAPTHA: ingenium

    the solution is pretty obvious,

    negate(val) {
     dblVal = val * 2;
     for(int i=0;i<absolute(dblVal);i++)
          val-=dblVal/absolute(dblVal);
}

absolute(val) {
     if(val<0) return negate(val);
     return val;
}</pre>
  • Jesper (unregistered)

    This made me think of The Millisecond Converter which I submitted a few years ago.

  • (cs)

    A lot of negativity in the responses today...

  • (cs) in reply to JamesCurran
    JamesCurran:
    The size independent method of taking the 1s compliment is "return ~n;"
    Why "return" anything? You'd have to have written a function to wrap a built-in operation. Do you also say things like this? 
    int add(int a, int b) { return a+b; }
  • What is that man? (unregistered)

    I am personally guilty of this, though not nearly to the same extent as the poor people who wrote the functions in this article...

    I once did:

    double negateNum(double num) {
  return num-(num*2);
}

    The most depressing part of it all for me was that I pride myself on successful and simple solutions to difficult problems with my programming (though negating a number is far from difficult >__>), and at the time this seriously seemed like the best way to negate a number. A colleague was looking through my code later and was like, "Dude, what's this? Just multiply by negative one." I did perhaps the biggest facepalm in the history of facepalms.

Leave a comment on “Classic WTF: The Challenges of Negation”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article