Перемножение двух чисел в дополнительном коде с обнаружением переполнения

Можно было сразу в заголовке написать что нужна длинная арифметика. Из поста это сразу не читается.

алгоритмы перемножения знаковых чисел заданного размера.

Заданного размера – это может быть заданное из 8/16/32/64/128 бит. То что вам надо, называется длинная арифметика.

Длинная арифметика — выполняемые с помощью вычислительной машины арифметические операции (сложение, вычитание, умножение, деление, возведение в степень, элементарные функции) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, с использованием базовых аппаратных средств работы с числами меньших порядков.

Заданного размера – это может быть заданное из 8/16/32/64/128 бит.

Заданного размера означает, что решение должно быть для любого размера, а не частным случаем от размера и машины.

То что вам надо, называется длинная арифметика.

Ценный смысл вашего поста в данной теме состоит в чём?..

В оправдании того, что вы не умеете читать?

Ценный смысл вашего поста в данной теме состоит в чём?.. В оправдании того, что вы не умеете читать?

вандриен, обсуждаемым вопросам 100 лет в обед. были особенно актуальны, когда деревья были большие, а процессоры СОВСЕМ не умели в умножение и деление. тогда математический сопроцессор был отдельной платой, за отдельную плату. и вся пурга что ты сейчас пытаешься понапридумать, была понапридумана задолго до тебя, людьми с хорошим образованием.

ее просто надо почитать, если ты умеешь читать конечно. но ты привык головой ломиться в стену, вместо того, чтобы открыть дверь.

алгоритмы перемножения знаковых чисел заданного размера.

Нет такого термина. Есть термин arbitrary-precision arithmetic, он же длинная арифметика.

С другой стороны, если бы ты это знал, то не стал бы создавать ржачные велосипедные темы.

Перемножить числа может быть гораздо быстрее, чем найти их вещественные логарифмы.

Целую часть двоичного логарифма числа, представленного в двоичной форме, искать не очень долго.

Кстати, а _BitInt(N) из C2X тут ещё не вспоминали?

Добавил _BitInt, на Clang 18.1 он быстрее GMP на 10%, а вот на GCC 14.2 на 50% медленее GMP.

GCC разочаровал, во первых замена вычислений __builtin_add_overflow(«Naive») на __uint128_t(«Naive optimization») просадило производительность на 7%, хотя компилятору была дана свобода. Да и _BitInt он скомпилировал так что медленее даже чем наивная реализация.

Clang прям порадовал, мало того что _BitInt он сгенерировал так что быстрее GMP на 9%, так еще и чуть оптимизированная наивная реализация сранялась по производительности с GMP.

Clang 18.1

GMP checked: 103 ms
GMP: 101 ms
Boost checked: 124 ms
Boost: 127 ms
Wide-integer: 236 ms
BitInt: 92 ms
Naive: 121 ms
Naive optimization: 100 ms

==========================

GCC 14.2

GMP checked: 106 ms
GMP: 102 ms
Boost checked: 126 ms
Boost: 121 ms
Wide-integer: 241 ms
BitInt: 149 ms
Naive: 130 ms
Naive optimization: 139 ms

как хорошо может раскрыться и показать свой истинный уровень автор, создав всего одну тему. после всего гонора и воинственного умничания на форуме. мдэ

Наивное определение переполнения в наивном алгоритме добавляет 50% к времени выполнения функции умножения. Зато нет дополнительных аллокаций памяти как в GMP и нет перерасхода памяти. Если половина чисел с переполнением то производительность сравнивается с GMP, который тратит эти 50% на аллокацию и довычисление числа.

Clang 18.1
Count of numbers with overflow: 0
Count of numbers without overflow: 3000000

GMP checked: 109 ms
GMP: 105 ms
Boost checked: 129 ms
Boost: 121 ms
Wide-integer: 243 ms
BitInt: 95 ms
Naive: 103 ms
Naive checked: 159 ms

--------------------------
Count of numbers with overflow: 1475896
Count of numbers without overflow: 1524104

GMP checked: 153 ms
GMP: 151 ms
Boost checked: 5633 ms
Boost: 157 ms
Wide-integer: 280 ms
BitInt: 93 ms
Naive: 99 ms
Naive checked: 154 ms

==========================
GCC 14.2

Count of numbers with overflow: 0
Count of numbers without overflow: 3000000

GMP checked: 110 ms
GMP: 104 ms
Boost checked: 131 ms
Boost: 125 ms
Wide-integer: 237 ms
BitInt: 150 ms
Naive: 129 ms
Naive checked: 189 ms

--------------------------
Count of numbers with overflow: 1475896
Count of numbers without overflow: 1524104

GMP checked: 152 ms
GMP: 146 ms
Boost checked: 5893 ms
Boost: 164 ms
Wide-integer: 290 ms
BitInt: 189 ms
Naive: 128 ms
Naive checked: 198 ms

получив произведение, которое имеет в 4 раза больше бит, чем исходные операнды.

Если в операндах N и M бит, то в произведении их будет N + M, а не max(N,M)*4

Если ты числа со знаком перемножаешь в лоб, то верными там не будет N*2 бит.

Ну не перемножай в лоб. Отдели знаки, перемножь, верни знак.

а не max(N,M)*4

Про это подробнее расскажу, поясню, что я там имел в виду.

В компах знаковые числа представлены в «дополнительном коде». А дополняются они до соответствующей степени двойки.

То есть: Почему 32-битное число -2 записывается как 0xFFFF_FFFE. Потому что 0x1_0000_0000 - 0xFFFF_FFFE = -2. Вот такая логика формирования чисел.

Из этого математически следует, что если мы умножаем два знаковых числа размера N, то в младших N битах мы получаем правильный результат.

И если переполнения нет, то старшие N нас не парят, на них можно забить. А вот если нас интересует переполнение, то забить не получится.

Почему такое умножение знаковых чисел «в лоб» работает, можно увидеть на примере, если взять десятичный аналог.

Пусть у нас будет дополнение до 1000. Запишем в дополнительном коде число -15. 1000 - 15 = 985. То есть 985 означает «-15».

Теперь умножим 17 на «-15»:

17 * 985 = 16745

Из числа 16745 отбрасываем старшие разряды, получаем 745. Это число в дополнительном коде. Переводим его в привычную форму:

-(1000 - 745) = -255

Это и есть правильный ответ: «17 * -15 = -255», всё сошлось.

Так, до меня, кажись, дошло, как тут можно оптимизировать кое-что. Надо будет утром прикинуть более конкретно.

мало того что _BitInt он сгенерировал так что быстрее GMP на 9%

Рекомендую использовать nanobench для бенчмарков.

если мы умножаем два знаковых числа размера N, то в младших N битах мы получаем правильный результат.

Правильный результат мы получим в N+N (ну хорошо, может быть N+N-1). Если вас интересует перемножение чисел фиксированной разрядности, а не длинная арифметика, то младшие N - результат, старшие - перенос. В общем случае его игнорировать нельзя.

Пусть у нас будет дополнение до 1000. Запишем в дополнительном коде число -15. 1000 - 15 = 985. То есть 985 означает «-15».

Теперь умножим 17 на «-15»:

Вы забыли расширить множители до 1000000:

17 -> 17
-15 -> 999985
17 * (-15) -> 17 * 999985 = 16'999'754

16 отбрасываем, 999 - перенос, 754 - результат

Из числа 16745 отбрасываем старшие разряды

Как потом старшие разряды расширить до «машинного слова» чтобы получить перенос?

Вы забыли расширить множители до 1000000

Зачем? Если мы знаем, что числа заведомо не дают переполнения трёх разрядов при умножении, то результат будет верным без расширения.

А если не знаем, тогда да, нужно больше разрядов.

Зачем? Если мы знаем, что числа заведомо не дают переполнения трёх разрядов при умножении

Отрицательные числа не могут не давать переполнения

ну хорошо, может быть N+N-1

Нет, все же N+N. Допустим, нам надо реализовать длинную арифметику в дополнительном коде, основание которого хранится отдельно для каждого числа.

-45 -> 55₁₀₀ -> 9955₁₀₀₀₀
+45 -> 45₁₀₀ -> 0045₁₀₀₀₀
-45*45 = -2025 -> 7975₁₀₀₀₀
9955*0045 = 44|7975₁₀₀₀₀

2 -> 2₁₀₀₀
-45 -> 955₁₀₀₀
2*955 = 1|910₁₀₀₀ -> -90

То есть при умножении двузначных чисел результат получается четырехзначным.

Другое дело, что для длинной арифметики не нужен перенос.

Так там всё равно в дополнительном коде результат верный получается. Я выше показывал на примере с десятичными.

Это где от балды взято дополнение до 1000 и маленькие множители? Ну повезло, что тут еще сказать. В общем случае это не сработает - придется расширять сомножители до N+M.

Если ты считаешь, что указанное неверно, приведи пример пары чисел, для которых это неверно.

Процессоры именно так аппаратно и вычисляют. Им плевать, со знаком число или нет, побитовый результат умножения идентичный. Смотри например инструкцию mul у risc-v. Она не зависит от наличия знака числа, потому что способ рассчета не зависит от интерпретации.

Если ты считаешь, что указанное неверно, приведи пример пары чисел, для которых это неверно.

Для дополнения до 1000? Я же сказал: поближе к пределу. Например, -485 и 369:

-485 -> 515
369 -> 369
-485 * 369 = -178'965 -> 1000000 - 821'035
515 * 369 = 190'035

Младшее-то «слово» получили, но перенос (821) потерян. А вот если расширять до N+M:

-485 -> 999515
369 -> 369
999515 * 369 = 368|821'035

Получили и младшее «слово» и перенос.

Для дополнения до 1000? Я же сказал: поближе к пределу. Например, -485 и 369

При умножении -485 на 369 результат превышает 3 значащих разряда. Произошло переполнение. Поэтому результат неверный.

Для любой пары чисел, произведение которых укладывается в три разряда, результат будет верный. У меня четко указано это условие в примере, который я рассматривал выше.

При умножении -485 на 369 результат превышает 3 значащих разряда. Произошло переполнение. Поэтому результат неверный.

Результат умножения числа разрядностью M на число разрядностью N укладывается в разрядность M+N. Соответственно, никакого переполнения нет и быть не может. В случае фиксированных M=N=машинное слово, результат также равен N, но добавляется перенос также длиной N, который вы теряете.

Для любой пары чисел, произведение которых укладывается в три разряда

В общем случае это гарантировать невозможно.

Непонятно, с чем вы спорите. У меня написано ровно это. Про частный случай и общий случай. Читайте внимательнее посты, на которые отвечаете.

Вы бы лучше задачу свою сформулировали. А то сначала перемножение чисел известного размера («заданного размера»), потом перемножение чисел, размер которых заранее неизвестен. Потом какое-то переполнение в умножении (это вы так перенос называете что ли?). Какие ограничения на алгоритм тоже неизвестно.

А главное, непонятно где это предполагается применять. Так хоть что-то додумать можно было бы.

размер которых заранее неизвестен

Это откуда такое?

Перемножение чисел в дополнительном коде: https://web.archive.org/web/20120717071922/http://bwrc.eecs.berkeley.edu/Classes/icdesign/ee241_s00/PAPERS/archive/booth51.pdf

Классика жанра

ну хорошо, может быть N+N-1

Нет, все же N+N.

Результат умножения числа разрядностью M на число разрядностью N укладывается в разрядность M+N.

Все ты верно сказал что N+N гарантирует отсутствие переполнения, но иногда можно получить результат длиной N+N-1. Из-за этого если к примеру сумма длин битов будет 513 бит, то результат умножения может быть как 512 бит так и 513 бит. Поэтому нельзя на вот этом пограничном случае однозначно сказать есть переполнение или нет, иначе можно было бы сделать функцию для проверики будет переполнение или нет.

Для демонстрации такой ситуации:

0b11111 - 5 бит.
0b1111 - 4 бита.
0b11111 * 0b1111 = 0b111010001 - 9 бит.

0b10000 - 5 бит.
0b1000 - 4 бита.
0b10000 * 0b1000 = 0b10000000 - 8 бит.

увидеть на примере

Знаешь, чем алгебра от арифметики отличается? Тем что в арифметике конкретные цифры, а в алгебре задачи решаются в общем виде, при помощи переменных. А - Абстрагирование.

В принципе, при реализации длинной арифметики это можно учесть: сначала выделить память M+N цифр, записать туда результат, а потом проверить старшую цифру. Если 0 - записать в поле длины M+N-1, если нет - M+N.