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

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

• Библиотека арифметики множественной точности GNU

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

Для Windows перейдите по этой ссылке:

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

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

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

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

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

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

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      

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

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

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