Programación en C, algoritmia -- 2
Budget: €8 – €30 EUR
Realizar un algoritmo empleando divide y vencerás para calcular raíces cuadradas de números de precisión arbitraria, que se simularán con un array de N enteros, donde se almacena la cifra menos significativa en el índice más bajo, empleando el algoritmo aprendido en la escuela para calcular raíces cuadradas, y usando Karatsuba para hacer los productos de números de varias cifras que aparezcan en los cálculos intermedios, y las sumas y restas usando las funciones que se vieron cuando se hizo karatsuba.
1. Escribir el pseudocódigo del algoritmo, que dado un número A de N cifras devuelva su raíz cuadrada entera y el resto de la misma, con sendos arrays, que también supondremos de N cifras, aunque en realidad tendrán menos.
2. Traducirlo a C de modo que pueda obtener la raíz cuadrada del entero pasado como parámetro.
3. Calcular el tiempo necesario en función de N, suponiendo conocido el tiempo de Karatsuba (N^log_2(3)), etc., es decir sólo hay que calcular el tiempo de la raíz, el resto se pueden poner directamente.
Ejemplo:
$ ./raiz 12345678908774589652145236985412
(3513641829893108,1157118531085748)
1. Escribir el pseudocódigo del algoritmo, que dado un número A de N cifras devuelva su raíz cuadrada entera y el resto de la misma, con sendos arrays, que también supondremos de N cifras, aunque en realidad tendrán menos.
2. Traducirlo a C de modo que pueda obtener la raíz cuadrada del entero pasado como parámetro.
3. Calcular el tiempo necesario en función de N, suponiendo conocido el tiempo de Karatsuba (N^log_2(3)), etc., es decir sólo hay que calcular el tiempo de la raíz, el resto se pueden poner directamente.
Ejemplo:
$ ./raiz 12345678908774589652145236985412
(3513641829893108,1157118531085748)