Created
March 4, 2018 16:27
-
-
Save feyderm/f2b3ff2a4c1f7d03c34fff58b2f5296f to your computer and use it in GitHub Desktop.
Karatsuba multiplication algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| object Karatsuba { | |
| def main(args: Array[String]): Unit = { | |
| def loop(str1: String, str2: String): BigInt = { | |
| val n_digits1 = str1.length | |
| val n_digits2 = str2.length | |
| if (n_digits1 == 1 || n_digits2 == 1) { | |
| BigInt(str1) * BigInt(str2) | |
| } else { | |
| val min_split = List(n_digits1, n_digits2).map(_ / 2).min | |
| val (a, b) = str1.splitAt(n_digits1 - min_split) | |
| val (c, d) = str2.splitAt(n_digits2 - min_split) | |
| val step1 = loop(a, c) | |
| val step2 = loop(b, d) | |
| val step3 = loop( | |
| (BigInt(a) + BigInt(b)).toString, | |
| (BigInt(c) + BigInt(d)).toString | |
| ) | |
| val step4 = step3 - step2 - step1 | |
| val step5 = ( | |
| BigInt(step1.toString + ("0" * (min_split * 2))) | |
| + step2 | |
| + BigInt(step4.toString + ("0" * min_split)) | |
| ) | |
| step5 | |
| } | |
| } | |
| val is_neg = args.map(_.charAt(0) == '-') | |
| val num1 = args(0) | |
| val num2 = args(1) | |
| val ans = is_neg match { | |
| case Array(false, false) => loop(num1, num2) | |
| case Array(true, false) => loop(num1.drop(1), num2) * BigInt("-1") | |
| case Array(false, true) => loop(num1, num2.drop(1)) * BigInt("-1") | |
| case Array(true, true) => loop(num1.drop(1), num2.drop(1)) | |
| } | |
| println(ans) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment