All posts tagged "number-theory"
Non-binary Linear Feedback Shift Registers
There’s way too much documentation about binary LFSRs out there, and not a whole lot on doing the same with other bases. Here are some tables for other bases so things can be thrown together without too much thought.
Extended checks on manual arithmetic
So you’ve done some arithmetic by hand and now you want to make sure it’s correct. Casting out nines is the conventional sanity check, but that has weaknesses. What if you want something stronger? Try this one weird trick.
Digits for a base-210 system
My own contribution to the field of making up improbable alien number systems involves counting in base 210. Rather than try to define 210 distinct symbols, or to make a 14-upon-15 or 15-upon-14 digit pair system, I chose to break each digit down into three components mod 5, mod 6, and mod 7.
Optimising Adler-32 checksum
The Adler-32 checksum consists of two 16-bit sums. One is the sum of all the bytes in the data, plus one, and the other is the sum of all those intermediate sums, which works out to be the same as the sum of all the bytes multiplied by their distance from the end of the buffer plus the length of the buffer. Both modulo 65521.
N-bit Mixer Functions
For reasons I intend (hah!) to go into in a longer post I was looking for operations with which to construct and whiten (or “finalise” or “mix” or “avalanche” or whatever) RNGs with 2n periods. I was looking at splitmix64 which led me to Fast splittable pseudorandom number generators which cited Improving on MurmurHash3’s 64-bit Finalizer (although I found that page by other means) and finally MurmurHash3 which tells me where those constants and that construction both come from.
Minimally biased NPOT-ranged random numbers
In my previous post I described a technique for scaling random numbers to new intervals producing extremely small bias but with a constant execution time.
Random number scaling
I’ve been doing some messing around with random number generation at work, and this inspired me to revisit something which has troubled me since my teenage years: Perfectly unbiased random numbers over a range which is not a power of two.
See also: