package com.examples.algorithms object MergeSortAlgorithm { def merge(left: List[Int], right: List[Int]): List[Int] = { (left, right) match { case (l, Nil) => l case (Nil, r) => r case(l :: l1, r :: r1) => if(l < r) l :: merge(l1, right) else r :: merge(left, r1) } } def run(input: List[Int]): List[Int] = { val n = input.length / 2 if (n == 0) input else { val (left, right) = input splitAt n merge(run(left), run(right)) } } }
0 Comments
package com.examples.algorithms object KarastubaAlgorithm { /** * calculate a,b,c,d such that x = pow(10, n/2).a + b ; y = pow(10, n/2).c + d * calculate ac, bd, (a+d)(b+d) recursively * x.y = pow(10,n).ac + pow(10, n/2)(ad + bc) + bd * @param x input of size n digits * @param y input of size n digits * @return product of x & y */ def run(x: Long, y: Long): Long = { val digits = math.log10(x) // we can take x or y to compute if(digits > 1) { val factor = math.pow(10, digits / 2).toInt val a = x / factor val b = x % factor val c = y / factor val d = y % factor val ac = run(a, c) val bd = run(b, d) val aPlusBTimesCPlusD = run(a + b, c + d) ac * factor * factor + bd + (aPlusBTimesCPlusD - ac - bd ) * factor } else { x * y } } } |
Archives
October 2016
Categories
All
|