Работа с большими числами в Haskell

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

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

(мод (8888^38071670985) 9746347772161)

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


haskell biginteger
person hraesvelgr    schedule 25.03.2012    source источник
comment
stackoverflow.com/ вопросов/1184296/ ..., ваш показатель чрезвычайно велик... однако....   -  person Kristopher Micinski    schedule 26.03.2012
comment
NVM о реализации собственного. Я посмотрел на реализацию этих алгоритмов в Haskell. Они именно так, как я бы их реализовал.   -  person hraesvelgr    schedule 26.03.2012
comment
Как я уже сказал... ваш показатель степени... чрезвычайно велик...   -  person Kristopher Micinski    schedule 26.03.2012
comment
Возможно, попробуйте оценить, сколько памяти вам понадобится для хранения вашего показателя. Это огромное число, которое вы хотите сохранить.   -  person Trismegistos    schedule 26.03.2012

Ответы (2)


arrow_upward
6
arrow_downward

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

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

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

(mod (8888^38071670985) 9746347772161)

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

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

person Daniel Fischer    schedule 25.03.2012
comment
Это сработало блестяще. Я должен был сделать это с самого начала. Я не знаю, почему я этого не сделал. В любом случае, я уже некоторое время смотрю на алгоритм. По какой-то причине я продолжал пытаться делать expt и мод отдельно и не соединял их вместе, чтобы использовать свойства конгруэнтности для уменьшения проблемы. - person hraesvelgr; 26.03.2012

arrow_upward
1
arrow_downward

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

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

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

1.5 * 10^11 / log(2) / 8 / (2^30) = 58GB

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

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

person Irfy    schedule 25.03.2012
comment
Модульное возведение в степень не требует сохранения числа перед взятием по модулю. - person user102008; 26.03.2012