Различные результаты для пола (a, b) и a // b

Question

--this function isn't relevant, but I included it for completeness
function gcd(a, b)
    local temp
    while b > 0 do
        temp = a % b
        a = b
        b = temp
    end
    return a
end

function extendedgcd(a, b)
    if b == 0 then
        return 1, 0, a
    end
    local x, y, d = extendedgcd(b, a % b)
    --this assertion fails for a = 568784642688024576, b = 5
    --left side gives 113756928537604915 (correct), while right side gives 113756928537604912 (wrong)
    assert(a // b == math.floor(a / b))
    --so here, I can't use math.floor
    return y, x - a // b * y, d
end

function modularinverse(e, mod)
    if gcd(e, mod) > 1 then
        return nil
    end
    local x, _, _ = extendedgcd(e, mod)
    if x < 0 then
        x = x % mod
    end
    if x * e % mod ~= 1 then
        error(string.format("Modular inverse (%d) doesn't produce 1 (e = %d, mod = %d)", x, e, mod))
    end
    return x
end

modularinverse(5, 568784642688024576)

За a = 5 а также b = 568784642688024576Утверждение в extendedgcd выходит из строя. Я не эксперт в точности FP, но есть разница в 3 между двумя, поэтому я не думаю, что здесь есть ошибка округления / точности. Но я могу ошибаться.

Обычно я бы просто использовал // вместо этого, но я не могу, потому что целевая платформа не работает на Lua 5.3, то есть когда оператор был добавлен.

Что мне не хватает? Как мне заставить это работать с floorили есть другой способ?

Также обратите внимание: та же проблема произошла, когда я переписал ее в Python для скрипки (с math.floor а также //).

Answer 1

Более точный ответ:

Как бумага и карандаш покажет: 568784642688024576 / 5 = 113756928537604915.02

Наиболее точное двоичное представление этого отношения в виде числа с двойной точностью:

0100001101111001010000100101010100101110010000111001001100110011

Который в десятичном виде: 1.13756928537604912E17 (обратите внимание на окончание...912)

Теперь, если вы уменьшите двоичное представление на единицу, вот так:

0100001101111001010000100101010100101110010000111001001100110010

Тогда это равно: 1.13756928537604896E17 (... 896 в конце!)

Если вам нужно увеличить исходное двоичное число на единицу, например, так:

0100001101111001010000100101010100101110010000111001001100110100

Тогда это равно: 1.13756928537604928E17 (... 928 в конце!)

Итак, существуют точные двоичные представления двойной точности для этих чисел:

113756928537604896

113756928537604912 (ближе всего к фактическому коэффициенту)

113756928537604928

Выше можно проверить с помощью онлайн-конвертеров, например, здесь.

Итак, урок:

Целочисленное деление даст правильный ответ (т. Е. Целую часть частного). Полы с плавающей запятой делятся на двоичное представление чисел, что не всегда точно.

Вне рамок этого ответа, но требуется чтение, чтобы действительно понять что-либо из этого:

Как вышеуказанные двоичные числа представляют их десятичные эквиваленты?

• Краткий ответ: IEEE-754. Я желаю вам удачи и много кофе, если вы планируете изучать этот документ по стандартам.

Какова алгоритмическая разница между / а также // ?

• Другими словами, почему // получить ответ, который мы хотим выше?

Answer 2

Числа Луа имеют двойную точность, верно? Как только вы превысите 2^52, в целочисленном представлении будут все большие пропуски.

568784642688024576 больше 2^58, поэтому вы можете столкнуться с некоторыми из этих пробелов. Если это так, то, похоже, // правильно учитывает пробелы, тогда как, возможно, слово не делает.

Если важно, чтобы ваш код обрабатывал целочисленные значения, приближающиеся к 2^64, то, возможно, стоит поискать плагин или что-то, что позволяет работать с 64-битными целыми числами. Или, если вам нужно иметь дело с еще большими числами, может быть библиотека или что-то для работы с очень большими числами.