kactl

I was reading about an implementation of Barrett reduction recently: https://en.wikipedia.org/wiki/Barrett_reduction Specifically one that uses 80-bit long double for calculating `(__int128_t)a * b % M` from this github: https://github.com/kth-competitive-programming/kactl/blob/ma... But how do you test the correctness of such code? You can't just stress test all possible product of 64 bit numbers! In the end you still gotta go back to good old fashion proofs: https://github.com/kth-competitive-programming/kactl/blob/ma...

https://github.com/kth-competitive-programming/kactl/blob/master/kactl.pdf I've occasionally seen sources of algorithms/data structures posted on HN, but they've mostly been fairly low quality. This source was created/maintained for the International Collegiate Programming Competition, which has a 25 page limit. Among others, the last 3 MIT ICPC teams have used a variant of this notebook. Some neat things in this notebook: The fastest 64 bit mod mul implementation I've seen (uses doubles and proven correct): https://github.com/kth-competitive-programming/kactl/blob/master/content/number-th… A fast/short implementation of FFT: https://github.com/kth-competitive-programming/kactl/blob/master/content/numerical… A bump allocator: https://github.com/kth-competitive-programming/kactl/blob/master/content/vario