From: Alberto Bertogli <albertogli@telpin.com.ar>
Date: Wed, 5 Oct 2005 08:25:37 +0000 (+0000)
Subject: Cambiar pot_dyc() por pot_dyc_n() y pot_dyc_k().
X-Git-Tag: Entrega_1~9
X-Git-Url: https://git.llucax.com/z.facultad/75.29/dale.git/commitdiff_plain/fd08b581ae86ad918c68140a68849b37b1b3b2e4

Cambiar pot_dyc() por pot_dyc_n() y pot_dyc_k().
El enunciado nos pide que se construyan dos versiones del algoritmo de
potenciacion por division y conquista que hagamos: una para la multiplicacion
naif y otra para la multiplicacion por Karatsuba-Ofman.
Este patch toma la funcion pot_dyc() y arma con ella las dos pedidas. Ademas
actualiza main.cpp y number.cpp acorde.
---

diff --git a/src/main.cpp b/src/main.cpp
new file mode 100644
index 0000000..c573549
--- /dev/null
+++ b/src/main.cpp
@@ -0,0 +1,81 @@
+
+#include "number.h"
+#include <cstdlib>
+#include <iostream>
+#include <fstream>
+#include <sstream>
+
+using namespace std;
+
+void imprimir_integrantes();
+void procesar(istream& is, ostream& os);
+
+int main(int argc, char* argv[])
+{
+	// Verifico parámetros.
+	if (argc < 3)
+	{
+		cerr << "Faltan argumentos. Uso: " << argv[0]
+			<< " [archivo_entrada] [archivo_salida]\n";
+		return EXIT_FAILURE;
+	}
+	ifstream ifs(argv[1]);
+	if (!ifs) // No se abrió bien
+	{
+		cerr << "No se puede abrir el archivo " << argv[1] << "\n";
+		return EXIT_FAILURE;
+	}
+	ofstream ofs(argv[2]);
+	if (!ofs) // No se abrió bien
+	{
+		cerr << "No se puede abrir el archivo " << argv[2] << "\n";
+		return EXIT_FAILURE;
+	}
+	imprimir_integrantes();
+	procesar(ifs, ofs);
+	return EXIT_SUCCESS;
+}
+
+void procesar(istream& is, ostream& os)
+{
+	string linea;
+	while (getline(is, linea))
+	{
+		istringstream iss(linea.c_str());
+		char operador;
+		string str_op1, str_operador, str_op2;
+		iss >> str_op1 >> operador >> str_op2;
+		number<> op1 = str_op1;
+		number<> op2 = str_op2;
+		switch (operador)
+		{
+			case '+':
+				os << op1 + op2 << "\n";
+				break;
+			case '-':
+				os << op1 - op2 << "\n";
+				break;
+			case '*':
+				os << naif(op1, op2) << "\n";
+				break;
+			case 'k':
+				os << karatsuba(op1, op2) << "\n";
+				break;
+			case '^':
+				os << pot_dyc_n(op1, op2) << "\n";
+				break;
+			case 'q':
+				os << pot_dyc_k(op1, op2) << "\n";
+				break;
+		}
+	}
+}
+
+void imprimir_integrantes()
+{
+	cout <<
+"Alberto Bertogli 84107\n\
+Ezequiel González 79872 \n\
+Leandro Lucarella 77891 \n";
+}
+
diff --git a/src/number.h b/src/number.h
index e9b821f..9286255 100644
--- a/src/number.h
+++ b/src/number.h
@@ -792,7 +792,7 @@ number < N, E > pot_ko(number< N, E > &u, number< N, E > &v)
  *
  */
 template < typename N, typename E >
-number< N, E > pot_dyc(const number< N, E > &x, const number< N, E > &y)
+number< N, E > pot_dyc_n(const number< N, E > &x, const number< N, E > &y)
 {
 	assert(y.sign == positive);
 	//std::cout << "pot(" << x << ", " << y << ")\n";
@@ -801,15 +801,41 @@ number< N, E > pot_dyc(const number< N, E > &x, const number< N, E > &y)
 		std::cout << "y es 1 => FIN pot(" << x << ", " << y << ")\n";
 		return x;
 	}
-	number< N, E > res = pot_dyc(x, y.dividido_dos());
+	number< N, E > res = pot_dyc_n(x, y.dividido_dos());
 	//std::cout << "y.dividido_dos() = " << y.dividido_dos() << "\n";
 	//std::cout << "res = " << res << "\n";
-	res *= res;
+	res = naif(res, res);
 	//std::cout << "res = " << res << "\n";
 	if (y.es_impar())
 	{
 		//std::cout << y << " es IMPAR => ";
-		res *= x; // Multiplico por el x que falta
+		res = naif(res, x); // Multiplico por el x que falta
+		//std::cout << "res = " << res << "\n";
+	}
+	//std::cout << "FIN pot(" << x << ", " << y << ")\n\n";
+	return res;
+}
+
+/* Idem que pot_dyc_n(), pero usa karatsuba() para las multiplicaciones. */
+template < typename N, typename E >
+number< N, E > pot_dyc_k(const number< N, E > &x, const number< N, E > &y)
+{
+	assert(y.sign == positive);
+	//std::cout << "pot(" << x << ", " << y << ")\n";
+	if (y == number< N, E >(1))
+	{
+		//std::cout << "y es 1 => FIN pot(" << x << ", " << y << ")\n";
+		return x;
+	}
+	number< N, E > res = pot_dyc_k(x, y.dividido_dos());
+	//std::cout << "y.dividido_dos() = " << y.dividido_dos() << "\n";
+	//std::cout << "res = " << res << "\n";
+	res = karatsuba(res, res);
+	//std::cout << "res = " << res << "\n";
+	if (y.es_impar())
+	{
+		//std::cout << y << " es IMPAR => ";
+		res = karatsuba(res, x);
 		//std::cout << "res = " << res << "\n";
 	}
 	//std::cout << "FIN pot(" << x << ", " << y << ")\n\n";
diff --git a/tests/number.cpp b/tests/number.cpp
index dd9b450..0bbcb37 100644
--- a/tests/number.cpp
+++ b/tests/number.cpp
@@ -33,17 +33,17 @@ int main()
 
 	assert(N2 == K2);
 
-	//std::cout << "nu^nu2 = "  << pot_dyc(A, B) << "\n\n";
+	//std::cout << "nu^nu2 = "  << pot_dyc_n(A, B) << "\n\n";
 
 	number<> X = 0xff;
 	number<> Y = 0xff;
 	std::cout << "r = " << naif(X, Y) << "\n\n";
 
 #if 1
-	number <>rd = pot_dyc(X, Y);
-	std::cout << "x `pot_dyc` y = " << rd << "\n\n";
-	number <>rc = pot_ko(X, Y);
-	std::cout << "x `pot_ko` y = " << rc << "\n\n";
+	number <>rd = pot_dyc_n(X, Y);
+	std::cout << "x `pot_dyc_n` y = " << rd << "\n\n";
+	number <>rc = pot_dyc_k(X, Y);
+	std::cout << "x `pot_dyc_k` y = " << rc << "\n\n";
 	if (!(rc == rd)) {
 		printf("Las pot NO DAN\n");
 	} else {