Wednesday, February 13, 2013

Adding numbers the hard way

I finally got to read the second part of Robey Pointer "How to add numbers" blog posts. Thinking about hardware "algorithms" can be interesting because distributed systems face similar problems sometimes. Below is my implementation of Kogge-Stone addition for 32 bits integers. Brent-Kung hybrid is very clever, but I couldn't figure out an obvious "step" for Brent-Kung that could be recursed into.
def add(x: Int, y: Int, cin: Boolean) = {
  def intToBooleanArray(n: Int): Array[Boolean] = {
    (0 until 32 map ((1).<<) map (n.&) map (0.!=)).toArray
  }

  val xs: Array[Boolean] = intToBooleanArray(x)
  val ys: Array[Boolean] = intToBooleanArray(y)

  // P means cout depends on cin
  // G means cout is 1 regardless of cin
  case class PG(p: Boolean, g: Boolean)
  def p(a: Boolean, b: Boolean) = a ^ b
  def g(a: Boolean, b: Boolean) = a & b

  // initial PG from input alone
  val pg0 = (xs, ys).zipped map ((a, b) => PG(g = g(a, b), p = p(a, b)))

  // Execute combine step until all PGs are final
  def combStep(lastPGs: Array[PG], finalPGs: Array[PG], step: Int): Array[PG] = {
    // Combines PGs formed by adjacent block of bits
    def comb(pga: PG, pgb: PG): PG = PG(p = pgb.p & pga.p, 
                                        g = pgb.g | (pgb.p & pga.g))

    if (lastPGs.isEmpty) finalPGs
    else {
      val (newFinalPGs, tempPGs) = lastPGs splitAt (step - step / 2)
      val nextPGs = (finalPGs ++ lastPGs, tempPGs).zipped map comb

      combStep(nextPGs, finalPGs ++ newFinalPGs, step << 1)
    }
  }

  val pgs = combStep(pg0, finalPGs = Array.empty, step = 1)

  // Carry for each bit
  def cout(cin: Boolean)(pg: PG): Boolean = pg.g | (pg.p & cin)
  val cn = pgs map cout(cin)

  // Final result for each bit
  val sn = (pg0 map (_.p), cin +: (cn take 31)).zipped map ((p, c) => p ^ c)

  // Convert boolean array back into an int
  val result = (sn.zipWithIndex map { 
    case (s, i) => if (s) 1 << i else 0
  }).sum
  (result, cn.last)
}

1 comment:

  1. I'm curious if you could use the same basic idea in adding really large numbers. Consider, adding 2 50 digit numbers. I'm assuming it wouldn't be worth doing in software, but still neat.

    ReplyDelete