Как производить математические операции с большими числами?

Question

[Дмитрий Хаперец]

Создал алгоритм для определения числа на простоту.
Написал программу на C++, которая из диапазона 1 ... 2^64 - 1 максимально большое простое число 18446744073709551557 проверяет за 7-8 секунд.
Теперь хотелось бы работать с числами произвольной длины, но не знаю как.
В общем нужно производить три операции с большими числами: вычисление квадратного корня числа (sqrt), округление числа к ближайшему целому (ceil) и деление по модулю (остаток от деления, %).
Подскажите, как можно организовать эти три операции над сверхбольшим числом в C++.

Comments

[Lynn «Кофеман»]

GMP.

Но зачем?

[Дмитрий Хаперец]

Алексей Тен: к примеру, чтобы определять числа на простоту порядка больше чем 2^1000000

[Lynn «Кофеман»]

Это у вас учебная задачка что-ли? Иначе я не вижу никакого смысла писать свой велосипед вместо того, что бы взять что-нибудь стандартное. Тот же openssl, например.

[Дмитрий Хаперец]

Алексей Тен: Да, типа учебная. Работаю над нахождением большого простого числа, нужно найти больше чем 2^57885161 - 1 (в нём 17425170 цифр)

[Lynn «Кофеман»]

Вы хотите обогнать GIMPS в одиночку? Ну удачи :)

[Lynn «Кофеман»]

Хотя, судя по вашему набору операций вы используете «наивный» алгоритм. Для 2^57885161 - 1 он будет выполняться миллиарды лет…

[Дмитрий Хаперец]

Алексей Тен: Для начала нужно сделать так, чтобы можно было работать с большими числами, а далее - алгоритм можно оптимизировать.
Спасибо, но попытаться стоит, как минимум для общего развития ;)

Answer 1

[Максим Кудрявцев]

Фраза для гугла "Длинная арифметика С++"

Answer 2

[Владимир Мартьянов]

Есть готовая и достаточно быстрая реализация в openSSL - BN. Можете ее использовать, можете их сорцы посмотреть (но там черт ногу сломит). Есть еще MIRACL (тоже с сорцами), но у них проблемы с производительностью и документация не очень местами. Можете посмотреть GMP, но лично не использовал.

Answer 3

[Виталий Витренко]

GMP