Как вы можете рассчитать коэффициент, если у вас есть другой фактор и продукт с переполнением?

Question

Как вы можете рассчитать коэффициент, если у вас есть другой фактор и продукт с переполнением?

a * x = b

У меня, казалось бы, довольно сложная проблема умножения / imul: если у меня есть a и у меня b, как я могу вычислить x, если все они — 32-битные слова (например, 0-1 = FFFFFFFF, FFFFFFFF + 1 = 0)?
Например:

0xcb9102df * x = 0x4d243a5d

В этом случае х равен 0x1908c643. Я нашел похожий вопрос, но условия были другими, и я надеюсь, что есть более простое решение, чем предложенные.

6

c++dword x86

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Числа имеют модульное мультипликативное обратное значение по модулю степени два точно, если они нечетны. Все остальное — нечетное число со сдвигом битов (четный ноль, который может быть чем угодно, со всеми сдвинутыми битами). Итак, есть пара случаев:

Дано a * x = b

tzcnt(a) > tzcnt(b) нет решения
tzcnt(a) <= tzcnt(b) разрешимый, с 2^{tzcnt (а)} решения

Второй случай имеет особый случай с 1 решением, для нечетного aа именно x = inverse(a) * b

В более общем смысле, x = inverse(a >> tzcnt(a)) * (b >> tzcnt(a)) это решение, потому что вы пишете a как (a >> tzcnt(a)) * (1 << tzcnt(a)), поэтому мы отменяем левый фактор с его обратным, мы оставляем правый фактор как часть результата (в любом случае его нельзя отменить), а затем умножаем на то, что осталось, чтобы получить его до b, По-прежнему работает только во втором случае, очевидно. Если вы хотите, вы можете перечислить все решения, заполнив все возможности для верхней tzcnt(a) биты.

Остается только получить обратное, вы, вероятно, видели это в другом ответе, каким бы он ни был, но для полноты вы можете вычислить его следующим образом: (не проверено)

; input x
dword y = (x * x) + x - 1;
dword t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
; result y

2