Scala Buzz

0 replies on 1 page.

 Previous Topic Next Topic
 Flat View: This topic has 0 replies on 1 page
Daniel Sobral

Posts: 80
Nickname: dcsobral
Registered: Aug, 2008

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

 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

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