Es un reemplazo del algoritmo de la escuela primaria para multiplicar números. de dígitos más grandes. El algoritmo de Karatsuba para el algoritmo de multiplicación rápida usando Divide and Conquer desarrollado por Anatolii Alexeevitch Karatsuba en 1960. Lo primero que se te ocurre es qué es y por qué está diseñado. Aunque hay 3 formas de multiplicar números:
- Algoritmo escolar de tercer grado Método (Standard-way)
- Método de algoritmo recursivo
- Método de multiplicación Karatsuba
¿Por qué el algoritmo de Karatsuba?
El objetivo del algoritmo está diseñado porque el espacio de diseño es sorprendentemente rico. Su complejidad de tiempo es la siguiente y no lo haga, ya que la complejidad de tiempo es muy importante y, a veces, se hace en las preguntas de la entrevista.
O(n^log2(3)) tiempo (~ O(n^1.585))
Donde n es el número de dígitos de los números que se multiplican. Se analiza multiplicando dos números enteros grandes para mostrar el funcionamiento interno paso a paso. El objetivo es reducir la complejidad del espacio en el que los términos de números enteros se dividirán de tal manera que x e y se dividan en un conjunto de dígitos, ya que la lógica detrás de esto es divide y vencerás. Si los números son más pequeños no hay necesidad de multiplicar, se prefiere la mutilación estándar de dos enteros.
El algoritmo está estandarizado para 4 dígitos en aras de la comprensión. Uno puede multiplicar tantos dígitos tomados en conjuntos.
Pasos del algoritmo:
- Calcular el conjunto inicial (a*c)
- Calcule el conjunto después del conjunto inicial, puede ser el conjunto final (b * d)
- Calcular conjunto inicial con conjuntos finales
- Reste los valores del paso 3 del paso 2 del paso 1
- Rellene (suma) 4 ceros al número obtenido en el paso 1, el valor del paso 2 no cambia y rellene dos ceros al valor obtenido en el paso 4.
Ahora propongamos los pasos anteriores y mostrémoslo con una ilustración antes de llegar a la parte de implementación.
Ilustración:
Input: x = 1234, y = 5678
Processing: As per above inputs x = 1234 y = 5678 a = 12, b = 34 c = 56, d = 78 Step 1: a * c = 172 Step 2: b * d = 2652 Step 3: (a+b)(c+d) = 134 * 36 = 6164 Step 4: 6164 - 2652 - 172 = 2840 Step 5: 1720000 + 2652 + 284000 = 7006652
Output: 7006652
El valor obtenido en el paso 5 es, de hecho, el producto obtenido si se realiza la multiplicación escolar estándar entre estos dos números ‘x’ e ‘y’.
1720000 + 2652 + 284000 = 7006652
Implementación : tenga en cuenta que no debe comprender las fórmulas establecidas para este algoritmo, sino comprenderlo de esta manera para mejorar.
Java
/// Java Program to Implement Karatsuba Algorithm
// Importing Random class from java.util packahge
import java.util.Random;
// MAin class
class GFG {
// Main driver method
public static long mult(long x, long y) {
// Checking only if input is within range
if (x < 10 && y < 10) {
// Multiplying the inputs entered
return x * y;
}
// Declaring variables in order to
// Find length of both integer
// numbers x and y
int noOneLength = numLength(x);
int noTwoLength = numLength(y);
// Finding maximum length from both numbers
// using math library max function
int maxNumLength
= Math.max(noOneLength, noTwoLength);
// Rounding up the divided Max length
Integer halfMaxNumLength
= (maxNumLength / 2) + (maxNumLength % 2);
// Multiplier
long maxNumLengthTen
= (long)Math.pow(10, halfMaxNumLength);
// Compute the expressions
long a = x / maxNumLengthTen;
long b = x % maxNumLengthTen;
long c = y / maxNumLengthTen;
long d = y % maxNumLengthTen;
// Compute all mutilpying variables
// needed to get the multiplication
long z0 = mult(a, c);
long z1 = mult(a + b, c + d);
long z2 = mult(b, d);
long ans = (z0 * (long)Math.pow(10, halfMaxNumLength * 2) +
((z1 - z0 - z2) * (long)Math.pow(10, halfMaxNumLength) + z2));
return ans;
}
// Method 1
// To calculate length of the number
public static int numLength(long n)
{
int noLen = 0;
while (n > 0) {
noLen++;
n /= 10;
}
// Returning length of number n
return noLen;
}
// Method 2
// Main driver function
public static void main(String[] args)
{
// Showcasing karatsuba multiplication
// Case 1: Big integer lengths
long expectedProduct = 1234 * 5678;
long actualProduct = mult(1234, 5678);
// Printing the expected and corresponding actual product
System.out.println("Expected 1 : " + expectedProduct);
System.out.println("Actual 1 : " + actualProduct + "\n\n");
assert(expectedProduct == actualProduct);
expectedProduct = 102 * 313;
actualProduct = mult(102, 313);
System.out.println("Expected 2 : " + expectedProduct);
System.out.println("Actual 2 : " + actualProduct + "\n\n");
assert(expectedProduct == actualProduct);
expectedProduct = 1345 * 63456;
actualProduct = mult(1345, 63456);
System.out.println("Expected 3 : " + expectedProduct);
System.out.println("Actual 3 : " + actualProduct + "\n\n");
assert(expectedProduct == actualProduct);
Integer x = null;
Integer y = null;
Integer MAX_VALUE = 10000;
// Boe creating an object of random class
// inside main() method
Random r = new Random();
for (int i = 0; i < MAX_VALUE; i++) {
x = (int) r.nextInt(MAX_VALUE);
y = (int) r.nextInt(MAX_VALUE);
expectedProduct = x * y;
if (i == 9999) {
// Prove assertions catch the bad stuff.
expectedProduct = 1;
}
actualProduct = mult(x, y);
// Again printing the expected and
// corresponding actual product
System.out.println("Expected: " + expectedProduct);
System.out.println("Actual: " + actualProduct + "\n\n");
assert(expectedProduct == actualProduct);
}
}
}
Product 1 : 85348320 Product 2 : 21726
Publicación traducida automáticamente
Artículo escrito por shivamraj74 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA