It’s a billion times integer modulus, summed. Div/mod is by far the slowest arithmetic instruction on a CPU, so it underestimates C/rust performance. I guess the author chose that to prevent the C compiler from optimizing the loop away.

▲

bddicken 7 months ago | parent [-]

Author here: Yeah, the mod was added to reduce risk of loop(s) getting optimized away.

▲

remcob 7 months ago | parent [-]

Did you verify this through disassembly? These loops can still be replaced by a closed form expression and I wouldn’t be surprised if LLVM figured this out.

▲

namibj 7 months ago | parent | next [-]

Sooooo.... anyone know a compiler that actually does the closed form tactic on the loop(s)? If I see correctly, in theory the program could be compiled down to something that finishes nearly instantly, with no loops at all?

▲

Dylan16807 7 months ago | parent | prev [-]

If it turned the inner loop into a closed form expression, I would expect the outer loop to go through 10k iterations a lot faster than needing half a second.

	▲	zamadatix 7 months ago \| parent [-]
		Running the C code through Godbolt with the same Clang and -O3 optimizations it looks like you're right, there are still 2 loops being performed. The loops are unrolled to perform 4 iterations at a time but it's otherwise the same. Other than that it didn't do too much with the loops. Hilariously there is a god awful set of shifts and magic numbers... to save a single modulo operation from running once on the line declaring 'r'. See here for why the Go version performs worse https://news.ycombinator.com/item?id=42251571