On 7th of January 2016, GIMPS found Mersenne prime number M74207281. GIMPS is a project combining efforts of a large crowd of volunteers contributing computing power and a university server combining the result – maintained by Curtis Cooper. If a number can be found satisfying the conditions of a Mersenne prime number, the number will be checked with primality tests; according to the article it took 31 days to do so.

M74207281 is specified 2^{274 207 281}-1 and a friend of mine at GoGraz wondered how to compute this number in decimal representation. I suggested square and multiply, but wasn’t sure how long it might take.

So I implemented the `exp-by-squaring-iterative`

algorithm on Wikipedia (didn’t thoroughly check whether it is the most efficient algorithm for this kind of problem):

package main import ( "log" "math/big" "os" "strconv" ) var zero *big.Int var one *big.Int var two *big.Int var hundred *big.Int func init() { // initialize global values zero = big.NewInt(0) one = big.NewInt(1) two = big.NewInt(2) hundred = big.NewInt(100) } // ExpBySquaringIterative exponentiates by squaring meaning it computes x^n // in logarithmic time in size of n func ExpBySquaringIterative(x, n *big.Int) *big.Int { switch n.Cmp(zero) { case -1: x.Div(one, x) n.Neg(n) case 0: c := big.NewInt(1) return c } y := big.NewInt(1) for n.Cmp(one) > 0 { x2 := big.NewInt(0) x2.Set(x) nm := big.NewInt(0) if n.Bit(0) == 0 { x.Mul(x2, x2) n.Div(n, two) } else { y.Mul(x2, y) x.Mul(x2, x2) nm.Sub(n, one) n.Div(nm, two) } } return x.Mul(x, y) } func main() { if len(os.Args) == 1 { log.Println("usage: go run num_2n1.go <exponent>") log.Println(" M74207281 is given by exponent 74207281") os.Exit(1) } expstr := os.Args[1] exponent, err := strconv.Atoi(expstr) if err != nil { log.Fatal(err) } log.Println("TBD ExpBySquaringIterative") result := ExpBySquaringIterative(big.NewInt(2), big.NewInt(int64(exponent))) result.Sub(result, one) log.Println("DONE ExpBySquaringIterative") log.Println("TBD computing decimal representation") log.Printf("2^%d - 1 = ", exponent) log.Println(result) log.Println("DONE computing decimal representation") }

And how long does it take to compute this number?

Was there anything interesting about it?

- The decimal representation uses 22.4 MB memory.
- It took 1 hour 27 minutes to compute the decimal representation. But it only takes 4 seconds to actually compute the number in binary. By far most of the hours are spent on computing the decimal string representation.
- The builtin function Exp (you need to set
`m`

to`nil`

) takes 1 hour 17 minutes; so it takes a little bit less time. - For reference, the first digits are 300376418084… and the last digits are …073391086436351 as can be seen on lcns2’s page.