Why is my Mersenne prime code faster with a larger exponent?

Question

I am writing a program in Rust to check if large numbers are Mersenne primes for fun. For some reason, when I test the program with an exponent of 1_000_000_000 it takes around 5 seconds, but when I use a much smaller exponent of 82,589,933 (to generate the largest Mersenne prime) it never finishes processing. Do any of you know what is happening? Why would a larger exponent increase the performance of my code?

use std::str::FromStr;
use num::{BigInt, One, Zero};

fn is_prime(number: &BigInt) -> bool {
    let mut iteration: BigInt = BigInt::from(2);

    while iteration < *number {
        if number % &iteration == Zero::zero() {
            return false;
        }

        iteration += BigInt::one();
    }

    true
}

fn main() {
    let exponent: u32 = 1_000_000_000; // when changed to 82,589,933 it never finishes
    let number: BigInt = BigInt::from_str("2").unwrap().pow(exponent) - BigInt::one();
    let is_prime: bool = is_prime(&number);
    println!("2^{exponent} - 1 is prime: {}", is_prime);
}

@mkrieger1 Looking back at it, if I try any power of 10 less than 1_000_000_000 it is almost instant. I think jthulhu hit the nail on the head with his answer! — figgyfarts
– figgyfarts, Commented Mar 20, 2024 at 9:56

jthulhu · Accepted Answer · 2024-03-19 20:55:00Z

6

The answer is very simple: with the bigger exponent, your code quickly finds a divisor, so it ends quickly (indeed, 2^1_000_000_000-1 = (2^2-1)(2^499_999_999+...+1) = 3n where n is a big number, so it spends five seconds doing two iterations). With the smaller, well-chosen exponent, it actually tries every smaller number to check if it's a divisor, which is not going to end, since 2^82,589,933 iterations is much bigger than any conceivable time span.

edited Mar 19, 2024 at 20:55

answered Mar 19, 2024 at 20:35

jthulhu

8,8842 gold badges24 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why is my Mersenne prime code faster with a larger exponent?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related