The ugliest patch in the history (versión 2, salida decimal ejecutando python).
Según parche increiblemente vergonzoso. Imprime salida decimal utilizando
python, a quien alimentamos con nuestra salida en hexa para que nos devuelva el
decimal.
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.
Implementa programa principal.
Implementación del programa principal con Makefile incluido. Por omisión compila
optimizado (en modo 'release' digamos), para compilar con símbolos de debug (y
dándole bola al assert y eso) usar: make DEBUG=1
The ugliest patch ever.
Sí, es por lejos el parche más feo que hice en mi vida y no estoy nada
orgulloso, pero a esta altura no podemos ponernos en exquisitos =(
Implementa el constructor a partir de un string.
Lo hace a través de un parser que va construyendo el número grande evualuando un
polinomio de potencias de 10. El polinomio se evalua usando la Reglar de Horner).
Reescribe normalize_length().
Además de arreglar un bug, ahora normalize length también recorta los números si
tiene muchos ceros en la perte más significativa, de manera tal que no crezcan
exponencialmente (lo que acelera increíblemente las cosas).
Sigue dejando los números con tamaño potencia de 2, pero elimina todos los ceros
que puede en el camino.
Reimplementa operator< para que sea realmente const.
El operator< utilizaba la función normalize_length() que tomaba parámetros
variables. Ahora operator< es completamente const y no necesita normalizar los
argumentos.
Contempla suma de números de signo distinto.
Utiliza a la resta para manejar esos casos. En el test quedó un caso que rompe
tanto a la suma (como resta) como a la potencia (por un problema que, como
mínimo, baja hasta la multiplicación).
Potenciación con división y conquista.
Este parche agrega el algoritmo de potenciación por división y conquista. Además
agrega varios métodos y funciones complementarias:
dividido_dos(): devuelve el número dividido 2 O(n) (haciendo shift bit a bit)
es_impar(): indica si es impar O(1) (viendo el bit menos significativo)
operator==(): comparación O(n) (en el peor caso, que es cuando son iguales)
Bugfix en la suma.
Tenía un problema cuando el 2do operando era MAX - 1 y había carry, no se sumaba
nada y tampoco se detectaba que había carry (porque pega la vuelta
indefectiblemente, sin importar el valor del operando 1).
Agregar karatsuba() y pot_ko().
En este patch se reintroduce karatsuba() (todavia no probado porque falta la
resta, pero no deberia distar mucho de su implementacion final) y pot_ko(),
tampoco probada. Soy un loco barbaro.
Merge y limpieza.
Merge del parche que implementa K-O y limpieza de algunos \r y se ponen algunos
funciones como métodos. Si bien compila el test, puede explotar porque realmente
nunca está compilando la mayor parte de las cosas porque están parametrizadas y
no se usarn.
Estructura inicial y tipo básico.
Mini estructura de directorios con lo básico. Hay un tipo parametrizado
number< T > (diseñado para unsigned's, si anda con otra cosa es casualidad) que
ya tiene implementada la suma y una forma _muy_ precaria de imprimirse.
Lo básico como para empezar a trabajar.
projects / z.facultad / 75.29 / dale.git / log