Как очистить x от накипи на n/d, когда x * n переполняется?

Question

Моя проблема ограничена целыми числами без знака длиной 256 бит.

У меня есть ценность x, и мне нужно очистить его от накипи в соотношении n / d, где n < d.

Конечно, простое решение x * n / d, но проблема в том, что x * n может переливаться.

Я ищу любую арифметическую уловку, которая может помочь достичь максимально точного результата.

Разделив каждый из n а также d от gcd(n, d) перед расчетом x * n / d не гарантирует успеха.

Есть ли какой-либо процесс (итеративный или другой), который я могу использовать для решения этой проблемы?

Обратите внимание, что я готов выбрать неточное решение, но мне нужно уметь оценить ошибку.

Answer 1

ПРИМЕЧАНИЕ: Использование целочисленного деления вместо нормального деления. Предположим,

x = ad + b
n = cd + e

Затем найдите a,b,c,e следующим образом:

a = x/d
b = x%d
c = n/d
e = n%d

Затем,

nx/d = acd + ae + bc + be/d

РАСЧЕТ be/d

1. Represent e in binary form
2. Find b/d, 2b/d, 4b/d, 8b/d, ... 256b/d and their remainders
3. Find be/d = b*binary terms + their remainders

Пример:

e = 101 in binary = 4+1
be/d = (b/d + 4b/d) + (b%d + 4b%d)/d

ДИАГНОСТИКИ b/d, 2b/d, ... 256b/d

quotient(2*ib/d) = 2*quotient(ib /d) + (2*remainder(ib /d))/d
remainder(2*ib/d) = (2*remainder(ib/d))%d

Выполняется за O(количество бит)