Работа с большими номерами в Haskell

Question

Я пытаюсь реализовать тест Миллера в Haskell (Not Miller-Rabin.) Я имею дело с большими числами, и, в частности, мне нужно показать большие числа и взять модуль много мода другой много.

Существуют ли какие-либо стандартные функции для этого? Нормальная функция expt^говорит мне, что у меня заканчивается память, прежде чем она вычисляет результат. Например, я хотел бы сделать:

(мод (8888^38071670985) 9746347772161)

Я мог бы реализовать свои собственные алгоритмы, но было бы хорошо, если они уже существуют.

Answer 1

В модуле arithmoi имеется модульное возведение в степень (и многое другое).

Поскольку я написал это, мне было бы интересно услышать, если вы найдете его полезным и что можно улучшить.

Если попытаться вычислить

(mod (8888^38071670985) 9746347772161) 

, как он стоит, промежуточный результат 8888^38071670985 будет занимать примерно 5 * 10 битов, около 60GB. Даже если у вас столько RAM, это близко (возможно, чуть выше) пределы GMP (поле размера в целых числах GMP равно четырем байтам).

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

Answer 2

Приближение к вашему номеру, прежде чем принимать по модулю является

10^log(8888^38071670985) 
= 10^(38071670985 * log(8888)) 
= 10^(1.5 * 10^11) 

Другими словами, она имеет около 1,5 * 10^11 цифр. Это потребует около

памяти только для представления.

Так что, начиная с этого, возможно, не самая лучшая идея. Имеет ли библиотека для поддержки расчета с помощью этих больших чисел?