Умножение больших больших чисел, найденных в строке, без использования внешних библиотек, Stack Overflow
Итак, я читал несколько тем о том, как GNU и другие библиотеки нужны для умножения больших больших чисел, но я работаю над тем, что не позволяет использовать большие внешние библиотеки. Поэтому я пошел с подходом ввода больших чисел в виде строк, и я смог выполнить с этими числами то, что хотел, но теперь я подошел к сложной части: умножение двух целых чисел до 50 цифр в каждой. Есть ли какой-нибудь код, который я могу найти около 200 или меньше строк, которые я могу реализовать в своем коде и может ли я сделать это? Или есть простой способ реализовать это умножение, разделив эти числа? Некоторые мысли или помощь будут с благодарностью.
Решение
Способ, которым я делал это в прошлом, состоит в том, чтобы создать массив целых чисел для чисел произвольного размера. Для 50 десятичных цифр требуется около 167 бит или чуть более 20 байтов. Округлите до 24, чтобы оно хорошо вписывалось в массив из 32-разрядных целых чисел. Затем преобразуйте свои десятичные строки в 24-битные целые числа a и b. Оттуда вы можете эффективно делать умножение так же, как вас учили делать это вручную. Предполагая, что у вас уже есть функция, которая добавляет эти числа, вы можете умножить их следующим образом:
int32_t a[6];
int32_t b[6];
// multiplication results require twice as much space as the operands
int32_t result[12];
memset(&result, 0, sizeof(12));
int32_t temp_result[6][7];
for (int i = 0; i < 6; i++)
{
for (int j = 0; j < 6; j++)
{
int64_t product = a[i] * b[j];
temp_result[i][j] = product & (0xffffffff);
temp_result[i][j + 1] = product & (0xffffffff00000000);
}
}
for (int i = 0; i < 6; i++)
{
// source a, source b, result
add(temp_result[i], result[i], result[i]);
}
Если у вас еще нет функции добавления, процесс очень похож.
Другие решения
mini-gmp (небольшой одиночный файл .c и .h, часть полного пакета gmp).
загрузочный multiprecision (не такой маленький, но только заголовок).