Проект Эйлер -Проб.№ 20 (Луа)

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

64

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

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

Answer 1

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

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

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