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

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

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

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

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

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

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

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


algorithm math division integer-arithmetic
person goodvibration    schedule 25.07.2020    source источник
comment
Простой ответ — использовать больше битов. Чтобы получить 256 бит, вы уже должны использовать математику повышенной точности, поэтому просто выполните умножение на 512-битную временную переменную.   -  person user3386109    schedule 25.07.2020
comment
@ user3386109: вы, должно быть, уже используете математику повышенной точности - это неправильно. Я использую нативный uint256 языка (и нет более крупного нативного типа, если вам все еще интересно).   -  person goodvibration    schedule 25.07.2020
comment
Конечно, вы можете сделать свою собственную повышенную точность, выполнив длинное умножение и деление. Но, наверное, есть что-то менее утомительное.   -  person Nate Eldredge    schedule 25.07.2020
comment
Для вычисления 512-битного произведения требуется четыре 128-битных умножения, а затем можно выполнить деление по основанию 2^128.   -  person user3386109    schedule 25.07.2020
comment
@ user3386109: это звучит как простой ответ. если у вас есть решение, не могли бы вы опубликовать его?   -  person goodvibration    schedule 25.07.2020
comment
Вот часть умножения. Разделение оставлено в качестве упражнения для читателя. Я просто отмечу, что вы делите 4-значное число на 2-значное число и знаете, что частное будет двузначным числом.   -  person user3386109    schedule 25.07.2020
comment
@ user3386109: нет, вы упомянули что-то о 512-битном числе, которого у меня нет на платформе, над которой я работаю!   -  person goodvibration    schedule 25.07.2020
comment
Связанный ответ показывает, как умножить два 64-битных числа, чтобы найти 128-битный продукт, на платформе, которая не поддерживает 128-битные числа. Это легко адаптируется к вашему варианту использования.   -  person user3386109    schedule 25.07.2020
comment
Отвечает ли это на ваш вопрос? Как умножить 64-битное целое число на дробь в C++, минимизируя ошибку?   -  person phuclv    schedule 26.07.2020
comment
(a * b) / c MulDiv и работа с переполнением из-за промежуточного умножения, Самый точный способ выполнить комбинированную операцию умножения и деления в 64-разрядной версии?, Как точно умножить и разделить 64-битные целые числа?   -  person phuclv    schedule 26.07.2020

Ответы (1)


arrow_upward
0
arrow_downward

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

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 (количество бит)

person Abhay Aravinda    schedule 25.07.2020
comment
Техас. Разве acd не подвержен переполнению так же, как xn? - person goodvibration; 25.07.2020
comment
Кстати, согласно определению в моем вопросе, n/d = 0 и n%d = d. Так что я сомневаюсь, что ваш ответ правильный. - person goodvibration; 25.07.2020
comment
@goodvibration Если n / d = 0, то n = 0 означает, что c и e равны 0. Таким образом, вывод правильный. Если acd переполняется, то математически точное значение (n*x/d) переполняется. Вы не сможете хранить его - person Abhay Aravinda; 25.07.2020
comment
acd не может переполниться, потому что c равно 0. Проблема в том, что be может переполниться. - person Nate Eldredge; 25.07.2020
comment
@NateEldredge b и e меньше d. Значит, произведение меньше d^2. - person Abhay Aravinda; 25.07.2020
comment
Конечно, и d^2 тоже может переполниться. У нас нет информации о максимальном размере d, за исключением того, что он не превышает 256 бит. - person Nate Eldredge; 25.07.2020
comment
(Что касается n/d, я предполагаю, что вы используете целочисленное деление, которое округляется в меньшую сторону. n/d=0 не подразумевает, что n=0, только n < d, и это действительно было одним из предположений.) - person Nate Eldredge; 25.07.2020
comment
@NateEldredge Да, я использовал целочисленное деление. Я исправлю это в ответе. Я хочу сказать, что при переполнении точное значение (xn/d) переполняется. Так что невозможно сохранить ответ - person Abhay Aravinda; 25.07.2020
comment
@NateEldredge: я написал, что моя проблема ограничена целыми числами без знака в верхней части моего вопроса. Поэтому, конечно, я полагаюсь здесь на целочисленное деление. - person goodvibration; 25.07.2020
comment
@AbhayAravinda: точное значение x*n/d не может переполниться, потому что n < d! Единственное переполнение, о котором я беспокоюсь, - это промежуточный результат x*n. - person goodvibration; 25.07.2020
comment
@AbhayAravinda: я думаю, вы ошибаетесь. Давайте попробуем пример с 8 битами вместо 256, чтобы сделать числа меньше. Предположим, d=32, n=19, x=191, поэтому a=5, b=31, c=0, e=19. Результат x*n/d должен быть 113, который не переполняется. Но b*e=589, который переполняется. - person Nate Eldredge; 25.07.2020
comment
Я полностью согласен с тем, что результат b*e/d укладывается в 8 бит. Но как его вычислить без предварительного вычисления b*e, для которого требуется более 8 бит? - person Nate Eldredge; 25.07.2020
comment
Повторение чего-либо b раз не будет очень практичным, так как b может быть таким же большим, как d, что составляет 256 бит. Вы запрашиваете до 2^256 итераций своего цикла, и это не закончится до того, как погаснет солнце. - person Nate Eldredge; 25.07.2020
comment
@NateEldredge Как насчет сейчас. Получил это до O (log d) - person Abhay Aravinda; 25.07.2020