I heard about rust as a cool language and trying to learn it now.
I write now nodejs and want a trick behind my sleeves when nodejs becomes to slow.
As i try to learn rust, i thought that i will try to solve project euler questions with rust.
I took the following problem #23 Non-abundant sums - Project Euler
I have two files:
main.rs
mod euler;
use euler::primes::sum_proper_divisors;
use std::collections::HashSet;
fn ex23() {
let mut res:u64 = 1;
let mut abundant: HashSet<u16> = HashSet::new();
for i in 2..28124{
{
let ab = &abundant;
let is_sum_of = ab.into_iter().filter(|&x| ab.contains(&(i -x))).next();
if is_sum_of == None {
res = res + (i as u64);
}
}
let sum_divisors = sum_proper_divisors(i as u32);
if sum_divisors > (i as u32) {
abundant.insert(i);
}
}
and euler/primes.rs
#[derive(Debug)]
struct PrimeDiv {
prime : u32,
count : u8
}
fn prime_factors(mut n:u32) -> Vec<PrimeDiv> {
let mut res: Vec<PrimeDiv> = vec![];
let root = (n as f64).sqrt().floor() as u32;
let mut i = 2;
while n>1 && i<=root{
if n%i ==0 {
let mut curr_prime = PrimeDiv{prime:i, count: 1};
n = n/i;
while n%i ==0 {
curr_prime.count = curr_prime.count +1;
n = n/i;
}
res.push(curr_prime);
}
i = i+1;
}
if n>1 && res.len()>0 {
res.push(PrimeDiv{prime:n, count: 1});
}
return res;
}
pub fn sum_proper_divisors(n:u32) -> u32 {
let mut sum = 1;
let prime_facts = prime_factors(n);
let mut helper_arr = vec![0; prime_facts.len()];
if prime_facts.len() ==0 {
return 0;
}
let last_index = prime_facts.len() - 1;
let mut divisor = 1;
loop {
let mut index =0;
while helper_arr[index] == prime_facts[index].count && index <last_index {
divisor = divisor / prime_facts[index].prime.pow(prime_facts[index].count as u32);
helper_arr[index] = 0;
index = index +1;
}
helper_arr[index] = helper_arr[index]+1;
divisor = divisor * prime_facts[index].prime;
if divisor ==n {
break;
}
//println!("divisor:{} index:{} helper: {} p:{}", divisor, index, helper_arr[index],prime_facts[index].count);
sum = sum + divisor;
}
return sum;
}
The program and the algorithms and very simple.
I was very impressed by the memory consumption.
It did not take more than 1.5 MB to run.
There were two topics which i am not sure i am doing the right way:
The conversion stuff. For example here: let root = (n as f64).sqrt().floor() as u32; This is so ugly. I did not find a better way to do so because the functions are missing. But why isn't there a sqrt function on integers and why float does not return an integer. Is there a better way to do so?
The running time was 4s. I can try to make the algorithm better and trade space for time, but for a system language 4s is an eternity. Do you see here any grave error?
I don't know of any language that has an integral sqrt in the standard library, so it would be somewhat strange for Rust to have it. For floor, floats have a much larger range than can be represented in an integer, e.g. the float 1e300_f64 is an integer (so its floor is itself) that cannot be represented in any of the primitive integer types: it is nearly 1000 bits long when written out in full.
You should compile with optimisations, either -O to rustc, or --release to cargo. The runtime goes from 3s to 0.13s on my computer.
(BTW, I edited your post to use backtick delimiters for the code, rather than a > block-quote, which makes it much easier to read.)
Yes, I personally have had uses for isqrt too, but as I just said, it would be a fairly niche feature to include in a standard library, such that it would be essentially unique to Rust and yet doesn't really relate to Rust's main goal (if Rust was focusing on just being the best language for writing prime sieves, then maybe, but it's trying to be more general than that). It also isn't at all hard to just write (x as f64).sqrt() as u32, or to even to stick it write an external crate and use that. An external crate could manage choosing the fastest implementation (which is likely to usually be (x as f64).sqrt(), anyway) in a more precise manner than std can do easily, anyway.
(It is not the role of Rust's standard library to include every feature/function that people have had some use for: there was early investment in cargo and crates.io for exactly this reason, to make it super easy to reuse external code.)
Except that's technically not safe, since casting NaN to an integer type can cause LLVM to lose its marbles.
To do it properly, you really need to do checked conversions, which means writing it yourself or using an external crate,use conv which is not quite as straightforward as you say.
If we're going to be technical, it is safe at a language level, although you are correct that there is a bug in one Rust compiler (currently the only one, of course) that means it isn't handled right there. That said, almost all use cases for isqrt I can think of have guaranteed-positive numbers anyway (i.e. the cast is from an unsigned integer), so it's probably not a major concern.
Rust does add some stuff to your code without --release, enabling you to debug much better, to say it in a simple way.
The compiler also tries not to re-invent code > compile again which you haven't changed.
This makes changing & compiling -> running much faster.
For production you simply add --release and it'll remove all this stuff, but will also take longer, even more through the mentioned optimisations.
