Умножение двух 32-битных чисел без использования 64-битного целого

Question

Мы делаем 32-битное * 32-битное умножение, используя следующий алгоритм

Давайте умножим a (32 бита) на b (32 бита), оба со знаком,

a = ah * 2 ^ 16 + al [ah - старшие 16 бит, al - младшие 16 бит]

b = bh * 2 ^ 16 + bl [bh - старшие 16 бит, bl - младшие 16 бит]

Мы эффективно делаем

Результат = (al * bl) + (((ah * bl) + (al * bh)) * 2 ^ 16) + ((ah * bh) * 2 ^ 32) ~~~

---

Мой вопрос,

Есть ли лучший способ сделать это?

Answer 1

В любом основном компиляторе эмуляция 64-битных целых на 32-битной платформе будет примерно такой же эффективной, как и самостоятельная математическая обработка. Но это будет намного надежнее.

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

Answer 2

Google "Умножение Карацубы".

Ой, а в вашем коде измените константу 2 ^ 15 (она появляется дважды) на 2 ^ 16.

Answer 3

Ответ: нет, нет лучшего способа сделать что-либо, кроме использования сдвига битов и масок вместо 2 ^ n. А именно:

a * 2^n <=> a << n

Во-вторых, ваши ценные бумаги подписаны или не подписаны? Если они подписаны, это меняет дело.

В-третьих, я не уверен, что ваши 2 ^ 15 верны. Если он не подписан, вы хотите сдвинуть биты на 16, а не на 15.

Наконец, вы должны следить за переполнением целых чисел в младшем порядке int. Если вы сложите числа в младшем порядке в int, которые переполняют его емкость, вам нужно правильно увеличить старшее значение int.

Answer 4

Вам необходимо знать (указать), как следует хранить 64-битное значение - предположительно, это пара 32-битных значений, возможно, два элемента массива или два элемента структуры. Вам также необходимо продумать, как информация о знаке будет храниться в результате.

Механически, вы, вероятно, захотите преобразовать оба подписанных значения в беззнаковые, а затем выполнить разбиение и повторную сборку в соответствии с показанными вами линиями, следя за тем, чтобы убедиться, что переносы из 32-разрядного значения младшего разряда правильно управляются в старшем порядке 32-битное значение.

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

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