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

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

Subscribe to:
Post Comments (Atom)

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