Как вывести большие(очень большие) числа?

184
15 января 2019, 15:00

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

long int Karatsuba(int A, int B) { // 2n n
    string Astr = to_string(A);
    string Bstr = to_string(B);
    unsigned long int a, b, c, d, sizeA = Astr.size(), sizeB = Bstr.size();
    if (sizeA == 1 || sizeB == 1) return A * B;
    unsigned long int n = max(sizeA, sizeB);
    a = A / static_cast<long int>(pow(10, n / 2));
    b = A % static_cast<long int>(pow(10, n / 2));
    c = B / static_cast<long int>(pow(10, n / 2));
    d = B % static_cast<long int>(pow(10, n / 2));
    unsigned long int p1 = Karatsuba(a, c);
    unsigned long int p2 = Karatsuba(b, d);
    unsigned long int p3 = Karatsuba(a, d) + Karatsuba(b, c);
    return pow(10, n) * p1 + pow(10, n / 2) * p3 + p2;
}

Пример чисел, которые нужно переменожить: 3141592653589793238462643383279502884197169399375105820974944592 * 2718281828459045235360287471352662497757247093699959574966967627

Answer 1

Классика жанра для работы с длинными числами это GMP. Но есть и другие варианты.

Как-то мне тоже понадобилась длинная арифметика. Но использовать GMP было нельзя, так как длинная арифметика нужна была для микроконтроллеров без операционной системы и кучи. Пришлось написать свою библиотеку С++ шаблонов для работы с длинными целыми числами. Вот ссылка:

https://sourceforge.net/projects/muntl/?source=frontpage&position=5

Там в архиве есть и описание на русском языке.

READ ALSO
Вывод массива в C++ (При сравнении массивов)

Вывод массива в C++ (При сравнении массивов)

Задается 2 массива a и b, нужно вывести массив имеющий наименьшее кол-во положительных элементовПример: Массив a { 1, 2,3}, массив b { -4, -5, 6} программа...

158
C++ Windows API цикл обработки сообщений

C++ Windows API цикл обработки сообщений

Есть Windows API окно обернутое в класСоздается в Windows API main методе например так:

158
Создание таблиц в PostgreSql из сгенерированных POJO классов из схемы AVRO

Создание таблиц в PostgreSql из сгенерированных POJO классов из схемы AVRO

Всем привет! Может кто сталкивался или знает куда копать?

199
MyClass&lt;&gt; myClass = new MyClass&lt;&gt;();

MyClass<> myClass = new MyClass<>();

И такЕсть известный класс ArrayList

148