Code review for Rust newbie

[struppi]

Hi!

I am very new to Rust and coming from Python it's my first strongly typed language.
Would be great if I could get some feedback on my code, which computes the digit periodicity of inverse integers (as seen here).

// Compute sorted vector of divisors for given integer n.
fn divisors(n: usize) -> Vec<usize> {
    if n == 0 {return vec![]};
    let mut divs = vec![1, n];
    // check all integers smaller than sqrt(n) + 1
    for i in 2..(1 + (n as f64).sqrt() as usize) {
        if n % i == 0 {
            divs.push(i);
            divs.push(n / i)
        }
    }
    divs.sort();
    divs.dedup(); // remove consecutive duplicates
    divs
}

// find digit periodicity of inverse of n in given base.
// e.g. n=3  -> 1/5  =0.2              -> periodicity=0
//      n=3  -> 1/3  =0.33333333333... -> periodicity=1
//      n=37 -> 1/37 =0.02702702702... -> periodicity=3
fn period(n: usize, base: usize) -> usize {
    if n==0 {return 0}; // otherwise divisors(n-1) won't work
    for div in divisors(n-1).iter() {
        if (usize::pow(base, *div as u32) % n) == 1 {
            return *div;
        }
    }
    0 // no periodicity otherwise
}


fn main() {
    let number = 19;
    let divs = divisors(number);
    let period = period(number, 10);
    println!("Computed divisors of {}: {:?}", number, divs);
    println!("Digit periodicity of 1/{}: {:?}", number, period);
}

Unfortunately, because it has to compute pow(b, div) % n (where b is the base and div the divisor of n-1), it will overflow pretty fast.

1. What types should I use to allow results for up to n=10^5? Is there a less expensive way to compute the modulo of a large power?
2. Why does usize::pow() expect a u32 as the second argument and not usize?
3. Do you notice any abhorrent violations of decent coding style?

I am thankful for any feedback!

Cheers,
struppi

[afetisov]

You obviously didn't run an autoformatter on that snippet. You can use rustfmt (usable as cargo fmt), or your IDE's inbuilt formatter.

You don't need to do for div in divisors(n-1).iter() since a vector is already iterable (i.e. it implements IntoIterator), and you don't need to reuse the vector afterwards. So you can just write for div in divisors(n-1) { ... }, like in Python. Generally iter() is used when you want to chain iterator combinators together, e.g. do something like

v.iter().filter(|x| foo.contains(x)).take(10).collect::<Vec<_>>()

@struppi

Unfortunately, because it has to compute pow(b, div) % n (where b is the base and div the divisor of n-1), it will overflow pretty fast.

Exponentiation is just repeated multiplication, and multiplication of residues modulo n is just another residue modulo n, so you never need to use numbers larger than n * n. You can just directly use the modular exponentiation algorithm. For small powers you can use the naive iterated multiplication by b. For large powers you should use the optimized square-and-multiply algorithm based on the bits of the exponent.

@struppi

Why does usize::pow() expect a u32 as the second argument and not usize?

usize is variably-sized (different size on different architectures), so it's not particularly convenient for arithmetics. Also, would you expect u8::pow to take u8 as an exponent? I would find it quite limiting.

u32 is a nice middle ground which is large enough for many applications and efficient enough in machine code, so I suppose it was just chosen as a reasonable default.

usize is generally used for accessing the memory (indexing into slices and collections, working with pointers etc). If you're doing arithmetics, consider using u32 or u64. In fact, it's pretty much impossible to write efficient portable numeric algorithms using usize, since it's variably sized, and efficient algorithms carefully utilize all available bits of the operands.

Your divisors function also isn't very efficient, since it always iterates up to n.sqrt(). Most numbers have small prime divisors, which means you can find all prime factors much faster if you divide the number by those small divisors. Once you have all prime factors with multiplicities, finding all unique divisors is a simple combinatorial problem which doesn't require brute-force search.

You have period(0, base) = 0. This violates the semantics of the period function: you're trying to find a period of 1 / n, but 1 / 0 is undefined. You should consider returning an error for n == 0. Your options are a panic! (which is not a good option here since n == 0 is a quite legitimate input), or changing the return type of your function to Option<usize> or Result<usize, SomeErr>. In the latter case you can return None or Err(SomeErrVariant).

In general, for garbage inputs you should return Err(Something) rather than silently providing garbage outputs.

Also, the algorithm works only for prime n. Consider adding a function is_prime and a check that n.is_prime() in your functions.