The Artima Developer Community
Sponsored Link

Scala Buzz
Adding numbers the hard way

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
Daniel Sobral

Posts: 80
Nickname: 57409
Registered: Aug, 2008

Daniel Sobral is an old dog trying to learn new tricks.
Adding numbers the hard way Posted: Feb 12, 2013 11:39 PM
Reply to this message Reply

This post originated from an RSS feed registered with Scala Buzz by Daniel Sobral.
Original Post: Adding numbers the hard way
Feed Title: Algorithmically challenged
Feed URL: http://dcsobral.blogspot.com/feeds/posts/default
Feed Description: Random thoughts of an IT worker in the stone age of computer science.
Latest Scala Buzz Posts
Latest Scala Buzz Posts by Daniel Sobral
Latest Posts From Algorithmically challenged

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

Read: Adding numbers the hard way

Topic: xsbt-proguard-plugin - taking over, new release Previous Topic   Next Topic Topic: Veripacks 0.2: exporting subpackages


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us