Hacker News Reader

In the spirit of "every programmer loves to fizzbuzz", I rewrote this in Rust. Aside from rewriting it in a different language, the biggest change I made was only doing trial division against known primes <= the square root of a number we are checking for primality. Able to get the first 1,000,000 primes in 20 seconds:

    use std::collections::HashMap;

    pub fn first_n_primes(n: u64) -> Vec<u64> {
        let mut primes = Vec::new();
        let mut candidate = 3;
        let mut count = 0;
        if n >= 1 {
            primes.push(2);
            count += 1;
        }
        while count <= n {
            let candidate_sqrt = ((candidate as f64).sqrt().ceil() + 1.0) as u64;
            let mut is_prime: bool = true;
            for prime in &primes {
                if candidate % prime == 0 {
                    is_prime = false;
                    break;
                }
                if prime > &candidate_sqrt {
                    break;
                }
            }
            if is_prime {
                primes.push(candidate);
                count += 1;
            }
            candidate += 2;
        }
        primes
    }

    fn main() {
        let mut last_digit_pair_counts: HashMap<String, u64> = HashMap::new();
        let primes = first_n_primes(1000000);

        for i in 0..(primes.len() - 1) {
            let last_digit0 = primes[i] % 10;
            let last_digit1 = primes[i+1] % 10;
            let digit_str = format!("{}-{}", last_digit0, last_digit1).to_string();
            let counter = last_digit_pair_counts.entry(digit_str).or_insert(0);
            *counter += 1;
        }
        last_digit_pair_counts.remove("2-3");
        last_digit_pair_counts.remove("3-5");
        last_digit_pair_counts.remove("5-7");
        let mut ordered_keys: Vec<String> = last_digit_pair_counts.keys().cloned().collect();
        ordered_keys.sort();
        for key in &ordered_keys {
            println!("{}: {}", key, last_digit_pair_counts[key]);
        }
    }

which outputs:

Small speed note: Rust 1.7 just made custom hashing functions available. Rust uses a cryptographically secure hashing function by default, but for work like this, that's inappropriate. To use FNV instead:

1. add fnv to your Cargo.toml's dependencies section 2. The first few lines become:

  extern crate fnv;

  use std::collections::HashMap;
  use std::hash::BuildHasherDefault;
  use fnv::FnvHasher;
    
  type MyHasher = BuildHasherDefault<FnvHasher>;

2. and the hash creation line becomes

  let mut last_digit_pair_counts: HashMap<String, u64, MyHasher> = HashMap::default();

This is 17% faster on my two runs of your code. :)

Other notes:

  format!("{}-{}", last_digit0, last_digit1).to_string();

The .to_string() is redundant here, format! already gives you a String. That should remove a bunch of allocations.

Thanks for taking time to give pointers to a noob Rustacean - this made my day.

Any time :)

Oh, one other thing: I noticed you said 20 seconds. Mine took about 4 seconds, and I was wondering where the difference was... did you compile with optimizations? Without, it takes 22s on my machine... `--release` as an argument to Cargo, or `-C opt-level=3` as an argument to rustc.

It's good to see this over a different language. I like how when working on larger data the 3-9 transition looses a big part of its "advantage" over the 3-7 transition. 9 is still the prefered/most probable "end-digit follower" for primes ending in 3, but it jumped form being alost 20% more probable (10k) to about 12% (1m).

Oh this is fun. I tried it in Lua:

    primes = {}
    function inPrimes(n)
    	for _, v in ipairs(primes) do
    		if n%v == 0 then return false end
    		if v > math.ceil(math.sqrt(n)) then break end
    	end
    	return true
    end
    for i = 3, 1.6e7, 2 do
    	if inPrimes(i) then table.insert(primes, i) end
    end
    last = '7'
    totalDigits = {}
    for i = 4, #primes do
    	c = last..tostring(primes[i]):sub(-1)
    	totalDigits[c] = totalDigits[c] and totalDigits[c] + 1 or 1
    	last = c:sub(-1)
    end
    for k, v in pairs(totalDigits) do print(k, v) end

Gets just as many primes and runs in 7 seconds in LuaJIT.

Computed up to 1e9:

    79      3796948
    37      3595468
    19      2744958
    97      3046626
    31      3046813
    71      3243702
    93      3243354
    33      2229686
    11      2328414
    73      3443707
    99      2328896
    17      3842263
    39      3840531
    77      2227956
    13      3795751
    91      4092457

In a sibling answer, steveklabnik suggests the Rust version was compiled without optimizations - https://news.ycombinator.com/item?id=11285569

Could you try running both on the same machine? I'm curious if LuaJIT can still beat Rust if both have optimizations working.

I know it can beat native code sometimes, which is pretty impressive (it finds common cases and specializes to them AFAIK, almost like "sufficiently advanced optimizing compiler" fairy tales).

I don't know how to Rust, but you are welcome to try it. LuaJIT is amazingly fast. It shouldn't be faster than native code in general, but it's still not orders of magnitude behind like interpreted languages are. As I understand it, JITs can sometimes do better by doing statistics on code paths and optimizing them.

And of course, it takes 0 seconds to compile, if you factor in that time : )

LuaJIT 2.0.4:

3.67user 0.01system 0:03.68elapsed 99%CPU

rustc 1.9.0-nightly (74b886ab1 2016-03-13) (-C opt-level=3):

5.18user 0.00system 0:05.20elapsed 99%CPU

Switching to BTreeMap gives me:

4.36user 0.00system 0:04.38elapsed 99%CPU

Using u8 as the key (last_digit0*10 + last_digit1) instead of a string:

4.18user 0.00system 0:04.18elapsed 99%CPU

I tried preallocating the vector of primes and it didn't help, strangely enough.

Replacing the floating-point sqrt with squaring in the comparison does bring it a bit lower:

4.04user 0.00system 0:04.05elapsed 99%CPU

I don't know how to bring that number lower without using a sieve, perf reports that most of the time is spent in:

86,31 │ div %rbx

I've also just noticed that the Lua and the Rust code don't give the same results, but I can't easily tell why.

Oh! The largest prime is 0x00ec4bab, so they can be stored as u32. Final Rust result:

2.33user 0.00system 0:02.33elapsed 99%CPU

Code: https://gist.github.com/eddyb/51a92fa2edf20d6e23fe

Nice. I suppose I should try optimizing the Lua code some more. There are some nasty branches in there that might slow it down.

The Lua code is not exactly identical to the rust code. I test all numbers less than n, as opposed to counting n primes. I set n so it got slightly more primes than the rust code though.

He diagnosed it correctly - I was running debug builds instead of release builds. Shaves 80% off my 20 sec runtime without including any of the other optimizations he shared.

The hashing optimization isn't necessary as using String at all is wasteful - my code ended up being simpler, but in the end the largest gain came from replacing u64 with u32 - see https://news.ycombinator.com/item?id=11290955.

Haskell:

  import Data.Numbers.Primes
  import Data.Counter

  countPrimeTransitions n = count $ zip primeEndings (tail primeEndings)
    where primeEndings = take (n+1) (map (`mod` 10) primes)

I have no idea what's happening but I think you just won

Couple useful speedups for your loop: you only need the xrange to go up to floor of sqrt(p), since any divisor would have been found already by that point. Also you can save a lot of divisions by working as a sieve with the first couple thousand primes (so check divisibility against a store list of primes, instead of all numbers, for as long as your memory allows).

Perl 6 version:

    my $primes := (1..*).grep(*.is-prime);

    my %count;
    for ^100000 -> $i {
        %count{($primes[$i] % 10) ~ '-' ~ ($primes[$i+1] % 10)}++; 
    }

    for %count.keys.sort -> $key {
        say "$key = { %count{$key} }";
    }

(I didn't skip the outliers, but I did explicitly write out the count so that it was in order.)

Results from the first 100,000 primes:

And because I couldn't resist, here's a one-liner (for calculations, anyway) version:

    my %count := (1..*).grep(*.is-prime).map(* % 10).rotor(2 => -1).map(~*)[^100000].Bag;

I think it's a bit slower than my previous version. (And much slower than the Rust version posted elsewhere here!)

without spending the time to make a better prime generator, you can get your test going much faster by only testing factors up till sqrt(p).

With just that change to your program, and asking for 100k primes:

{'9-1': 8829, '1-1': 4104, '9-7': 5671, '3-9': 8387, '3-7': 7419, '7-1': 6438, '1-3': 7961, '3-3': 3604, '7-9': 8022, '1-7': 8297, '7-3': 6928, '1-9': 4605, '3-1': 5596, '7-7': 3627, '9-3': 6513, '9-9': 3994}

Thanks for the pointer, sounds like a reasonable speedup to the basic algorithm :)

So among the less populated set of same final digit-ed sequential primes is the next-digit-more-significant anti-correlated (to mitigate its 'misbehavior' ;)? In a sense, how likely does this unusual homo-digitalism rise once our focus on the final digit is shifted?

Shouldn't that be `if p % x == 0:`, not `if p % 2 == 0:`?

Yes, exactly, another bad typo ¬¬

Thanks for pointing it out, I did this over an IPython session and copied it in a (completely unnecesary) hurry. The results are good though :)

Edit: as to keep my claim that the results are good, check this sentence from the article "...Nor could it explain why, as the pair found, primes ending in 3 seem to like being followed by primes ending in 9 more than 1 or 7." -- it backs up the data I posted :)

Using sqrt and Numba - decorating the primer function with @numba.jit(nopython=True) - allows you to check the first million in around 15 seconds.