Double Tramposo
Otros idiomas: English 中文 Português
Este texto es una traducción del artículo original de mi amigo, Maksim Pelevin. Si te sientes cómodo leyendo en ruso, podrías encontrar artículos más interesantes en su blog.
Ya sabes esto:
El tipo de datos double no es muy preciso
Reforcemos este entendimiento resolviendo un problema en CodeWars.
Enunciado del problema
La traducción de la tarea descrita en CodeWars es la siguiente:
Tu tarea es construir un edificio, que será un montón de n cubos. El cubo de la parte inferior tendrá un volumen de n^3, el cubo de arriba tendrá un volumen de (n-1)^3 y así sucesivamente hasta el top que tendrá un volumen de 1^3.
Se te da el volumen total m del edificio. Teniendo el volumen m, ¿puedes encontrar el número n de cubos que tendrás que construir?
El parámetro de la función findNb será un entero m
y tienes que devolver el entero n tal que
n^3 + (n-1)^3 + … + 1^3 = m si tal n existe o -1 si no existe tal n.
Solución ingenua
La solución más sencilla utilizando bucles sería algo así:
public static long findNb(long m) {
long n = 0, totalVolume = 0;
while (totalVolume < m) {
totalVolume += ++n * n * n;
}
return totalVolume == m ? n : -1;
}Solución matemática
De vuelta en la universidad, aprendí sobre series matemáticas y los métodos para calcular sus sumas, así que aquí está mi intento de una solución matemática.
Ya no recuerdo las fórmulas, pero afortunadamente, Wolfram Alpha está aquí para ayudar. Para obtener la fórmula, ejecutemos la siguiente consulta: n^3, n = 1 to k.
Los resultados nos dicen que:
Vamos a sustituir m por el lado izquierdo de la ecuación,
luego aplicamos la propiedad de la raíz cuadrada
y multiplicamos ambos lados de la ecuación por dos.
Después de simplificar, obtenemos:
Escribe el código
Aquí hay una solución para la ecuación anterior, escrita en Java:
public static long findNb(long m) {
double res = Math.sqrt(m);
double d = 1 + 8 * res;
double n = (Math.sqrt(d) - 1) / 2;
return n - Math.floor(n) == 0 ? (long) n : -1;
}Resultados
Resulta que este código devuelve un resultado incorrecto para un subconjunto de datos de prueba.
Esta inconcistencia es visible, por ejemplo, cuando
pasas 1646842954019151682L como entrada.
Al calcular una raíz cuadrada en Java, puedes obtener un resultado que no es totalmente preciso. Veamos:
System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// output 1283293791.000000000000000000000000000000
// correct 1283293791.00000000038962239473657673134031176401122912...Obviamente, la salida y la respuesta correcta son diferentes. ¡Fin!
Conclusión
La solución técnicamente más precisa y potencialmente más rápida no siempre es la mejor opción a elegir. Esto puede no ser una sorpresa para un desarrollador experimentado, pero aquellos que son nuevos en la programación pueden desconcertarse con la causa del error durante bastante tiempo.
Si te preguntas cómo solucionar el problema con la solución matemática,
un enfoque es usar BigDecimal. Este código pasa todas las pruebas:
public static long findNb(long m) {
MathContext mc = new MathContext(64);
BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}… y un pequeño bonus: ¿puedes adivinar cuál de los siguientes es true,
y cuál es false?
(1646842954019151681L == 1646842954019151682D)(1646842954019151681L == (long) 1646842954019151682D)
