Anarchy

Contents

• Utility Functions
• Random Number Generator Functions
• Cohort Functions
• Distribution Functions

Libraries

• anarchy

Examples

• test_anarchy.lua

Source

• anarchy.lua
• test_anarchy.lua

Module anarchy

anarchy.lua

Reversible chaos library (version for Lua 5.3+).

Info:

• Copyright: 2025 Peter Mawhorter
• Release: 1.0-1

  This version uses the native integers available in Lua versions 5.3+, which are 64-bit integers by default or 32-bit integers if your Lua was compiled with only 32-bit integer support.

  If you want to use Lua 5.1, 5.2 or LuaJIT, use the 'anarchy32' library instead, although performance and probably quality will be worse.

  See more details in the README file.

• Author: Peter Mawhorter

Utility Functions

Random Number Generator Functions

Cohort Functions

Distribution Functions

Utility Functions

anarchy.util.posmod (num, base) line 55

Modulus that's always positive Use % operator instead in Lua since it has the same behavior. Included for compatibility with anarchy implementations in other languages.

Parameters:

• num number The number to compute the modulus of.
• base number The base of the modulus.

Returns:

number The number modulo the base.

anarchy.util.hash_string (s) line 64

A string hashing function. See: https://stackoverflow.com/questions/7616461/generate-a-hash-from-string-in-javascript-jquery

Parameters:

• s string The string to hash

Returns:

number The hash for that string

anarchy.util.mask (bits) line 85

Creates a mask with the given number of 1 bits, up to anarchy.ID_BITS maximum (any larger value gives all-1s, same as if you had given anarchy.ID_BITS).

Parameters:

• bits number The number of 1 bits to put in the mask.

Returns:

number A value with that many 1 bits starting from the least significant place.

anarchy.util.byte_mask (n) line 95

Returns a mask that covers just the nth byte (zero-indexed), starting from the least-significant digits. Returns 0 if n is >= anarchy.ID_BYTES.

Parameters:

• n number The byte index (starting from 0)

Returns:

number The mask with 1s in that byte and 0s elsewhere

Random Number Generator Functions

anarchy.rng.swirl (x, distance) line 114

Circular bit shift to the right Distance is capped at 3/4 of ID_BITS

Parameters:

• x number The number to swirl.
• distance number How far to swirl it.

Returns:

number The swirled number.

anarchy.rng.rev_swirl (x, distance) line 131

Circular bit shift to the left inverse of swirl Distance is capped at 3/4 of ID_BITS

Parameters:

• x number The number to unswirl.
• distance number How far to unswirl it.

Returns:

number The unswirled number.

anarchy.rng.fold (x, where) line 145

Folds lower bits into upper bits using xor. fold is its own inverse. 'where' is restricted to fall between 1/4 and 1/2 of ID_BITS.

Parameters:

• x number the number to fold.
• where number which tit to fold at

anarchy.rng.flop (x) line 171

Flops each 1/2 byte with the adjacent 1/2 byte. flop is its own inverse.

Parameters:

• x number the number to flop

Returns:

number The flopped number

anarchy.rng.scramble (x) line 205

Implements a reversible linear-feedback-shift-register-like operation.

Parameters:

• x number the number to scramble.

Returns:

number the scrambled number

anarchy.rng.rev_scramble (x) line 226

Inverse of scramble (see above).

Parameters:

• x number the number to unscramble

Returns:

number the unscrambled number

anarchy.rng.scramble_seed (s) line 244

Scrambles a seed value to help separate RNG sequences generated from sequential seeds.

Parameters:

• s number the seed to scramble

Returns:

number the scrambled seed

anarchy.rng.prng (x, seed) line 264

A simple reversible pseudo-random number generator You can call anarchy.rng.rev_prng with the result of this function and the same seed to get back the number you put in here, so that results form a chain you can traverse forwards or backwards.

Parameters:

• x number the current/previous number
• seed number the generation sequence seed (this can be constant for a bunch of calls)

Returns:

number the next number in the generation sequence

anarchy.rng.rev_prng (x, seed) line 286

Inverse of anarchy.rng.prng (see above).

Parameters:

• x number the current/next number
• seed number the generation seed that determines the sequence

Returns:

number the previous number in the generation sequence

anarchy.rng.lfsr (x) line 328

Implements a max-cycle-length 32-bit linear feedback shift register. See: https://en.wikipedia.org/wiki/Linear-feedbackshiftregister Note that this is NOT reversible! Note: Do not use this as an irreversible PRNG; it's a terrible one! Note: Zero is a fixed point of this function: do not use it as your seed!

Parameters:

• x number the current number

Returns:

number the next number in the LFSR sequence

anarchy.rng.uniform (seed) line 349

Generates a random number between 0 and 1 given a seed value.

Parameters:

• seed number The seed that determines the result.

Returns:

number A number between 0 (inclusive) and 1 (exclusive)

anarchy.rng.normalish (seed) line 361

Generates and averages three random numbers between 0 and 1 to give a pseudo-gaussian-distributed random number (still strictly on [0, 1) )

Parameters:

• seed number The seed that determines the result.

Returns:

number A number between 0 (inclusive) and 1 (exclusive) which is more likely to be near 0.5 than near either 0 or 1.

anarchy.rng.flip (p, seed) line 378

Flips a coin with probability p of being True. Using the same seed always gives the same result.

Parameters:

• p number The probability that the result should be True when results are averaged across many different seeds.
• seed number The seed that determines the result.

Returns:

boolean Either true (with probability p when averaged across seeds) or false (with probability 1-p when averaged across seeds).

anarchy.rng.integer (seed, start, cap) line 399

Even distribution over the given integer range, including the start but excluding the cap (even if the cap is lower than the start). The last number before the cap is about 1/anarchy.rng.U_DIVISOR less likely to be generated than the other numbers.

Note: Why route integer stuff through uniform instead of just using a modulus which would be faster? Because we have little idea how selective biased lfsr and/or prng values might be for an arbitrary modulus. Our prng is almost certainly NOT capable of producing every 64-bit number, for example, and might even have some short cycles out there somewhere.

Parameters:

• seed number The seed that determines the result.
• start number The minimum allowed result value.
• cap number The result limit (will NOT ever be generated itself).

Returns:

number An integer between start (inclusive) and cap (exclusive).

anarchy.rng.exponential (seed, lambda) line 415

Generates a number from an exponential distribution on [0,∞) with mean 1/lambda given a seed. Higher values of lambda make the distribution more sharply exponential; values between 0.5 and 1.5 exhibit reasonable variation. See: https://math.stackexchange.com/questions/28004/random-exponential-like-distribution and https://en.wikipedia.org/wiki/Exponential_distribution

Parameters:

• seed number The seed that determines the result.
• lambda number The shape parameter for the distribution.

Returns:

number An arbitrarily large number (subject to the limits of the number type) that's much more likely to be small than large.

anarchy.rng.truncated_exponential (seed, lambda) line 430

Generates a number from a truncated exponential distribution on [0, 1), given a particular seed. As with expdist, the lambda parameter controls the shape of the distribution, and a 0.5–1.5 range is usually reasonable. For why this method works, see: https://math.stackexchange.com/questions/28004/random-exponential-like-distribution

Parameters:

• seed number The seed that determines the result.
• lambda number The shape parameter for the distribution.

Returns:

number A number between 0 (inclusive) and 1 (exclusive) that is much more likely to be small than large.

Cohort Functions

anarchy.cohort.cohort (outer, cohort_size) line 459

Computes cohort number for the given outer index and cohort size.

Parameters:

• outer number An index into a sequence to be chopped into cohorts, starting with the beginning of the first cohort at index 1.
• cohort_size number The size of each cohort to divide the sequence into.

Returns:

number The index of the cohort that the outer index falls into. The first cohort (starting at index 1 of the outer sequence) has index 1.

For example, if outer index is 54 and cohort_size is 10, the return value will be 6, since 54 falls into the 6th group of 10.

anarchy.cohort.cohort_inner (outer, cohort_size) line 476

Computes within-cohort index for the given outer index and cohorts of the given size.

Parameters:

• outer number An index into a sequence to be chopped into cohorts, starting with the beginning of the first cohort at index 1.
• cohort_size number The size of each cohort to divide the sequence into.

Returns:

number The index of the given outer index within its cohort, starting from 1 in the first position.

For example, if the outer index is 54 and the cohort_size is 10, the result will be 4, since 54 falls at index 4 within its group of 10 (starting at index 1 at 51).

anarchy.cohort.cohort_and_inner (outer, cohort_size) line 491

Returns two results: the cohort number and inner index for the given outer index and cohort size.

Parameters:

• outer number An index into a sequence to be chopped into cohorts.
• cohort_size number The size of each cohort to divide the sequence into.

Returns:

multiple Multiple values: The cohort index (an integer) followed by the inner index within that cohort (also an integer).

For example, if the outer index is 29 and the cohort_size is 10, this will return 3, 9

anarchy.cohort.cohort_outer (cohort, inner, cohort_size) line 514

Inverse of cohortandinner; computes the outer index from a cohort number and inner index.

Parameters:

• cohort number The cohort index determining which group a position belongs to.
• inner number The index of the position within that group. Should be between 1 and the cohort size, inclusive.
• cohort_size number The size of each group to divide the total sequence of positions into.

Returns:

number The index of that position within the total sequence of positions, starting from index 1.

For example, if cohort is 3, inner is 1, and cohort_size is 5, then we're at index 1 (1st item) within the 3th group of 5 things, putting us at total index 5*2 + 1 = 11 outside of the groups.

Note: Negative cohort and/or inner indices may result in negative outer indices. The inner index value is not constrained to be smaller than the cohort size.

anarchy.cohort.cohort_interleave (inner, cohort_size) line 526

Interleaves cohort members by folding the top half into the bottom half. The bottom half get even indices while the top half are assigned backwards to the odd indices.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.

Returns:

number The new within-cohort index for the same item after interleaving the top and bottom parts of the cohort.

anarchy.cohort.rev_cohort_interleave (inner, cohort_size) line 541

Inverse interleave (see above).

Parameters:

• inner number The index of an item within a cohort after interleaving items.
• cohort_size number The size of each cohort.

Returns:

number The original index within that cohort that the item would have been at prior to interleaving things.

anarchy.cohort.cohort_fold (inner, cohort_size, seed) line 558

Folds items past an arbitrary split point (in the second half of the cohort) into the middle of the cohort. The split will always leave an odd number at the end.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines where the fold happens.

Returns:

number The new index of the item within the cohort after folding.

anarchy.cohort.rev_cohort_fold (inner, cohort_size, seed) line 587

Inverse fold (see above).

Parameters:

• inner number The index of an item within a cohort after folding.
• cohort_size number The size of each cohort.
• seed number The seed that determines where the fold happened.

Returns:

number The original index that would have been folded into the given position if cohort_fold were used with the same seed..

anarchy.cohort.cohort_spin (inner, cohort_size, seed) line 615

Applies a circular offset

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how far to spin.

Returns:

number The index of the item after spinning.

anarchy.cohort.rev_cohort_spin (inner, cohort_size, seed) line 625

Inverse spin (see above).

Parameters:

• inner number The index of an item within a cohort after being spun.
• cohort_size number The size of each cohort.
• seed number The seed that determined how far to spin.

Returns:

number The original index of the item before spinning.

anarchy.cohort.cohort_flop (inner, cohort_size, seed) line 639

Flops sections (with seeded sizes) with their neighbors.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how big each section to flop is.

Returns:

number The index of the item after flopping with a neighboring sesction.

anarchy.cohort.cohort_mix (inner, cohort_size, seed) line 670

Applies a spin to even and odd items separately with different seeds.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how far to spin evens & odds.

Returns:

number The index of the item after spinning the even & odd elements among themselves with different (derived) seeds.

anarchy.cohort.rev_cohort_mix (inner, cohort_size, seed) line 697

Inverse mix (see above).

Parameters:

• inner number The index of an item within a cohort after mixing.
• cohort_size number The size of each cohort.
• seed number The seed that determined how far to spin evens & odds.

Returns:

number The index that this index would have been before mixing with the given seed.

anarchy.cohort.cohort_spread (inner, cohort_size, seed) line 732

Spreads items out between a random number of different regions within the cohort.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines how many regions we use.

Returns:

number The index after spreading out indices between random regions.

anarchy.cohort.rev_cohort_spread (inner, cohort_size, seed) line 763

Inverse spread (see above).

Parameters:

• inner number The index of an item within a cohort after spreading.
• cohort_size number The size of each cohort.
• seed number The seed that determined how many regions we use.

Returns:

number The index that would have been used to generate the provided index with a spread operation and the given seed.

anarchy.cohort.cohort_upend (inner, cohort_size, seed) line 795

Reverses ordering within each of several fragments.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determined how many regions we use.

Returns:

number The index after upending the order of each region.

anarchy.cohort.cohort_shuffle (inner, cohort_size, seed) line 832

Compose a bunch of the above functions to perform a nice thorough shuffle within a cohort.

Parameters:

• inner number The index of an item within a cohort.
• cohort_size number The size of each cohort.
• seed number The seed that determines where to shuffle things.

Returns:

number The position of the index after shuffling the cohort. When shuffling two different indices with the same cohort size and seed, you'll get two different results. Usually not the same as the original index.

anarchy.cohort.rev_cohort_shuffle (inner, cohort_size, seed) line 880

Inverse shuffle (see above).

Parameters:

• inner number The index of an item within a cohort after shuffling.
• cohort_size number The size of each cohort.
• seed number The seed that determined where to shuffle things.

Returns:

number The original index within the cohort that would have been shuffled into the specified position.

Distribution Functions

anarchy.distribution.distribution_split_point (total, n_segments, segment_capacity, roughness, seed) line 966

Implements common distribution functionality: given a total item count, a segment count and per-segment capacity, and a roughness value and seed, computes the split point for the items as well as the halfway index for the segments.

Note that per the normal Lua convention, indices for both total items and segments start from 1!

Parameters:

• total number The total number of items that will be distributed among segments.
• n_segments number The number of segments to distribute the items into.
• segment_capacity number The capacity of each segment. nsegments times segmentcapacity must be >= total.
• roughness number A number between 0 and 1. When roughness is 0, items will be split across segments as evenly as possible. When roughness is 1, up to 100% of the items may be placed into the first or second half of the segments while recursively apportioning items. At roughness 0.5 the first or second half of the segments might get as little as 50% of what it would get when roughness is 0.
• seed number The seed that determines how the total gets distributed among the segments when roughness allows different distributions.

Returns:

multiple Multiple results: two numbers. The first is the split point for the distribution: the number out of the total items which end up in the first half of the segments. The second is the number of segments in that first half of the segments, which is half of n_segments, rounded down.

anarchy.distribution.distribution_items (segment, total, n_segments, segment_capacity, roughness, seed) line 1049

Given that 'total' items are to be distributed evenly among 'nsegment' segments each with at most 'segmentcapacity' items and we're in segment 'segment' of those (indexed from 1), computes the start index (from 1) among the total of the first item in this segment, and how many items are in this segment. The 'roughness' argument should be a number between 0 and 1 indicating how even the distribution is: 0 indicates a perfectly even distribution, while 1 indicates a perfectly random distribution. Does work proportional to the log of the number of segments.

Note that segmentcapacity * nsegments should be > total.

Parameters:

• segment number Which segment we want to know the portion for, as an index starting from 1.
• total number The total number of items that will be distributed among segments.
• n_segments number The number of segments to distribute the items into.
• segment_capacity number The capacity of each segment. nsegments times segmentcapacity must be >= total.
• roughness number A number between 0 and 1. When roughness is 0, items will be split across segments as evenly as possible. When roughness is 1, up to 100% of the items may be placed into the first or second half of the segments while recursively apportioning items. At roughness 0.5 the first or second half of the segments might get as little as 50% of what it would get when roughness is 0.
• seed number The seed that determines how the total gets distributed among the segments when roughness allows different distributions.

Returns:

multiple Multiple values: the start index (from 1) of the first item in this segment and the number of the total items that get distributed into the specified segment, for the given seed. The number of items May be as low as 0 when roughness is 1; it will be one of the integers adjacent to (total / n_segments) when roughness is 0. If the number of items is 0, then the 'start index' will be the same as the 'start index' for the subsequent segment (and if multiple segments in a row get 0 items they'll all share the same start index with the first segment after them that gets at least 1 item).

anarchy.distribution.distribution_segment (index, total, n_segments, segment_capacity, roughness, seed) line 1125

Computes the segment number in which a certain item appears (one of the 'total' items distributed between segments; see distribution_items above). Requires work proportional to the log of the number of segments.

Parameters:

• index number Which item among the total we want to know the fate of, starting from 1. Must be less than or equal to the total.
• total number The total number of items that will be distributed among segments.
• n_segments number The number of segments to distribute the items into.
• segment_capacity number The capacity of each segment. nsegments times segmentcapacity must be >= total.
• roughness number A number between 0 and 1. When roughness is 0, items will be split across segments as evenly as possible. When roughness is 1, up to 100% of the items may be placed into the first or second half of the segments while recursively apportioning items. At roughness 0.5 the first or second half of the segments might get as little as 50% of what it would get when roughness is 0.
• seed number The seed that determines how the total gets distributed among the segments when roughness allows different distributions.

Returns:

multiple Multiple values: the segment index (starting from 1) within which the indicated item appears, and then the index within that segment (starting from 1) at which it is placed.

anarchy.distribution.sumtable_for_distribution (total, n_segments, segment_capacity, roughness, seed) line 1196

Takes distribution parameters and returns a table containing the cumulative sum of items in each segment (The table indices will start at 1, just like the segment indices). The list contains n_segments entries, and each entry holds the sum of the items from the total assigned to that segment plus all earlier segments. This means that each entry is greater than or equal to the entry before it (and they're only equal if zero items are assigned to that segment). The last entry will be equal to the total.

Parameters:

• total number The total number of items being distributed.
• n_segments number The number of segments to distribute items among.
• segment_capacity number The capacity of each segment.
• roughness number How rough the distribution should be (0-1).
• seed number The seed that determines a specific distribution.

Returns:

table An array table holding cumulative sums, starting at index 1 with the number of items in the first segment.

n_segments times segment_capacity must be >= total otherwise an error will be raised.

anarchy.distribution.fill_sumtable_for_distribution (ledger, start, prior) line 1254

Recursively fills in the sumtable based on the distribution parameters given (see sumtable_for_distribution). Total work done is n_segments times log(n_segments).

Note that using a sumtable instead of using the distribution functions with the same parameters over and over again represents a space/time tradeoff. Most operations on a sumtable are O(1), where equivalent distribution functions need O(log(n)) time. The sumtable needs to store one integer per segment. The use of distribution functions is recommended primarily in situations where the algorithm structure makes it inconvenient to store the sumtable in an accessible way, so sharing parameters is easier. Parameters are the same as for sumtable_for_distribution but with:

Parameters:

• ledger table The table to fill in. Values will be added/overwritten between start and start + n_segments - 1 (inclusive).
• start number The index at which to start overwriting values (counting from index 1).
• prior number The number of items distributed prior to the start index.

Returns:

nil No return (modifies the given ledger).

anarchy.distribution.sumtable_from_portions (portions) line 1317

Returns a sumtable for the same distribution, where entries are the cumulative sum of all portions up to an index, rather than just the portion at that index. Use functions like sumtable_total, sumtable_segments, sumtable_portion, and sumtable_segment to get information out of the sumtable efficiently.

Parameters:

• portions table The array of per-segment item counts, indexed starting at 1.

Returns:

table The sumtable that encodes the same distribution (also indexed from 1, like all normal Lua tables. Hahaha why would we even mention this?).

anarchy.distribution.sumtable_total (sumtable) line 1337

Returns the total number of items across all segments in a sumtable, which is just the last entry in that table.

Parameters:

• sumtable table The table of sums describing the distribution in question.

Returns:

number The total number of items distributed.

anarchy.distribution.sumtable_segments (sumtable) line 1350

Returns the number of segments in the given sumtable, which is just its length.

Parameters:

• sumtable table The table of sums describing the distribution in question.

Returns:

number The number of segments in the distribution.

anarchy.distribution.sumtable_portion (sumtable, i) line 1367

Returns the portion of the total items which is distributed into the segment with the given index (starting from 1). Just needs to subtract the entry to the left to figure this out. Raises an error if the index is invalid.

Parameters:

• sumtable table The table of sums describing the distribution in question.
• i number The segment to compute the portion for (from 1).

Returns:

number The number of items distributed into the specified segment.

anarchy.distribution.sumtable_items (sumtable, i) line 1398

Returns a pair containing the index of the first item in the segment and then the number of items in that segment, like distribution_items, but for a sumtable. Parameters:

Parameters:

• sumtable table The table of sums describing the distribution in question.
• i number The segment to compute the portion for (from 1).

Returns:

multiple Two numbers: The index of the first item in the segment (from index 1), then the number o items in the indicated segment.

anarchy.distribution.sumtable_segment (sumtable, item) line 1429

Uses binary search to find the index of the smallest sum in the given sumtable that's greater than or equal to the given value breaking ties towards earlier entries. Works in time proportional to the logarithm of the sumtable size. This will be the segment which the given item (out of the total) falls into.

Raises an error if the sumtable is empty, or if the item index is too large for the sumtable or is zero or negative.

Parameters:

• sumtable table The table of sums describing the distribution in question.
• item number The item (out of the total distributed, starting from 0) that we want to find the segment for.

Returns:

number The segment index (starting from 1) for the specified item.