Algoritmo Básico

Si tienes curiosidad por conocer explora nuestra web

El algoritmo de karatsuba en java

Post publicado por Admin , a las 10:52 , este tema tiene 0 comentarios



Hay muchas aplicaciones de la ciencia moderna, como la criptografía y la transformada rápida de Fourier, que necesitan calcular las operaciones con números grandes. Los números utilizados en estas aplicaciones pueden subir a cientos o miles de dígitos. Multiplicación de un gran número requiere enormes recursos de tiempo y espacio. El estudio de los algoritmos de multiplicación rápida siempre ha sido una tarea importante y estudiada por los matemáticos y científicos de la computación. En la década de 1960, los matemáticos rusos descubrieron una forma más rápida para multiplicar dos números. La técnica se la atribuyó a Karatsuba (aunque su desarrollo de la idea está en disputa), por lo que la técnica se llama multiplicación de Karatsuba.

La idea del algoritmo es la siguiente:

x = x1*B^m + x0
y = y1*B^m + y0

donde x0 y y0 son menos de B^m. El producto entonces es:

xy = (x1*B^m + x0)(y1*B^m + y0)
xy = z2*B^2m + z1*B^m + z0

donde

z2 = x1*y1
z1 = x1*y1 + x0*y1
z0 = x0*y0

Estas fórmulas requieren de cuatro multiplicaciones, y era conocido por Charles Babbage. Karatsuba observó que xy se pueden calcular en solo tres multiplicaciones, a costa de algunas adiciones extras. Con z0 y z2.

z1 = (x1 + x0)*(y1 + y0) – z2 –z0

Que remplaza la expresión

z1 = x1*y1 + x0*y1

Por

z1 = (x1 + x0)*(y1 + y0) – x1*y1 –x0*y0

Y el resultado queda de esta manera

resultado = z2*B^2m + z1*B^m + z0

Ejemplo práctico:

Para calcular el producto de 12.345 y 6.789, elija B = 10 y m = 3. Luego se descomponen los operandos de entrada utilizando la base resultante (B^m = 1000), como:

12345 = 12 • 1000 + 345
6789 = 6 • 1000 + 789

Sólo tres multiplicaciones, que operan en números enteros más pequeños, se utilizan para calcular tres resultados parciales:

z2 = 12 × 6 = 72
z0 = 345 × 789 = 272 205
z1 = (12 + 345) × (6 + 789) - z2 - z0 = 357 × 795 - 72-272205 = 283815 - 72-272205 = 11538

resultado final

result = 72 · 1000^2 + 11538 · 1000 + 272205 = 83810205.

A continuación el algoritmo de karatsuba realizado en java:

public static BigInteger karatsuba(BigInteger num1, BigInteger num2) {
  int posiciones = Math.max(num1.bitLength(), num2.bitLength());
  //Para n menor que mil, es más eficiente la multiplicación normal.
  if (posiciones <= 1000) {
      return num1.multiply(num2);
  }
  posiciones = posiciones / 2;

  BigInteger b = num1.shiftRight(posiciones);
  BigInteger a = num1.subtract(b.shiftLeft(posiciones));
  BigInteger d = num2.shiftRight(posiciones);
  BigInteger c = num2.subtract(d.shiftLeft(posiciones));

  // Calculamos los resultados parciales
  BigInteger z0 = karatsuba(a, c); //z0=a*c
  BigInteger z1 = karatsuba(a.add(b), c.add(d)); //z1=(a+b)*(c+d)
  BigInteger z2 = karatsuba(b, d); //z2=b*d

  BigInteger result = z1.subtract(z2).subtract(z0); //z1-z2-z0

  // Se juntan los resultados parciales para obtener el resultado global.
  return z2.shiftLeft(2 * posiciones).add(result.shiftLeft(posiciones)).add(z0);
}


Enlaces relacionados:
alternativas al algoritmo de karatsuba podrías encontrarlo aquí
El algoritmo de karatsuba en java
El algoritmo de karatsuba en java - escrito por Admin , publicado en 10:52, categorizado como DivideyVenceras , Matematicos . y tiene 0 comentarios
No comment Add a comment
Copyright © 2015 Algoritmo Básico Todos los derechos reservados.
Si te gusta nuestra web, no te olvides de compartir nuestros post.

Desarrollado por Algoritmo Básico con la tecnología Blogger.