Lesson 09 · Comparing signed integers - Build an Arbitrary-Precision Integer Library

Comparing signed integers

A negative number is always below a positive one, and among negatives the bigger magnitude is the smaller number. Today you build the public Cmp on top of magnitude comparison.

The goal

Compare two BigInts and return -1, 0, or 1, dispatching on sign then magnitude.

Start here - the target

TO DO

Scenario: Signed comparison dispatches on sign, then magnitude with a flip for negatives

Giventhe BigInts -5 and 3

WhenCmp(-5, 3) is evaluated

Thenit returns -1

AndCmp(-5, -3) is -1 (a bigger magnitude is a smaller negative), Cmp(3, 3) and Cmp(0, 0) are 0, and Cmp(5, -100) is 1

Background

Sign dominates: if the two signs differ, the one with the larger sign value is greater and you are done - no need to look at magnitudes. Two zeros (sign 0) are equal. When the signs are equal and non-zero, the magnitudes break the tie, but with a twist for negatives: among negative numbers a larger magnitude is a smaller value (-5 < -3).

The clean way to handle that twist is to compare magnitudes and multiply the result by the shared sign: for two positives the magnitude order stands, and for two negatives it flips, exactly as it should. That one multiply turns four cases into one line and keeps the comparison total and consistent with the arithmetic you are about to build.

Make it work

func Cmp(x, y BigInt) int {
  if x.sign != y.sign {
    if x.sign < y.sign { return -1 }
    return 1
  }
  if x.sign == 0 { return 0 }
  c := cmpMag(x.mag, y.mag)
  // when both are negative, a larger magnitude means a smaller value
  return c * x.sign
}

CheckpointDONE

BigInts order correctly across signs. Commit and stop here.