Ståle’s weblog

I am an avid reader of The Daily WTF, and recently there was a small challenge posted on the site. It deals with something called Russian multiplication. The explanation on the site is much better to understand than something I could reproduce myself, so I urge you to read the full text there. Basically, in order to multiply 2 numbers, you set them in 2 columns. You then add a row with half and double of the first and second number in the previous row. Keep doing that until you have reached 1. Here is a simple table example for 47*131:

You then add all the numbers in the second column, when the number in the first column is odd, 131 + 262 + 524 + 1048 + 4192 = 6157.

Now to create a small Scala program that can solve this. First, I need a method that just produces the table above. This is rather simple to create:

1
2

def sumParts(a:Int, b:Int): List[(Int,Int)] = 
    if (a==0) List() else (a,b) :: sumParts(a/2, b*2)

Notice the list type here is (Int, Int), which indicates it’s a list of tuples. If you have used scripting languages, you might be aware of tuples already. Tuples in Scala allows us to define a list like type with fixed size, and fixed type for each value. This is a tuple of 2 Ints, and the actual type off the method is a List of tuples, each with 2 Ints. If we send 47,131 as arguments to this method, we will get List((47,131), (23,262), (11,524), (5,1048), (2,2096), (1,4192)) in return. We can now iterate over this list to create a presentable output:

1
2
3
4

val numbers = sumParts(47, 131)
for ((a,b) <- numbers) {
    println("% 8d % 8d %5s" format(a, b, if (a%2==1) "*" else ""))
}

Which produces this output:

      47      131     *
      23      262     *
      11      524     *
       5     1048     *
       2     2096
       1     4192     *

To format the output nicely, I use the format operator on the string. I have used the “%” operator to format stuff extensivly when printing in python, so I was happy to find the same functionality easily available in Scala. It would be nice if they also added a “%” overloaded method for RichString in Scala for this. I also use an if to print out a “*” next to each number that should be included in the addition. Next we need to filter out the numbers we actually need for the addition, and add them together.

1
2
3

val addNums = for ((a,b) <- numbers; if (a%2==1)) yield b
val sum = (0 /: addNums) (_+_)
println("Numbers: %s, ansver: %d" format(addNums mkString(" + "), sum))

To get addNums, we use a for loop, and Scalas powerfull pattern matching. The for syntax is (item <- iterable). Instead of accessing each entry as a tuple, we use the (a,b) pattern to indicate the shape to Scala. The shape of the List ([(Int, Int)]) matches this, and each value in the tuple will be unpacked into a and b. When then filter on values where a is odd, and yield b. We will then have a list of only those numbers that had a corresponding odd number in our original table. Using mkString we can create a presentable String version off those numbers, and using the fold operator we add the numbers together.

It's also possible to create a smaller method for just calculating the sum from the list of parts returned by sumParts:

1

def calc(a: Int, b: Int) = (0 /: (sumParts(a,b) filter(_._1%2==1))) (_+_._2)

Here I fold on the tuples, so I need to use _2 to access the 2nd value off the tuple.

Finally, here is the program in full, accepting 2 numbers on the command line. No error checking and verification is present in this version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

object RussianMultiplication {
    def sumParts(a:Int, b:Int): List[(Int,Int)] =
        if (a==0) List() else (a,b) :: sumParts(a/2, b*2)
 
   def main(args: Array[String]) {
        val numbers = sumParts(args(0) toInt,args(1) toInt)
        for ((a,b) <- numbers) {
            println("% 8d % 8d %5s" format(a, b, if (a%2==1) "*" else ""))
        }
        val addNums = for ((a,b) <- numbers; if (a%2==1)) yield b
        val sum = (0 /: addNums) (_+_)
        println("Numbers: %s, ansver: %d" format(addNums mkString(" + "), sum))
    }
}

Staale Programming, Scala Scala, TheDailyWTF