Такой интересный вопрос у меня.
Необходимо выполнить умножение 2-х длинных целых знаковых чисел длиной N слов, которые хранятся в дополнительном коде little-endian. Т.е. 2 — это 0002 0000 (hex, при условии, что слово = 16 бит, побайтно: 02 00 00 00), а -2 — FFFE FFFF (побайтно: FE FF FF FF).
Для примера возьмём простой алгоритм умножения (без Карацубы), где для C = A * B каждое слово числа A умножается на каждое слово числа B и записывается в C со сдвигом и суммированием (с переносом при переполнении).
У нас есть операции умножения знаковых чисел и беззнаковых, причём результат произведения может быть в 2 раза больше, чем множители. По моим наблюдениям, удобнее использовать беззнаковое умножение (каждой пары слов), например:
FFFE FFFF
x
0002 0000
=
FFFC 0001
+
0000 FFFE 0002
=
FFFC FFFF 0002
2-ку убираем, получаем
FFFC FFFF = -4, всё ок.
Именно поэтому 2-3-операндный imul в асме (где старшая часть произведения отбрасывается) используется как для знаковых чисел, так и для беззнаковых.
При знаковом умножении получается так:
FFFE FFFF
x
0002 0000
=
FFFC FFFF
+
0000 FFFC FFFF
=
FFFC FFFB 0000 0001
Какая-то ерунда. По крайней мере, это требует преобразования но не очень понятному мне алгоритму.
А теперь самое главное :)
Необходимо определить — было бы переполнения при умножении.
Понятное дело, что если мы вылезли за диапазон N слов, то переполнение было.
А если нет?
Я пока вижу только такой алгоритм: умножать абсолютные значения множителей (C = abs(A)*abs(B)), поменять знак произведения, если знаки A и B отличаются и сравнить знак результата с тем, что должно получиться (т.е. если знаки A и B разные, значит должно получиться отрицательное число).
Это работает, но это, опять же, лишние операции по проверке и изменению знаков, к тому же, нужно ещё проверять множители на 0, т.к. при нуле результат не будет отрицательным, что может выдать ложный сигнал переполнения.
Вопрос: можно ли (и самое главное, как — по какому алгоритму) определить переполнение после умножения без приведения исходных множителей к абсолютным величинам?
Если нужно, алгоритм умножения можно чуть-чуть модифицировать (добавив что-то или заменив какие-то операции).
Цель — упрощение кода.
