CODEWITHSUNDEEP
haskellbiginteger
afkbowflexin
afkbowflexin

Reputation: 4089

Dealing with big numbers in Haskell

I'm trying to implement the Miller test in Haskell (Not Miller-Rabin.) I'm dealing with big numbers, and in particular I need to exponentiate big numbers and take the modulus of a large number mod another large number.

Are there any standard functions for doing this? The normal expt function ^ tells me I run out of memory before it computes a result. For example, I'd like to do:

(mod (8888^38071670985) 9746347772161)

I could implement my own algorithms, but it'd be nice if these already exist.

Upvotes: 2

Views: 2817

Answers (2)

Daniel Fischer
Daniel Fischer

Reputation: 183878

There is modular exponentiation (and much more) in the arithmoi package.

Since I wrote it, I'd be interested to hear if you find it useful and what could be improved.

If you try to compute

(mod (8888^38071670985) 9746347772161)

as it stands, the intermediate result 8888^38071670985 would occupy roughly 5*1011 bits, about 60GB. Even if you have so much RAM, that is close to (maybe slightly above) the limits of GMP (the size field in the GMP integers is four bytes).

So you also have to reduce the intermediate results during the calculation. Not only does that let the computation fit into memory without problems, but it's also faster since the involved numbers remain fairly small.

Upvotes: 6

Irfy
Irfy

Reputation: 9587

An approximation to your number before taking modulo is

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

In other words it has around 1.5 * 10^11 digits. It would need around

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

of memory just to represent.

So starting with this may not be the best idea. Does the library have to support calculation with this large numbers?

Upvotes: 1

Related Questions