En esa que hace poco hago una entrevista técnica por teléfono para una compañía internacional y me preguntaron 3 cosas en el tiempo que duró, pero solo fui capaz de responder a 1 satisfactoriamente. De las otras dos, la primera fue: En una hipotética plataforma móvil con poca memoria y donde solo se dispone de enteros, nos encontramos con que no disponemos de una librería matemática, ¿sabría usted realizar un algoritmo para calcular raíces cuadradas?
Mi estupefacción en ese momento fue considerable y le dije que internet estaría lleno de esa clase de algoritmos. Obviamente me dijo que en esta hipotética situación, no se podía acceder a internet. Así que me sinceré y le dije que posiblemente llevaba sin calcular una raíz cuadrada desde los 12 años. Oh tonto de mí, que varias horas después pensé en un primer método muy sencillo por fuerza bruta, y varios minutos después en uno un poco menos bruto.
El método más bruto es empezar desde el cero, calcular el cuadrado de la victima actual, comprobar si es mayor o igual el resultado al número que deseamos calcular, si es menor pasamos a la siguiente víctima, sino miramos a ver si el resultado es igual, en ese caso se devuelve la victima actual, sino la anterior. Esta forma sencilla se le puede ocurrir a cualquier persona, pero supongo que los nervios siempre juegan una mala pasada. La otra solución es:
#include <iostream>
#include <vector>
unsigned Square(unsigned x) { return x * x; }
void FindSquareRootRange(
unsigned victim, unsigned baseResult,
unsigned & nextLower, unsigned & nextUpper
) {
unsigned prevOffset = 0, nextOffset = 1;
while(Square(nextOffset + baseResult) < victim) {
prevOffset = nextOffset;
nextOffset <<= 1;
}
nextLower = baseResult + prevOffset;
nextUpper = baseResult + nextOffset;
}
unsigned SquareRoot(unsigned victim) {
if(victim < 2) {
return victim;
} else {
unsigned lower = 0, upper = victim;
do {
FindSquareRootRange(victim, lower, lower, upper);
} while(upper - lower > 1);
return Square(upper) == victim ? upper : lower;
}
}
int main(int agrc, char ** argv) {
const unsigned MAX_VICTIM = 1000000;
const unsigned MAX_RESULTS = 1000;
std::vector<unsigned> results[MAX_RESULTS];
for(unsigned i = 0; i < MAX_VICTIM; ++i) {
unsigned currentResult = SquareRoot(i);
results[currentResult].push_back(i);
}
for(unsigned i = 0; i < MAX_RESULTS; ++i) {
if(!results[i].empty()) {
std::cout << "Sqrt(" << results[i][0] << ".."
<< results[i][results[i].size() - 1]
<< ") = " << i << "\t\t"
<< ((Square(i) == results[i][0]) ?
"true" : "false")
<< std::endl;
}
}
return 0;
}
La idea sigue siendo similar a la primera de fuerza bruta, solo que la forma de seleccionar nuestra próxima víctima cambia. En vez de ir de uno en uno, vamos usando las potencias de 2, para obtener un rango de valores donde podría estar el resultado, hasta que este rango se componga de como mucho 2 valores. Entonces cogemos y tomamos de esos dos valores el que más cerca esté sin pasarse.
Horas después de encontrar la solución de este problema, encontré una idea para afrontar el segundo que no pude responder, pero ya escribiré sobre eso otro día. Que a ver si le doy un poco más de vidilla al blog de vez en cuando, jej… ^_^U
Escrito por Gorkin 
