Long multiplication: Difference between revisions

=={{header|Scala}}==

This implementation does not rely on an arbitrary precision numeric type. Instead, only single digits

are ever multiplied or added, and all partial results are kept as string.

<lang scala>def addNums(x: String, y: String) = {

def rev(n: String) = n.reverse.padTo(x.length max y.length, "0").mkString

val (sum, carry) = (rev(x) zip rev(y)).foldLeft(("", 0)) {

case ((acc, carry), (dx, dy)) =>

val sum = dx.asDigit + dy.asDigit + carry

((sum % 10).toString + acc, sum / 10)

}

if (carry != 0) carry.toString + sum else sum

}

def multByDigit(num: String, digit: Int) = {

val (mult, carry) = num.reverse.foldLeft(("", 0)) {

case ((acc, carry), d) =>

val mult = d.asDigit * digit + carry

((mult % 10).toString + acc, mult / 10)

}

if (carry != 0) carry.toString + mult else mult

}

def mult(x: String, y: String) =

y.foldLeft("")((acc, digit) => addNums(acc + "0", multByDigit(x, digit.asDigit)))</lang>

Sample:

<pre>

scala> mult("18446744073709551616", "18446744073709551616")

res73: java.lang.String = 340282366920938463463374607431768211456

</pre>