Posted By

josepino on 04/14/11


Tagged

number numbers numeros algorithm n Large digit multiply Karatsuba grandes digitos


Versions (?)

Multiplication of large numbers (Multiplicación de números grandes)


 / Published in: Java
 

An example of Karatsuba algorithm for multiplication of n digit numbers.

  1. import java.math.BigInteger;
  2. import java.util.Random;
  3. import java.io.*;
  4.  
  5. public class Karatsuba {
  6.  
  7. /**
  8.   * MÃ��Ã�©todo que mediante la tÃ��Ã�©cnica divide y vencerÃ��Ã�¡s, multiplica dos nÃ��Ã�ºmeros
  9.   * muy grandes tras una serie de pasos.
  10.   * @param u BigInteger Entero grande 1.
  11.   * @param v BigInteger Entero grande 2.
  12.   * @return BigInteger Resultado
  13.   * JOSE PINO
  14.   */
  15. public static BigInteger karatsuba(BigInteger u, BigInteger v) {
  16. int posiciones = Math.max(u.bitLength(), v.bitLength());
  17.  
  18. //Para n menor que mil, es m���¡s eficiente la multiplicaci���³n normal.
  19. if (posiciones <= 1000) {
  20. return u.multiply(v);
  21. }
  22. posiciones = posiciones / 2;
  23.  
  24. /*
  25.   * Repartimos en trocitos:
  26.   * u = w * 2^n + x
  27.   * v = y * 2^n + z
  28.   */
  29.  
  30. BigInteger w = u.shiftRight(posiciones);
  31. BigInteger x = u.subtract(w.shiftLeft(posiciones));
  32. BigInteger y = v.shiftRight(posiciones);
  33. BigInteger z = v.subtract(y.shiftLeft(posiciones));
  34.  
  35. // Calculamos los resultados parciales
  36. BigInteger p = karatsuba(w, y); //p=w*y
  37. BigInteger q = karatsuba(x, z); //q=x*z
  38. BigInteger r = karatsuba(x.add(w), z.add(y)); //r=(x+w)*(z+y)
  39. BigInteger z1 = r.subtract(p).subtract(q); //r-p-q
  40.  
  41. // Se juntan los resultados parciales para obtener el resultado global.
  42. return p.shiftLeft(2 * posiciones).add(z1.shiftLeft(posiciones)).add(q);
  43. }
  44.  
  45. public static void main(String[] args) {
  46. Random rnd = new Random();
  47.  
  48. System.out.println("ALGORITMO DE KARATSUBA");
  49. System.out.println("----------------------");
  50.  
  51. System.out.print(
  52. "Introduzca un n���ºmero de bits(Sugerencia: A poder ser mayor que 1000): ");
  53.  
  54.  
  55. try {
  56. String numero = br.readLine();
  57.  
  58. int N = Integer.parseInt(numero);
  59.  
  60. //Creamos dos n���ºmeros al azar de N cifras.
  61. BigInteger x = new BigInteger(N, rnd);
  62. BigInteger y = new BigInteger(N, rnd);
  63.  
  64. //System.out.println("Numero 1: " + x);
  65. //System.out.println("\n\nNumero 2: " + y);
  66. System.out.println("Multiplicamos...");
  67.  
  68. //Mediremos los tiempos de Karatsuba y Multiplicaci���³n normal para ver las diferencias.
  69. long t = System.nanoTime();
  70.  
  71. //z ser���­a el resultado. Hacemos la llamada al m���©todo.
  72. BigInteger z = karatsuba(x, y);
  73.  
  74. t = System.nanoTime() - t;
  75. System.out.printf("\nEl valor de X es: %d " , x);
  76. System.out.printf("\nEl valor de Y es: %d " , y);
  77. System.out.printf("\nEl resultado de X*Y mediante Karatsuba es: %d " , z);
  78. System.out.println("\n\n\nN = " + N);
  79. System.out.println("\n\n\nN = " + N);
  80. System.out.println("Karatsuba: tiempo = " + t);
  81.  
  82. t = System.nanoTime();
  83. z = x.multiply(y);
  84. t = System.nanoTime() - t;
  85. System.out.println("Multiplicaci���³n Normal: tiempo = " + t);
  86.  
  87. }
  88. System.err.println("Atenci���³n: Car���¡cter no valido.");
  89. System.exit( -1);
  90. }
  91. catch (IOException ioe) {
  92. System.err.println("Error de E/S");
  93. System.exit( -1);
  94. }
  95. catch (Exception e) {
  96. System.err.println("Error inesperado. " + e.getMessage());
  97. System.exit( -1);
  98. }
  99. }
  100. }

Report this snippet  

You need to login to post a comment.