Proyecto Euler-Prob.#20(Lua)

sum project

Question

http://projecteuler.net/problem=20 He escrito un código para resolver este problema, sin embargo, parece ser preciso en algunos casos e inexacto en otros. Cuando trato de resolver el problema a 10 (la respuesta se da en cuestión, 27) obtengo 27, la respuesta correcta. Sin embargo, cuando intento resolver la pregunta (100) obtengo 64, la respuesta incorrecta, ya que la respuesta es otra.

Aquí está mi código:

function factorial(num)
    if num>=1 then
        return num*factorial(num-1)
    else
        return 1
    end
end

function getSumDigits(str)
    str=string.format("%18.0f",str):gsub(" ","")
    local sum=0
    for i=1,#str do
        sum=sum+tonumber(str:sub(i,i))
    end
    return sum
end

print(getSumDigits(tostring(factorial(100))))

64

Como Lua convierte números grandes en notación científica, tuve que volver a convertirla en notación estándar. No creo que esto sea un problema, aunque podría ser.

¿Hay alguna explicación para esto?

Answer 1

Lamentablemente, la solución correcta es más difícil. El principal problema aquí es que Lua usa variables de punto flotante de 64 bits , lo que significa que esto aplica.

La larga historia es breve: el número de dígitos significativos en un flotador de 64 bits es demasiado pequeño para almacenar un número como 100 !. Los flotadores de Lua pueden almacenar un máximo de 52 bits de mantisa, por lo que cualquier número superior a 2 ^ 52 inevitablemente sufrirá errores de redondeo, lo que le da un poco más de 15 dígitos decimales. Para almacenar 100 !, necesitarás al menos 158 dígitos decimales. ¡El número calculado por su función factorial () está razonablemente cerca del valor real de 100! (es decir, el error relativo es pequeño), pero necesita el valor exacto para obtener la solución correcta.

Lo que debe hacer es implementar sus propios algoritmos para tratar con números grandes. De hecho, resolví ese problema en Lua almacenando cada número como una tabla, donde cada entrada almacena un dígito de un número decimal. La solución completa requiere un poco más de 50 líneas de código, por lo que no es demasiado difícil y es un buen ejercicio.