@@ -0,0 +1,1009 @@
+%0Apublic class Karatsuba %7B%0A%09%0A%09/**%0A%09 * Returns product of num1 and num2.%0A%09 * Gives running time of O(n%5E1.585) as opposed %0A%09 * to O(n%5E2) of %22grade school%22 multiplication.%0A%09 * This implementation only works for four-digit numbers.%0A%09 */%0A%09public long karatsuba(long num1, long num2) %7B%0A%09%09if (num1 %3C 10 %7C%7C num2 %3C 10) %7B%0A%09%09%09return num1 * num2;%0A%09%09%7D%0A%09%09%0A%09%09/* calculates the size of the numbers */%0A%09%09double m = Math.round(Long.toString(num1).length());%0A%09%09double m2 = m/2;%0A%09%09%0A%09%09/* split the digit sequences about the middle */%0A%09%09long a = (long) (num1 / Math.pow(10, Math.round(m2)));%0A%09%09long b = (long) (num1 %25 Math.pow(10, Math.round(m2)));%0A        long c = (long) (num2 / Math.pow(10, Math.round(m2)));%0A%09%09long d = (long) (num2 %25 Math.pow(10, Math.round(m2)));%0A%0A%09%09/* 3 calls made to numbers approximately half the size */%0A%09%09long z0 = karatsuba(a, c);%0A%09%09long z1 = karatsuba(b, d);%0A%09%09long z2 = karatsuba(a+b, c+d);%0A%0A        return ((long) ((z0*Math.pow(10, Math.round(m)))+((z2-z1-z0)*Math.pow(10, Math.round(m2)))+z1));%0A%09%7D%0A%0A%7D

Add Karatsuba Multiplication