# Code review for Rust newbie

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

1 Like

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<_>>()
``````

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.

`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.

6 Likes