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

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

А что, нельзя просто переможить и посмотреть не стал ли результат меньше одного из двух операндов?

gmplib

А что, нельзя просто переможить и посмотреть не стал ли результат меньше одного из двух операндов?

Например, возьмём 4-битные без знака:

5 * 6 = 30 // Перемножаем, получили число за пределами разрядной сетки
30 % 16 = 14 // Возвращаем в разрядную сетку

14 больше и 5, и 6.

Но это для беззнаковых. Для беззнаковых такой критерий не работает. А для знаковых я хз.

знаковых чисел заданного размера

Целых или с плавающей точкой? Это в данном случае важно, и оптимальная реализация будет разной.

Целых. В дополнительном коде.

Тогда не пойму, почему просто MUL не использовать и не смотреть флаг OF на предмет переполнения. Оно же на уровне процессора уже есть. По крайней мере для x86(-64). Зачем тут ещё что-то кодить?

upd: а, кажется понял, надо для чисел больше 64 бит…

расширяем операнды до максимального общего (32 до 64 если 32x64), перемножаем..если флаг переполнения, что бывает но редко, возвращаемся и повторяем с 128 бит. Покуда ЦП/АЛУ/ГПУ поддерживает разрядность. Иначе более зубодробительно и mp. То есть работа от исключений и ошибок.

можно конечно заранее предрассчитывать что X*Y гарантированно вызовет переполнение и стоит расширять разрядность, но это @па всему..

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

а на вашей стадии надо вообще забить :-) вы ещё не определились выбором пола даже с семантикой и синтаксисом. Потом когда всё прочее вдруг устроиться уже решите проблемы перемножения больших чисел

Тогда не пойму, почему просто MUL не использовать и не смотреть флаг OF

Алгоритм беззнакового умножения для операндов длиной n бит требует 3 операции умножения чисел длиной n/2 бит. Ну и там еще сложений и проверок по мелочи.

Таким образом мы можем рекурсивно задать алгоритм умножения для чисел любого размера.

А вот для знаковых - я выше описал: сначала нужно увеличить операнды в 2 раза по битности, уже затем умножать, получая соответствующие накладные расходы про производительности.

Расширить операнды знаком в 2 раза.

Зачем?

Тупой алгоритм.

сводим все к умножению положительных/беззнаковых чисел:

1. берем абсолютные значения
2. умножаем абсолютные значения
3. если разные знаки операндов, возвращем отрицательное

https://github.com/X547/wayland-server/blob/master/XkbKeymap.cpp

u=u*u: x && z / x != y

s=s*s: y < 0 && x == min || y && (s)z / (s)y != x

Алгоритм, который мне известен:

Наверное я там херню несу.

Пойдём сначала.

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

 x
 x
--
xx

А нам нужно научиться умножать вот такие числа:

  xx
  xx
----
xxxx

Для этого мы с «половинками» чисел производим операции умножения, получив 4 числа, а затем складываем их:

00xx  <- множитель b.l * a.l
0xx0  <- множитель a.h * b.l
0xx0  <- множитель b.h * a.l
xx00  <- множитель a.h * b.h

Получаем произведение нужного размера.

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

Так?

Если идёт компиляция под конкретную архитектуру, то я бы использовал ассемблерную вставку и после операции перемножения прочитал бы флаги процессора. Там есть бит, который указывает, было переполнение или нет.

1. Убираем знак
2. Складываем биты, получаем разрядность результата
3. Выделяем место под результат, умножаем (любимым алгоритмом, хоть в столбик, хоть карацубой)
4. Возвращаем знак, если одно из исходных чисел отрицательное

4. Возвращаем знак, если одно из исходных чисел отрицательное

если оба отрицательные, тоже?

Арифметику совсем не помним?

Ничего не знаю про ассемблер, но помню про умножение методом русского крестьянина. Там нужно только один операнд удваивать. За ним и приглядывать проще и удвоение должно быть очень родной операцией, может в ассемблере какая помогайка для неё есть.

Там помимо этого удвоения ещё куча операций сложения. Слишком много получается. Да и всё равно три числа в памяти держать (левый столбец, правый столбец, результат). То есть по памяти, конечно, немножко выигрываем (в 1.5 раза больше надо, а не в 2), но по количеству необходимых операций очень сильно проигрываем.

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

Это много? Флаг для хранения знака + копии аргументов

int mul(int a, int b)
{
  int acc = 0;
  int s = (a^b)&(1<<31);
  if(a&(1<<31)) a=(a^-1)+1;
  if(b&(1<<31)) b=(b^-1)+1;
  while(b) {
    if(b&1 == 1) acc += a;
    a<<=1;
    b>>=1;
  }
  return s? (acc ^ (-1))+1 : acc;
}

посмотри как это сделано

https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

Если я правильно понял, wandrien хочет играться с числами произвольной величины (потому что для байтов/слов/двойных слов есть обычный флаг переполнения). Тогда имеет смысл вот так вот заморачиваться. А если нет, то согласен с вами, слишком много действий для столь базовой операции как умножения.

хочет играться с числами произвольной величины

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

Не та ссылка: https://github.com/jart/jtckdint?tab=readme-ov-file#correctness

Использовать деление для проверки переполнения в умножении…

Я не смог придумать забавного комментария к этому.

hakmem?

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

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

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

Складываешь первое число само с собой столько раз, чему равно второе число. Компилятор/синтезатор сам развернёт цикл и сделает одновременное многоразовое сложение. Времена карт Карно остались в прошлом.

Читал https://en.wikipedia.org/wiki/Multiplication_algorithm?

очевидно надо юзать готовые заточены для этого инструкции проца, они в нем есть:-)

Один предлагает юзать несуществующие инструкции проца для перемножения чисел произвольной разрядности.

Другой предлагает разворачивать умножение в цикл суммирования.

Цирк на выезде.

Вот просто для сравнения, чтобы была понятна разница в уровне дискуссии:

https://board.flatassembler.net/topic.php?t=20099

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

Ух какое оптимальное решение: складывать единицу минус саму с собой два миллиарда раз.

anonymous

if(a&(1<<31)) a=(a^-1)+1;

А что, if(a<0)a=-a или a=abs(a); не проще?

Кстати, первый аргумент можно и не проверять. Сложению знак безразличен:

int64_t mul(int32_t a, int32_t b){
  int32_t sign = b;
  if(b<0)b=-b;
  int64_t res = 0, arg1 = a;
  while(b){
    if(b & 1)res += arg1;
    arg1 <<= 1;
    b >>= 1;
  }
  if(sign>=0)return res; else return -res;
}

Умножать в унарной системе счисления ещё не предлагали?

А что, if(a<0)a=-a или a=abs(a); не проще?

Проще, но «гулять так гулять» И потом — это каркас, в который вместо интов легко подставляется кастомный тип, например, какой-нибудь num_t с массивом внутри. А +=, <<= и >>= становятся add(res,a), shift_left(a), shift_right(b). А вместо ^(1<<31)+1 - neg(res), работающий по тому же принципу. И вместо интов 2^32, внезапно, складываем инты размером хоть в 2^1024, хоть 2^65536

складываем

умножаем, конечно

Другой предлагает разворачивать умножение в цикл суммирования.

Ты действительно считаешь себя умнее компилятора/синтезатора, над которым трудились лучшие умы планеты? В таком случае, не забудь поделиться результатами. Удачи!

hobbit, сними с меня скор, я боюсь так же отпупеть как местные по мере роста звёзд)))

Я-то к тому, что компилятор может не догадаться, что (~x)-1 это всего лишь смена знака. А abs() можно реализовать и более оптимально, чем проверка плюс смена знака. Пару лет назад я нечто подобное для risc-v изобретал. Можно через if(x<0)x=0-x; - две инструкции, но используется переход, то есть ломается конвейер. А можно в 4 битовые инструкции, но последовательные. Сейчас лень вспоминать какие.

это каркас, в который вместо интов легко подставляется кастомный тип

Или, скажем, реализовывать на ПЛИС. Аппаратное умножение сейчас даже на дешевых контроллерах есть.

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

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

ну и п.здуй в поисковые системы.

компилятор может не догадаться

Я по памяти набросал, почти наверняка не оптимально. Скомпилировал, проверил — работает/умножает, ну и ладно. Конечно, в готовой реализации нужно внимательно смотреть, что компилятор сгенерит и как оно на процессор ляжет.

Или, скажем, реализовывать на ПЛИС. Аппаратное умножение сейчас даже на дешевых контроллерах есть.

А ещё есть BCD, тоже интересный вариант (для «кастомных» вещественных, например). Как с помощью «битовой магии» реализовать сложение и умножение — рецепты есть. Наверное можно и на ПЛИС.

несуществующие инструкции проца для перемножения чисел произвольной разрядности.

Я не увидел в исходном посте слов о произвольной разрядности. И я не увидел ответа на свой вопрос - по какому критерию искомый алгоритм должен быть оптимальным? Скорость? Расход памяти? Еще что то? На каком железе?

Как бы очевидно что если речь о скорости и разрядность чисел лезет в разрядность стандартных интов, то надо юзать стандартные инты, и это не только про умножение а вообще про все операции.

Если разрядность не лезет то проще взять готовую либу для длинных целых, такие тоже в природе есть.

Зря Вы так, Enthusiast в общем прав. У нас в HPC (где выжимают из железа каждый такт и экономят каждый бит) 20 лет назад еще писали ассемблерные вставки. Сейчас никто этим не занимается, компилятор как правило делает asm лучше человека. Иногда втыкают pragma unroll, но редко.

Я не увидел в исходном посте слов о произвольной разрядности.

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

по какому критерию искомый алгоритм должен быть оптимальным? Скорость?

Скорость.

Если разрядность не лезет то проще взять готовую либу для длинных целых, такие тоже в природе есть.

Я не спрашивал, «чем мне проще умножить числа». Я спрашивал об алгоритме. Вы не понимаете разницу между тортом из магазина и технологией выпечки тортов?

https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

Может быть в тему

abs(x) реализуется как (x xor y) - y, где y - это расширенный на все биты знак числа.

То есть можно без перехода сделать.

Правда в случае генерализации алгоритма на числа произвольного размера, всё равно там будет цикл.

Сейчас никто этим не занимается, компилятор как правило делает asm лучше человека.

Так ТС же вроде компилятор и пишет(если я его ни с кем не путаю). Поэтому ему и смешно, когда предлагают уповать на оптимизации компилятора.

abs(x) реализуется как (x xor y) - y, где y - это расширенный на все биты знак числа.

То есть можно без перехода сделать.

Вот только это минимум 4 операции и минимум один лишний регистр задействуется. А с переходом - 2 операции (считая сам переход). Интуитивно мне кажется, что на arm с их операциями условного выполнения вариант с if будет лучше.

Правда в случае генерализации алгоритма на числа произвольного размера

Смотря какие операции доступны для машинных слов. «Умножение в столбик» оправдано если нет аппаратного умножения. А если оно есть, пусть даже только для байтов, уже можно другие алгоритмы придумывать. Самое простое - посмотреть как реализовано умножение чисел, не влезающих в одно машинное слово, в существующих компиляторах. Скорее всего, так же, «в столбик», но «цифры» будут не однобитные, а однословные.

Я спрашивал об алгоритме

внятнее надо формулировать, лол )

https://chromium.googlesource.com/v8/v8/+/refs/heads/main/src/bigint/