Welcome, guest | Sign In | My Account | Store | Cart

Used to multiply big integers (visible difference with >400bits).

C++, 137 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/* Alumno: Guillermo López Leal 2IM1
 * 
 * Karatsuba algorith: fast multiplication of large integers.
 * 
 * Sorry for the comments in Spanish, but I think the code is very legible ;)
 */
#include <iostream>
#include <math .h>
 
using namespace std;
 
/*
 * Función Power(double x, int y)
 * calcula el número que resulta de calcular
 * x elevado a y. Se realiza por recursión.
 * Devuelve un tipo T, que se supone será
 * un número: int, double, float...
 *
 */
int Power(int x, int y) {
	if (y == 0)
		return (1);
	else if (y == 1)
		return(x);
	else
		return(x * Power(x, y-1));
}
 
/*
 * Función Digitos (T n, int &dig)
 * calcula el número de dígitos (dig) que tiene el número n, que
 * podría ser cualquier tipo de número: int, float, double...
 * Devuelve el número de dígitos (int).
 * He preferido cambiar la función para que devuelva el número
 * de dígitos en vez de mostrarlo por pantalla ya que en el algoritmo de
 * Karatsuba es necesario saber el número de dígitos de un número.
 *
 */
 
int Digitos (int n, int &dig) {
	if (n < 10)	return (dig+1);
	else {
		dig++;
		return(Digitos(n/10, dig));
	}
}
 
/*
 * Recibimos el número de dígitos que queremos ver como últimos
 * y el número, claro
 * Devolvemos el módulo de dividir el número entre la potencia de 10
 * elevado al número de dígitos:
 * e.g. sacar los últimos 3 dígitos de 3454567:
 * 3454567 % power(10, 3) -> 3454567 % 1000 -> 567
 *
 */
int ultimos(int digitos, int &numero) {
	return numero % Power(10, digitos);
}
 
/*
 * Al igual que con los últimos, devolvemos los n primeros "digitos" de "numero".
 * para ello usamos algo simple: dividimos el número entre la potencia de 10 elevado
 * al número de dígitos que queremos sacar.
 *
 */
int primeros(int digitos, int &numero) {
	return numero/Power(10, digitos);
}
 
/*
 * Algoritmo de Karatsuba. Multiplicación rápida de enteros largos
 * @param: int &u -> pasamos por referencia uno de los números a multiplicar.
 * @param: int &v -> pasamos por referencia el segundo número.
 */
int multiplica (int &u, int &v) {
	int dig1=0, dig2=0;
	//División en trozos iguales de los números. Tenemos que dividir según
	//el mayor de ambos entre 2: 3457689 -> 345 y 7689
	//							 3455 -> 0 y 3455
	int numDigitos = max(Digitos(u, dig1), Digitos(v, dig2));
	//Caso base, cuando se puede hacer una multiplicación directa (1 cifra)
	//En teoría si se lograba beneficio con números de más de 300 bits, se podría
	//sustituir ese 1 por 300.
	if (numDigitos < = 1) return u*v;
	//Número de dígitos redondeados HACIA ARRIBA para sacar la división.
	//e.g -> 9 dígitos de máximo -> sacamos los 5 últimos y después los 4 primeros
	//NO podemos sacar los 4.5 mayores y los 4.5 menores
	numDigitos = (numDigitos / 2) + (numDigitos % 2);
	//Vamos calculando los diferentes w, x, y, z…
	int w = primeros(numDigitos, u);
	int x = ultimos(numDigitos, u);
	int y = primeros(numDigitos, v);
	int z = ultimos(numDigitos, v);
	//Operaciones intermedias
	int p=multiplica(w, y);
	int q=multiplica(x, z);
	int wMasx = w + x;
	int zMasy = z + y;
	//Volvemos a llamar al algoritmo hasta que (como se ve arriba en el if) lleguemos al
	//caso base de n=numDigitos=1. Llamada recursiva
	int r=multiplica(wMasx, zMasy);
	// Salida final, usamos la función Power implementada arriba
	return Power(10, 2*numDigitos)*p+Power(10, numDigitos)*(r-p-q)+q;
}
 
//Funcion aleatoria para sacar números aleatorios menores que el parámetro x
int MiRandom(int x)
{
	int Numero=0;
	Numero=(rand()%x);
	return Numero;
}
 
int main () {
	//Inicializamos la semilla apuntando al tiempo
	srand(time(NULL));
	int numero=0;
	//Menor que 46340 -> raiz(max_int)=raiz(2147483647)...
	//Obviamente podría funcionar con más de 46340, pero podría producirse overflow.
	//Sólo ocurriría en el caso de que la semilla hiciera dos 46341 -> bum!!
	// Se podría poner hasta semilla 2147483647 si se tuviera la suerte que el random
	// fuera 1 y 2147483647
	//Además es que hemos limitado a "int", si hubiéramos puesto un valor más grande, como
	//unsigned long long int, tendríamos valores perfectos y muy grandes
	cout < < "Número máximo a multiplicar (menor que 46341, leer código fuente) :";
	cin >> numero;
	//Creamos dos enteros aleatorios máximo "numero"
	int num1 = MiRandom(numero);
	int num2 = MiRandom(numero);
	//Les mostramos
	cout < < "\nnum1=" << num1;
	cout << "\nnum2=" << num2;
	//Les multiplicamos!
	cout << "\nEl resultado del producto es: " << multiplica(num1, num2);
	return EXIT_SUCCESS;
}
Created by Guillermo López on Thu, 2 Jul 2009 (MIT)
C++ recipes (21)
Guillermo López's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks