Multiplication In different Way

In computer science and mathematics, there are multiple ways to perform multiplication, especially when considering binary operations, algorithms, and hardware-specific optimizations. Some of the common methods for multiplication include:

1. Basic Long Multiplication (Traditional method)
2. Multiplication Using a Loop ()
3. Multiplication using Recursive ()
4. Multiplication Using Logarithms ()
5. Russian Peasant Multiplication (also known as Ancient Egyptian multiplication)
6. Booth's Multiplication Algorithm (optimized for signed binary numbers)
7. Karatsuba Algorithm (efficient for large numbers)
8. Shift-and-Add Multiplication (binary multiplication based on shifting)
9. Matrix Multiplication
10. FFT-based Multiplication (used for multiplying large numbers)
11. Divide-and-Conquer Multiplication (splitting large numbers)

I'll walk through each method briefly and provide code examples where relevant.

1. Basic Long Multiplication (Traditional Method)

This is the method taught in schools. It works by multiplying each digit of one number by each digit of the other and adding up the results, accounting for their positions.

Java Code Example:

java

public class LongMultiplication {       public static long multiply(long a, long b) {         return a * b;     }       public static void main(String[] args) {         long result = multiply(123456789L, 987654321L);         System.out.println("Long Multiplication Result: " + result);     } }

 

This uses Java’s in-built multiplication operator, which internally uses this method.

 

2. Multiplication Using a Loop (multiplyUsingForLoop)

This method mimics multiplication using repeated addition. It adds the first number to itself the second number of times.

Java Code Example:

java

public static final long multiplyUsingForLoop(int a, int b) {     int absoluteSecondData = Math.abs(b);     long result = a;     for (int i = 1; i < absoluteSecondData; i++) {         result += a;     }     return (b < 0) ? -result : result; }

 

This uses Java’s in-built multiplication operator, which internally uses this method.

3. Recursive Multiplication (multiplyUsingRecursive)

This method performs multiplication recursively, repeatedly adding the first number until it reaches the second number.

Java Code Example:

java

public class RecursiveMultiplication {       // Recursive function to multiply a and b     public static int multiply(int a, int b) {         // Base case: if b is 0, the result is 0         if (b == 0) {             return 0;         }                 // Recursive case: add 'a' and call multiply with b-1         if (b > 0) {             return a + multiply(a, b - 1);         }           // For negative b, we add a and multiply(a, b + 1) to handle negative cases         return -multiply(a, -b);     }       public static void main(String[] args) {         // Test the function with two numbers         int a = 3;         int b = 4;                 int result = multiply(a, b);         System.out.println(a + " * " + b + " = " + result);     } }

 

Recursive Multiplication Explanation

Ø  If b=0, then a×b=0 (base case).

Ø  Otherwise, a×b=a+(a×(b−1)) for b>0.

Example: Multiplying 3 and 4 Recursively

To multiply 3 and 4:

Ø  3×4=3+(3×3)

Ø  3×3=3+(3×2)

Ø  3×2=3+(3×1)

Ø  3×1=3+(3×0)

Ø  3×0=0 (base case)

Explanation:

1. Base case: When b=0, the result is 0.
2. Recursive case: The function adds a and calls itself with b−1 until it reaches the base case.
3. Handling negative numbers: If b is negative, we flip the sign by recursively calling with -b.

Example for Negative Numbers:

If we want to multiply 3 and -4, the function will still work correctly by flipping the sign internally.

Efficiency Consideration:

This method has a time complexity of O(b), where b is the second operand. It’s straightforward and easy to understand, though not as efficient as the Karatsuba algorithm for large numbers.

 

4. Multiplication Using Logarithms (multiplyUsingLogirithms)

This method uses logarithms to perform multiplication. The logarithmic property used here is: 

\(log_{10}(a×b)=log_{10}(a)+log_{10}(b)\).

Java Code Example:

java

public static final long multiplyUsingLogirithms(int a, int b) { // Handle zero case explicitly      if (a == 0 || b == 0) { return 0; }     long absoluteFirstData = Math.abs(a);     long absoluteSecondData = Math.abs(b);     long result = Math.round(Math.pow(10, (Math.log10(absoluteFirstData) + Math.log10(absoluteSecondData))));     return (a > 0 && b > 0 || a < 0 && b < 0) ? result : -result; }

 

This Java method attempts to multiply two integers using logarithms instead of traditional multiplication. Here's a detailed explanation of the code:

1. Input Handling:

Ø  The function takes two integers a and b.

Ø  First, it calculates the absolute values of a and b to simplify the process:

long absoluteFirstData = Math.abs(a);

long absoluteSecondData = Math.abs(b);

2. Logarithmic Multiplication:

Ø  The multiplication is done using the logarithmic identity: \(log_{10}(a×b)=log_{10}(a)+log_{10}(b)\)

Ø  Instead of multiplying the numbers directly, it calculates:

long result = Math.round(Math.pow(10, (Math.log10(absoluteFirstData) + Math.log10(absoluteSecondData))));

ü  First, it calculates log10 of both numbers.

ü  Then, it adds the two logarithms.

ü  After that, it raises 10 to the power of the sum to calculate the result, which simulates multiplication.

3. Adjusting the Sign:

Ø  The method then handles the sign of the result:

return (a > 0 && b > 0 || a < 0 && b < 0) ? result : -result;

ü  If both a and b are either positive or both negative, the result is positive.

ü  If one is positive and the other is negative, the result is negative.

4. Potential Issues:

Ø  Floating-Point Precision: The logarithmic approach can introduce precision issues because log10 and pow operate on floating-point numbers. This might cause slight inaccuracies for large numbers.

Ø  Handling Zero: This method doesn’t handle the case where one or both of the numbers is 0. You should add a check at the beginning to return 0 if either a or b is 0:

This method now:

Ø  Handles the multiplication of zero properly.

Ø  Uses logarithms to multiply two numbers, although the traditional multiplication (a * b) is much faster and more accurate in practice.

 

Suppose we want to multiply 12 and 34. Here's how the method would calculate the result.

Example: Multiplying 12 and 34

Given numbers:

Ø  a=12

Ø  b=34

Step 1: Calculate Absolute Values

long absoluteFirstData = Math.abs(12);   // absoluteFirstData = 12

long absoluteSecondData = Math.abs(34);  // absoluteSecondData = 34

Step 2: Apply Logarithms

We use base-10 logarithms (log10) to transform the multiplication into addition. Here's the key mathematical identity:

$$log_{10}(a×b)=log_{10}(a)+log_{10}(b)$$

Now, calculate the logarithms of 12 and 34:

Ø  \(log_{10}(12)≈1.07918\)

Ø  \(log_{10}(34)≈1.53148\)

Step 3: Add the Logarithms

Add the results of the two logarithms:

1.07918+1.53148=2.61066

Step 4: Exponentiate the Sum

Raise 10 to the power of the sum of the logarithms:

\(10^{2.61066}≈407.999\)

Since this is using floating-point arithmetic, rounding it gives us 408.

Step 5: Sign Adjustment

Finally, adjust the sign based on the original values of a and b. In this case, both numbers are positive, so the result remains positive:

result=408

Verification with Traditional Multiplication

Using traditional multiplication:

12×34=408

This uses Java’s in-built multiplication operator, which internally uses this method.

 

5. Russian Peasant Multiplication (Ancient Egyptian)

This method works by halving one number and doubling the other until the first number reaches 1. If a halved number is odd, the corresponding doubled value is added to the result.

Algorithm Steps:

• Halve the first number (ignore the remainder).
• Double the second number.
• If the first number is odd, add the second number to the result.

Java Code Example:

java

public class RussianPeasantMultiplication {       public static long multiply(long a, long b) {         long result = 0;                 while (a > 0) {             if ((a % 2) != 0) { // If a is odd                 result += b;             }             a = a / 2;             b = b * 2;         }                 return result;     }       public static void main(String[] args) {         long result = multiply(18, 25);         System.out.println("Russian Peasant Multiplication Result: " + result);     } }

 

Steps:

1. Halve the first number (discarding fractions) and double the second number repeatedly.
2. If the first number is odd, add the second number to the result.
3. Stop when the first number becomes zero.

Example: 18 × 25

Step	First Number	Second Number	Add to Result?	Result
1	18	25	No	0
2	9	50	Yes	50
3	4	100	No	50
4	2	200	No	50
5	1	400	Yes	450
6	0	--	--	450

 

So, 18 × 25 = 450.

Code Explanation:

Ø  The algorithm continues until the first number (a) becomes 0.

Ø  If the first number is odd, it adds the second number (b) to the result.

Ø  Then, it halves the first number and doubles the second number in each iteration.

Time Complexity:

Ø  Time Complexity: O(loga), because in each step, the value of a is halved, which means the loop runs approximately loga times.

Key Features:

Ø  Efficient for large numbers due to the halving and doubling operations.

Ø  It uses basic arithmetic and no complex algorithms, making it a simple, historical method for multiplication.

6. Booth’s Multiplication Algorithm

Booth's algorithm is used to perform binary multiplication, particularly for signed numbers. It uses bit manipulation to multiply two numbers efficiently by encoding the multiplier.

Java Code Example:

java

public class BoothMultiplication {       public static int boothMultiply(int multiplicand, int multiplier) {         int m = multiplicand;         int r = multiplier;         int n = Integer.SIZE; // Number of bits in integers                 int A = m << n;         int Q = r;         int Q1 = 0;         int M = m << n;                 for (int i = 0; i < n; i++) {             int LSB = Q & 1;             if (LSB == 1 && Q1 == 0) {                 A = A - M;             } else if (LSB == 0 && Q1 == 1) {                 A = A + M;             }             Q1 = LSB;             int shift = ((A & (1 << (2 * n - 1))) != 0) ? 1 : 0;             A = (A << 1) | (Q >> (n - 1));             Q = (Q << 1) | shift;         }                 return A >> n;     }       public static void main(String[] args) {         int result = boothMultiply(3, -6);         System.out.println("Booth's Multiplication Result: " + result);     } }

 

This is an optimized binary multiplication algorithm for signed numbers.

7. Karatsuba Algorithm

The Karatsuba algorithm is a faster divide-and-conquer algorithm for multiplying large numbers. It reduces the multiplication of two n-digit numbers to at most three multiplications of n/2-digit numbers.

Java Code Example:

java

public class KaratsubaMultiplication {       public static long karatsuba(long x, long y) {         if (x < 10 || y < 10) {             return x * y;         }           int n = Math.max(Long.toString(x).length(), Long.toString(y).length());         int halfN = n / 2;           long a = x / (long) Math.pow(10, halfN);         long b = x % (long) Math.pow(10, halfN);         long c = y / (long) Math.pow(10, halfN);         long d = y % (long) Math.pow(10, halfN);           long ac = karatsuba(a, c);         long bd = karatsuba(b, d);         long adbc = karatsuba(a + b, c + d) - ac - bd;           return ac * (long) Math.pow(10, 2 * halfN) + adbc * (long) Math.pow(10, halfN) + bd;     }       public static void main(String[] args) {         long result = karatsuba(12345678, 87654321);         System.out.println("Karatsuba Multiplication Result: " + result);     } }

 More information karatsubas-algorithm-for-multiplying

8. Shift-and-Add Multiplication (Binary)

This method involves shifting the multiplier and adding the multiplicand to the result if the corresponding bit in the multiplier is 1. It is a basic binary multiplication method used in hardware.

Java Code Example:

java

public class ShiftAndAddMultiplication {       public static long multiply(long multiplicand, long multiplier) {         long result = 0;           while (multiplier > 0) {             if ((multiplier & 1) == 1) {                 result += multiplicand;             }             multiplicand <<= 1; // Multiply multiplicand by 2             multiplier >>= 1; // Divide multiplier by 2         }           return result;     }       public static void main(String[] args) {         long result = multiply(15, 12);         System.out.println("Shift-and-Add Multiplication Result: " + result);     } }

 

9. Matrix Multiplication

This involves multiplying matrices. If matrix A is of size m x n and matrix B is of size n x p, their product matrix C will be of size m x p.

In matrix multiplication, the elements in the resulting matrix are computed by multiplying the corresponding row elements of the first matrix by the column elements of the second matrix.

Matrix Multiplication Java Example:

java

public class MatrixMultiplication {       public static int[][] multiplyMatrices(int[][] matrixA, int[][] matrixB) {         int rowsA = matrixA.length;         int colsA = matrixA[0].length;         int colsB = matrixB[0].length;                 int[][] result = new int[rowsA][colsB];           for (int i = 0; i < rowsA; i++) {             for (int j = 0; j < colsB; j++) {                 for (int k = 0; k < colsA; k++) {                     result[i][j] += matrixA[i][k] * matrixB[k][j];                 }             }         }           return result;     }       public static void printMatrix(int[][] matrix) {         for (int[] row : matrix) {             for (int val : row) {                 System.out.print(val + " ");             }             System.out.println();         }     }       public static void main(String[] args) {         int[][] matrixA = {             {1, 2, 3},             {4, 5, 6}         };                 int[][] matrixB = {             {7, 8},             {9, 10},             {11, 12}         };           int[][] result = multiplyMatrices(matrixA, matrixB);         System.out.println("Resultant Matrix:");         printMatrix(result);     } }

 

Output:

Resultant Matrix: 58 64 139 154

 

10. FFT-based Multiplication

This method uses the Fast Fourier Transform (FFT) to multiply large numbers efficiently. It is used in applications like multiplying large polynomials.

FFT-based Multiplication is used to multiply two large numbers by treating them as polynomials. Fast Fourier Transform (FFT) allows for fast convolution, which is used to multiply the two polynomials. Here's a simplified version using complex numbers and FFT.

For simplicity, we'll use the built-in Apache Commons Math library to handle FFT in Java. This requires adding the following dependency to your project (Maven example):

xml

<dependency>     <groupId>org.apache.commons</groupId>     <artifactId>commons-math3</artifactId>     <version>3.6.1</version> </dependency>

 

FFT-based Multiplication Java Example:

java

import org.apache.commons.math3.complex.Complex; import org.apache.commons.math3.transform.*;   public class FFTMultiplication {       public static int[] multiply(int[] a, int[] b) {         int n = 1;         while (n < a.length + b.length) n <<= 1; // Get next power of 2           Complex[] A = new Complex[n];         Complex[] B = new Complex[n];                 for (int i = 0; i < a.length; i++) A[i] = new Complex(a[i], 0);         for (int i = a.length; i < n; i++) A[i] = Complex.ZERO;                 for (int i = 0; i < b.length; i++) B[i] = new Complex(b[i], 0);         for (int i = b.length; i < n; i++) B[i] = Complex.ZERO;           FastFourierTransformer fft = new FastFourierTransformer(DftNormalization.STANDARD);                 // Perform FFT on both arrays         Complex[] FA = fft.transform(A, TransformType.FORWARD);         Complex[] FB = fft.transform(B, TransformType.FORWARD);                 // Multiply the results         Complex[] FC = new Complex[n];         for (int i = 0; i < n; i++) {             FC[i] = FA[i].multiply(FB[i]);         }           // Perform inverse FFT to get the result         Complex[] resultComplex = fft.transform(FC, TransformType.INVERSE);           // Extract the real part and round         int[] result = new int[n];         for (int i = 0; i < n; i++) {             result[i] = (int) Math.round(resultComplex[i].getReal());         }           return result;     }       public static void main(String[] args) {         int[] poly1 = {3, 2, 5}; // 5x^2 + 2x + 3         int[] poly2 = {5, 1, 2}; // 2x^2 + x + 5                 int[] result = multiply(poly1, poly2);                 System.out.println("Result of Polynomial Multiplication:");         for (int val : result) {             System.out.print(val + " ");         }     } }

 

Output:

Result of Polynomial Multiplication: 15 13 29 9 10

 Steps:

1. Zero-padding: Extend both input arrays to the nearest power of two to ensure that the FFT works correctly.
2. FFT Transform: Use FFT to transform both polynomials from the time domain to the frequency domain.
3. Point-wise Multiplication: Multiply the transformed arrays element by element.
4. Inverse FFT: Use the inverse FFT to transform the result back into the time domain.
5. Extract Real Parts: Since the result is complex, we take the real part of each element and round it to the nearest integer.

Example:

Polynomial 1:

\(5x^{2}+2x+3\)

Polynomial 2:

\(2x^{2}+x+5\)

Expected result:

$$(5x^{2}+2x+3)×(2x^{2}+x+5)=10x^{4}+9x^{3}+29x^{2}+13x+15$$

So the expected output array for the coefficients will be: 15,13,29,9,10

11. Divide-and-Conquer Multiplication

This method splits numbers into parts, multiplies them recursively, and combines the results. Karatsuba multiplication is a more efficient form of this method.

In Divide-and-Conquer Multiplication, we split large numbers into smaller parts, multiply them recursively, and combine the results. The Karatsuba algorithm is a well-known divide-and-conquer multiplication technique, which reduces the number of multiplications required.

Karatsuba Algorithm Java Example:

java

public class KaratsubaMultiplication {       public static long karatsuba(long x, long y) {         if (x < 10 || y < 10) {             return x * y;         }           int n = Math.max(Long.toString(x).length(), Long.toString(y).length());         int halfN = n / 2;           // Split x into a and b, and y into c and d         long a = x / (long) Math.pow(10, halfN);         long b = x % (long) Math.pow(10, halfN);         long c = y / (long) Math.pow(10, halfN);         long d = y % (long) Math.pow(10, halfN);           // Recursively calculate products         long ac = karatsuba(a, c);         long bd = karatsuba(b, d);         long adbc = karatsuba(a + b, c + d) - ac - bd;           return ac * (long) Math.pow(10, 2 * halfN) + adbc * (long) Math.pow(10, halfN) + bd;     }       public static void main(String[] args) {         long x = 12345678;         long y = 87654321;           long result = karatsuba(x, y);         System.out.println("Karatsuba Multiplication Result: " + result);     } }

 

Output:

Karatsuba Multiplication Result: 1082152022374638

 

These are some of the multiple ways to perform multiplication, depending on the specific use case, size of the numbers, and whether you're working in hardware or software environments.