Project Euler -Prob. # 20 (Lua)

Question

http://projecteuler.net/problem=20 Я написал код, чтобы выяснить эту проблему, однако в некоторых случаях это кажется точным и неточным в других. Когда я пытаюсь решить проблему до 10 (ответ дан в вопросе, 27), я получаю 27, правильный ответ. Однако, когда я пытаюсь решить заданный вопрос (100), я получаю 64, неправильный ответ, так как ответ - это что-то другое.

Вот мой код:

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)))) 

Поскольку Lua преобразует большие числа в научной нотации, я должен был преобразовать его обратно в стандартной нотации. Я не думаю, что это проблема, хотя это может быть.

Есть ли какие-либо объяснения этому?

Answer 1

К сожалению, правильное решение сложнее. Основная проблема здесь в том, что Lua использует переменные 64bit floating point, что означает, что применяется this.

Длинная история рассказана короткой: количество значащих цифр в 64-битном плавании слишком мало, чтобы хранить число, подобное 100 !. Поплавки Lua могут хранить максимум 52 битны мантиссы, поэтому любое число больше 2^52 неизбежно будет страдать от ошибок округления, что дает вам чуть более 15 десятичных цифр. Чтобы сохранить 100 !, вам понадобится как минимум 158 десятичных цифр. Число, рассчитанное вашей функцией factorial(), достаточно близко к реальному значению 100! (т. е. относительная ошибка мала), но для получения правильного решения вам нужно точное значение .

Что вам нужно сделать, это реализовать свои собственные алгоритмы для работы с большими числами. Я действительно решил эту проблему в Lua, сохраняя каждое число в виде таблицы, где каждая запись хранит одну цифру десятичного числа. Полное решение занимает не более 50 строк кода, поэтому это не слишком сложно и приятно.