2
\$\begingroup\$

This is a program to find solutions to Goldbach's weak conjecture. I've tried to optimise the solution function by never looking at primes that are larger than the remaining sum, but it feels clunky. Any ideas?

extern crate primal;

use std::env;

fn get_input() -> usize {
    env::args()
        .nth(1)
        .expect("Single positive integer expected as argument")
        .parse::<usize>()
        .expect("Single positive integer expected as argument")
}

fn list_primes_until(input: &usize) -> Vec<usize> {
    let sieve = primal::Sieve::new(input.clone());
    return sieve.primes_from(0).take_while(|x| x <= input).collect();
}

fn get_goldbach_solution(input: &usize) -> Option<[usize; 3]> {
    let first_primes = list_primes_until(&input);

    for first_prime in first_primes {
        if input - first_prime < 1 {
            continue;
        }

        let second_primes = list_primes_until(&(input - first_prime));
        for second_prime in second_primes {
            if input - first_prime - second_prime < 1 {
                continue;
            }

            let third_primes = list_primes_until(&(input - first_prime - second_prime));
            for third_prime in third_primes {
                if &(first_prime + second_prime + third_prime) == input {
                    return Some([first_prime, second_prime, third_prime]);
                }
            }
        }
    }

    return None;
}

fn main() {
    let input = get_input();

    let solution = get_goldbach_solution(&input).expect("No solution found for input");
    println!(
        "{} = {} + {} + {}",
        input,
        solution[0],
        solution[1],
        solution[2]
    );
}
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Pass by value

There is little point passing integrals by reference:

  1. They are Copy, meaning that they can be copied implicitly, so there is no usability penalty to having the caller by pass value,
  2. They are cheap to copy, so there is no performance penalty either. Actually... it may actually perform better.

It's cheaper and easier so pass by value!

This will get rid for the weird &(first_prime + second_prime + third_prime) == input thing.

Expression oriented language

Rust is an expression oriented language. In short, it means that practically everything is an expression.

Notably, a block {} is an expression which evaluates to the value of its last expression (or () if its ends with a statement).

Therefore, the body of a function is an expression, you can simple use None at the end instead of return None;.

Avoid recomputing primes over and over

At the moment, the complexity of your program is horrendous because you keep recomputing the primes over and over. This is unnecessary.

Instead, you can compute the primes up until input once, and then filter those primes.

First Draft

Applying the two above strategies already cleans up the code quite a bit:

fn get_goldbach_solution(input: usize) -> Option<[usize; 3]> {
    let primes = list_primes_until(input);

    for &first_prime in &primes {
        let remainder = input - first_prime;

        for &second_prime in primes.iter().take_while(|p| **p < remainder) {
            let remainder = remainder - second_prime;

            for &third_prime in primes.iter().take_while(|p| **p <= remainder) {
                if third_prime == remainder {
                    return Some([first_prime, second_prime, third_prime]);
                }
            }
        }
    }

    None
}

The last step however is not, in terms of algorithmic complexity, as efficient as it could be. We are iterating over primes until finding one which equals remainder. Since primes is sorted, a simple binary_search would be more algorithmically palatable; although in practice, for small numbers, linear iteration might be faster.

Result

fn get_goldbach_solution(input: usize) -> Option<[usize; 3]> {
    let primes = list_primes_until(input);

    for &first_prime in &primes {
        let remainder = input - first_prime;

        for &second_prime in primes.iter().take_while(|p| **p < remainder) {
            let third_candidate = remainder - second_prime;

            if let Ok(_) = primes.binary_search(&third_candidate) {
                return Some([first_prime, second_prime, third_candidate]);
            }
        }
    }

    None
}

It might be more efficient to start from the highest primes, as it reduces the size of the list to iterate further.

I'm not quite sure about it; you can test it using .rev() on the iterators to reverse them.

\$\endgroup\$
2
  • \$\begingroup\$ I like the direction, but both of your rewritten functions fail to compile for me. \$\endgroup\$ Apr 19, 2018 at 14:25
  • \$\begingroup\$ @SimonBrahan: I am sorry for that; the primal crate is not available on the Rust playground so I could not compile as-is. I've adjusted the samples by mocking it; just sprinkling & and * to appease the compiler :) \$\endgroup\$ Apr 19, 2018 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.