From fd08b581ae86ad918c68140a68849b37b1b3b2e4 Mon Sep 17 00:00:00 2001 From: Alberto Bertogli Date: Wed, 5 Oct 2005 08:25:37 +0000 Subject: [PATCH] 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. --- src/main.cpp | 81 ++++++++++++++++++++++++++++++++++++++++++++++++ src/number.h | 34 +++++++++++++++++--- tests/number.cpp | 10 +++--- 3 files changed, 116 insertions(+), 9 deletions(-) create mode 100644 src/main.cpp 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 +#include +#include +#include + +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 { -- 2.43.0