Умножение и деление на целые числа разбиваются на части

Question

Кто-нибудь знает, где я могу получить инструкции о том, как сделать умножение и деление (и, возможно, даже модуль) для целых чисел, которые хранятся в частях?Я делаю библиотеку, которая хранит uint128_t как uint64_t UPPER, LOWER.

Answer 1

Вы знакомы с GMP библиотекой? Почему бы вам не использовать его вместо реализации своего собственного?

• Многофункциональная арифметическая библиотека GNU

По приведенной выше ссылке вы можете скачать файл tar.bz для ОС на базе Unix.

Для Windows, смотрите эту ссылку:

• Инструкция по установке GMP для платформы Windows

Содержит много информации и установочный файл для MinGW, MSVC ++ и CgyWin. Загрузите то, что вам нужно. Вы также можете увидеть эти ссылки:

• Как установить и запустить GMP в Windows, используя MPIR
• Создание библиотеки GMP с помощью Visual Studio? (тема Stackover)

---

После того, как вы закончите установку и настройку, вы хотели бы знать, как программировать с использованием GMP, для этого просмотрите следующие ссылки:

• Основы GMP
• Руководство по GMP

Answer 2

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

x = x1 * 2^k + x2
y = y1 * 2^k + y2

Используя школьное умножение, вам потребуется 4 умножения:

x*y = (x1*y1) * 2^(2*k) + (x1*y2 + x2*y1) * 2^k + x2*y2

Карацубе нужно еще несколько дополнений, но только 3 умножения:

p1 = x1 * y1
p2 = x2 * y2
x*y = p1 * 2^(2*k) + ((x1+x2)*(y1+y2) - p1 - p2) * 2^k + p2      

Конечно, проблема в том, как бороться с переполнением.

Answer 3

Меня интересует та же тема, и я нашел похожий вопрос прямо здесь: Как реализовать большой int в C ++ Я надеюсь, что это укажет вам правильное направление!

Answer 4

Посмотрите на различные библиотеки Big Integer.Вот тот, который Google нашел https://mattmccutchen.net/bigint/

Answer 5

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic может быть хорошим началом. Уже есть много открытых библиотек