The following text has been taken from Wiki:

“The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.[1][2][3] It reduces the multiplication of two n-digit numbers to at most

{\displaystyle n^{\log _{2}3}\approx n^{1.58}}

single-digit multiplications in general (and exactly

{\displaystyle n^{\log _{2}3}}

when n is a power of 2).

It is therefore asymptotically faster than the traditional algorithm, which requires

{\displaystyle n^{2}}

single-digit products. For example, the Karatsuba algorithm requires 310 = 59,049 single-digit multiplications to multiply two 1024-digit numbers (n = 1024 = 210), whereas the traditional algorithm requires (210)2 = 1,048,576 (~17.758 times faster).

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n.

Here is an implementation of this algorithm in Java.

Here's the formatted Java code for the Karatsuba algorithm:

/**
 * The Karatsuba algorithm is a multiplication algorithm developed by Anatolii Alexeevitch Karatsuba in 1960.
 * It operates in O(n^log2(3)) time (~ O(n^1.585)), with n being the number of digits of the numbers we are multiplying together.
 * Standard grade-school multiplication operates in O(n^2) time. Karatsuba's method is asymptotically much faster.
 * Normally, you can choose any base you want, but we will be using base 10 in this algorithm with m varying depending on the length of the inputs.
 * Specific details are included with an example in the comments before the actual method.
 * 
 * @author Ayamin
 */
public class Karatsuba {

    // Takes two integers and returns the maximum of them
    public static int max(int x, int y) {
        return (x > y) ? x : y;
    }

    // Takes a string and an index.
    // The index in this case is the "m". It will count backwards from the last (least significant) digit and split the string there.
    // It will return a 2-element array of the split string.
    // For example: Given 12345 as the string and 2 as the index, it will split the string into the string array ["123", "45"].
    // This is so the 123 can be written as 123 * 10^m, with m = 2 the index.
    public static String[] strCopy(long index, String string) {
        String first = "", last = "";
        long actualIndex = string.length() - index;
        for (int i = 0; i < actualIndex; i++) {
            first += string.charAt(i);
        }
        for (int i = (int) actualIndex; i < string.length(); i++) {
            last += string.charAt(i);
        }
        return new String[]{first, last};
    }

    // An exponent function. Works the same way as Math.pow, but with 64bit integers instead of double precision floats.
    public static long power(long x, long y) {
        if (y == 0) return 1;
        else {
            long answer = 1;
            for (int i = 1; i <= y; i++) {
                answer *= x;
            }
            return answer;
        }
    }

    /**
     * Take two numbers, x and y.
     * Example: 12345 and 6789.
     * Find a base b and power m to separate it into.
     * We'll pick base = 10, and m to be half the length of the digits of the numbers in this implementation of the algorithm.
     * In this case, m will be 2, so 10^2 = 100. We will split the 2 numbers using this multiplier.
     * The form we want is:
     * x = x1b^m + x0
     * y = y1b^m + y0
     * ----------
     * Using the above example,
     * x1 = 123
     * x0 = 45
     * ----------
     * y1 = 67
     * y0 = 89
     * ----------
     * b = 10 and m = 2
     * ----------
     * Thus:
     * 12345 = 123 * 10^2 + 45
     * 6789 = 67 * 10^2 + 89
     * 
     * The recursive algorithm is as follows:
     * 
     * If x < 10 or y < 10, return xy. Single digit multiplication is the base case.
     * Otherwise:
     * Let z2 = karatsuba(x1, y1). x1 and y1 are the most significant digits, and are the local variables "high".
     * Let z0 = karatsuba(x0, y0). x0 and y0 are the least significant digits, and are the local variables "low".
     * Let z1 = karatsuba(x1 + y0, x0 + y1) - z0 - z2.
     * And the result is the following sum:
     * z2 * b^2m + z1 * b^m + z0
     * 
     * @param x The multiplicand.
     * @param y The multiplier.
     * @return The product.
     */
    public static long karatsuba(long x, long y) {
        // Base case: single digit multiplication
        if (x < 10 || y < 10) {
            return x * y;
        }
        // Recursive case: Decompose the problem by splitting the integers and applying the algorithm on the parts.
        else {
            // Convert the numbers to strings so we can compute the # of digits of each number.
            // Note: We could also use floor(log10(n) + 1) to compute the #digits, but remember that we need to split the numbers too.
            String xString = Long.toString(x);
            String yString = Long.toString(y);

            // Local variables
            long m = max(xString.length(), yString.length()); // the maximum # of digits
            long m2 = m / 2; // the middle; if the number is odd, it will floor the fraction

            long high1 = Long.parseLong(strCopy(m2, xString)[0]); // the most significant digits. this is the scalar multiplier for b^m2
            long low1 = Long.parseLong(strCopy(m2, xString)[1]); // the least significant digits. this is what is added on to high1b^m2
            long high2 = Long.parseLong(strCopy(m2, yString)[0]); // same for y
            long low2 = Long.parseLong(strCopy(m2, yString)[1]); // same for y

            // Three recursive calls
            long z0 = karatsuba(low1, low2); // z0 = x0y0
            long z2 = karatsuba(high1, high2); // z2 = x1y1
            long z1 = karatsuba((low1 + high1), (low2 + high2)) - z2 - z0; // z1 = (x0 + y1)(x1 + y0) - z2 - z0, courtesy of Karatsuba

            return (z2 * power(10, 2 * m2) + (z1 * power(10, m2)) + z0);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(Karatsuba.karatsuba(200, 200));
        System.out.println(Karatsuba.karatsuba(12345, 6789));
        System.out.println(Karatsuba.karatsuba(2358925, 1259174));
    }
}

Result:

The Comparision:

Please see the comparison done by some of the college professors of #Bharat

And look at the algorithm that our forefathers had developed thousands of years back, which was actually unbeatable for so many years afterward.

So, my earnest request to the engineers of #Bharat

Know your real worth.

Go back to the roots.

Embrace #Sanskrit

And now you will realize why my wife is learning Sanskrit to teach my currently 11-years-old son so that he can learn Vedic algorithms from the original Sanskrit script

And now the surprises for the people of #universe.

Please have a look at the document that follows to get an idea.

I am happy to see that the teaching community of Bharat are coming forward to reclaim who we are

Enjoy