Tuesday, May 17, 2022

Engineers of #bharat - wake up - know #whoweare - part I

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.


 

/*

* 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 = x1*b^m + x0

         * y = y1*b^m + y0

         * ----------

         * Using the above example,

         * x1 = 123

         * x0 = 45

         * ----------

         * y1 = 67

         * y2 = 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 x*y. 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 = Integer.toString((int)x);

                        String yString = Integer.toString((int)y);

                        // Local variables

                        long         m = max(xString.length(), yString.length()), // the maximum # of digits

                                        m2 = m/2, // the middle; if the number is odd, it will floor the fraction

                                        high1 = Integer.parseInt(strCopy(m2, xString)[0]), // the most significant digits. this is the scalar multiplier for b^m2

                                        low1 = Integer.parseInt(strCopy(m2, xString)[1]), // the least significant digits. this is what is added on to high1*b^m2

                                        high2 = Integer.parseInt(strCopy(m2, yString)[0]), // same for y

                                        low2 = Integer.parseInt(strCopy(m2, yString)[1]), // same for y

                                        // Three recursive calls

                                        z0 = karatsuba(low1, low2), // z0 = x0y0

                                        z2 = karatsuba(high1, high2), // z2 = x1y1

                                        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




No comments: