Package squidpony.squidmath

Class VanDerCorputQRNG

java.lang.Object
squidpony.squidmath.VanDerCorputQRNG
All Implemented Interfaces:
Serializable, RandomnessSource, StatefulRandomness
public class VanDerCorputQRNG
extends Object
implements StatefulRandomness, RandomnessSource, Serializable
A quasi-random number generator that goes through one of many sub-random sequences found by J.G. van der Corput. More specifically, this offers the standard family of van der Corput sequences, each defined by a (almost always prime) base number. Each sequence only changes the state by incrementing it (this works better in the normal usage as part of a 2D or 3D point generator). The state is internally stored in a 64-bit long that is incremented once per generated number. The important things to know about this class are: size of state affects speed (prefer smaller seeds, but quality is sometimes a bit poor at first if you start at 0); the base (when given) should be prime (smaller bases tend to yield better quality, but oddly, larger bases perform better); this doesn't generate very random numbers, and is classified as a quasi-random number generator (which can be good for making points that should not overlap); this is a StatefulRandomness with an additional method for generating quasi-random doubles, nextDouble(); and there are several static methods offered for convenient generation of points on the related Halton sequence (as well as faster generation of doubles in the base-2 van der Corput sequence, and a special method that switches which base it uses depending on the index to seem even less clearly-patterned). There are also, for lack of a better place to put such small code, methods to generate points in the R2 sequence found by Martin Roberts, which is very similar in 2D to some Halton sequences but has better separation between points.
This generator allows a base (also called a radix) that changes the sequence significantly; a base should be prime, and this performs better in terms of time used with larger primes, though quality is also improved by preferring primes that aren't very large relative to the quantity of numbers expected to be generated. Unfortunately, performance is not especially similar to conventional PRNGs; smaller (positive) state values are processed more quickly than larger ones, or most negative states. At least one 64-bit integer modulus and one 64-bit integer division are required for any number to be produced, and the amount of both of these relatively-non-cheap operations increases linearly with the number of digits (in the specified base, which is usually not 10) needed to represent the current state. Since performance is not optimal, and the results are rather strange anyway relative to PRNGs, this should not be used as a direct substitute for a typical RandomnessSource (however, it is similar to, but simpler and faster than, SobolQRNG). So what's it good for?
A VanDerCorputSequence can be a nice building block for more complicated quasi-randomness, especially for points in 2D or 3D. There's a simple way that should almost always "just work" as the static method halton(int, int, int, int[]) here. If it doesn't meet your needs, there's a little more complexity involved. Using a VanDerCorputQRNG with base 3 for the x-axis and another VanDerCorputQRNG with base 5 for the y-axis, requesting a double from each to make points between (0.0, 0.0) and (1.0, 1.0), has an interesting trait that can be desirable for many kinds of positioning in 2D: once a point has been generated, an identical point will never be generated until floating-point precision runs out, but more than that, nearby points will almost never be generated for many generations, and most points will stay at a comfortable distance from each other if the bases are different and both prime (or, more technically, if they share no common denominators). This is also known as a Halton sequence, which is a group of sequences of points instead of simply numbers. The choices of 3 and 5 are examples; any two different primes will technically work for 2D (as well as any two numbers that share no common factor other than 1, that is, they are relatively coprime), but patterns can be noticeable with primes larger than about 7, with 11 and 13 sometimes acceptable. Three VanDerCorputQRNG sequences could be used for a Halton sequence of 3D points, using three different prime bases, four for 4D, etc. SobolQRNG can be used for the same purpose, but the points it generates are typically more closely-aligned to a specific pattern, the pattern is symmetrical between all four quadrants of the square between (0.0, 0.0) and (1.0, 1.0) in 2D, and it probably extends into higher dimensions. Using one of the possible Halton sequences gives some more flexibility in the kinds of random-like points produced. Oddly, using a base-2 van der Corput sequence as the x axis in a Halton sequence and a base-39 van der Corput sequence as the y axis results in the greatest minimum distance between points found so far while still involving a base-2 sequence (which is preferential for performance). There, the minimum distance between the first 65536 points in the [0,1) range is 0.001147395; a runner-up is a y base of 13, which has a minimum distance of 0.000871727 . The (2,39) Halton sequence is used by halton(int, int, int) and halton(int, int, int, int[]).
Created by Tommy Ettinger on 11/18/2016. Uses code adapted from Alan Wolfe's blog, which turned out to be a lot faster than the previous way I had it implemented.
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    int base  
    long state  

  • Constructor Summary

    Constructors 
    Constructor Description
    VanDerCorputQRNG()
    Constructs a new van der Corput sequence generator with base 7, starting point 37, and scrambling disabled.
    VanDerCorputQRNG​(int base, long seed)
    Constructs a new van der Corput sequence generator with the given base (a.k.a.
    VanDerCorputQRNG​(long seed)
    Constructs a new van der Corput sequence generator with the given starting point in the sequence as a seed.

  • Method Summary

    Modifier and Type Method Description
    static double altDetermine​(long base, int index)
    Similar to determine(int, int), but can take bases that aren't prime and can sometimes produce a Halton-like sequence with almost-as-good distance between points.
    VanDerCorputQRNG copy()
    Produces a copy of this StatefulRandomness that, if next() and/or nextLong() are called on this object and the copy, both will generate the same sequence of random numbers from the point copy() was called.
    static double determine​(int base, int index)
    Convenience method to get a double from the van der Corput sequence with the given base at the requested index without needing to construct a VanDerCorputQRNG.
    static double determine2​(int index)
    Convenience method to get a double from the van der Corput sequence with the base 2 at the requested index without needing to construct a VanDerCorputQRNG.
    static double determine2_scrambled​(int index)
    Method to get a double from the van der Corput sequence with the base 2 at a scrambling of the requested index without needing to construct a VanDerCorputQRNG.
    static double determineMixed​(int index)
    Chooses one sequence from the van der Corput sequences with bases 2, 3, and 5, where 5 is used 1/8 of the time, 3 is used 3/8 of the time, and 2 is used 1/2 of the time, and returns a double from the chosen sequence at the specified index.
    boolean equals​(Object o)  
    long getState()
    Get the current internal state of the StatefulRandomness as a long.
    static Coord haltoid​(int seed, int width, int height, int xOffset, int yOffset, int index)
    Samples a quasi-random Coord sequence that is almost unique to the given seed, getting a Coord with x between xOffset (inclusive) and width + xOffset (exclusive), y between yOffset (inclusive) and height + yOffset (exclusive).
    static Coord halton​(int width, int height, int index)
    Convenience method that gets a quasi-random Coord between integer (0,0) inclusive and (width,height) exclusive and gets the corresponding Coord from the Coord pool.
    static Coord3D halton​(int width, int height, int depth, int index)
    Convenience method that gets a quasi-random Coord3D between integer (0,0,0) inclusive and (width,height,depth) exclusive.
    static int[] halton​(int width, int height, int index, int[] point)
    Convenience method that gets a quasi-random 2D point between integer (0,0) inclusive and (width,height) exclusive and fills it into point.
    static Coord halton​(int width, int height, int xOffset, int yOffset, int index)
    Convenience method that gets a quasi-random Coord between integer (0,0) inclusive and (width,height) exclusive and gets the corresponding Coord from the Coord pool.
    static int[] halton​(int width, int height, int depth, int index, int[] point)
    Convenience method that gets a quasi-random 3D point between integer (0,0,0) inclusive and (width,height,depth) exclusive.
    int hashCode()  
    int next​(int bits)
    Using this method, any algorithm that might use the built-in Java Random can interface with this randomness source.
    double nextDouble()
    Gets the next quasi-random double from between 0.0 and 1.0 (normally both exclusive; only if state is negative or has wrapped around to a negative value can 0.0 ever be produced).
    long nextLong()
    Gets the next quasi-random long as a fraction of Long.MAX_VALUE; this can never produce a negative value.
    static double planarDetermine​(long base, int index)
    A quasi-random number generator of doubles between 0.0 inclusive and 1.0 exclusive, but that has issues when it would be used like a Halton sequence.
    static int roberts​(int span, int offset, int index)
    Martin Roberts' "unreasonably effective" quasi-random int sequence based on the golden ratio.
    static Coord roberts​(int width, int height, int xOffset, int yOffset, int index)
    Martin Roberts' "unreasonably effective" quasi-random point sequence based on a 2D analogue to the golden ratio.
    void setState​(long state)
    Set the current internal state of this StatefulRandomness with a long.
    String toString()  
    static float weakDetermine​(int index)
    Given any int (0 is allowed), this gets a somewhat-sub-random float from 0.0 (inclusive) to 1.0 (exclusive) using the same implementation as NumberTools.randomFloat(long) but with index alterations.
    static float weakSignedDetermine​(int index)
    Like weakDetermine(int), but returns a float between -1.0f and 1.0f, exclusive on both.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Field Details

  • Constructor Details

    • VanDerCorputQRNG

      public VanDerCorputQRNG()
      Constructs a new van der Corput sequence generator with base 7, starting point 37, and scrambling disabled.

    • VanDerCorputQRNG

      public VanDerCorputQRNG​(long seed)
      Constructs a new van der Corput sequence generator with the given starting point in the sequence as a seed. Usually seed should be at least 20 with this constructor, but not drastically larger; 2000 is probably too much. This will use a base 7 van der Corput sequence and have scrambling disabled.
      Parameters:
      seed - the seed as a long that will be used as the starting point in the sequence; ideally positive but low

    • VanDerCorputQRNG

      public VanDerCorputQRNG​(int base, long seed)
      Constructs a new van der Corput sequence generator with the given base (a.k.a. radix; if given a base less than 2, this will use base 2 instead) and starting point in the sequence as a seed. Good choices for base are between 10 and 60 or so, and should usually be prime. Good choices for seed are larger than base but not by very much, and should generally be positive at construction time.
      Parameters:
      base - the base or radix used for this VanDerCorputQRNG; for most uses this should be prime but small-ish
      seed - the seed as a long that will be used as the starting point in the sequence; ideally positive but low

  • Method Details

    • nextLong

      public long nextLong()
      Gets the next quasi-random long as a fraction of Long.MAX_VALUE; this can never produce a negative value. It is extremely unlikely to produce two identical values unless the state is very high or is negative; state increases by exactly 1 each time this, next(int), or nextDouble() is called and can potentially wrap around to negative values after many generations.
      Specified by:
      nextLong in interface RandomnessSource
      Returns:
      a quasi-random non-negative long; may return 0 rarely, probably can't return Long.MAX_VALUE

    • next

      public int next​(int bits)
      Description copied from interface: RandomnessSource
      Using this method, any algorithm that might use the built-in Java Random can interface with this randomness source.
      Specified by:
      next in interface RandomnessSource
      Parameters:
      bits - the number of bits to be returned
      Returns:
      the integer containing the appropriate number of bits

    • nextDouble

      public double nextDouble()
      Gets the next quasi-random double from between 0.0 and 1.0 (normally both exclusive; only if state is negative or has wrapped around to a negative value can 0.0 ever be produced). It should be nearly impossible for this to return the same number twice unless floating-point precision has been exhausted or a very large amount of numbers have already been generated. Certain unusual bases may make this more likely.
      Returns:
      a quasi-random double that will always be less than 1.0 and will be no lower than 0.0

    • copy

      public VanDerCorputQRNG copy()
      Description copied from interface: StatefulRandomness
      Produces a copy of this StatefulRandomness that, if next() and/or nextLong() are called on this object and the copy, both will generate the same sequence of random numbers from the point copy() was called. This just needs to copy the state so it isn't shared, usually, and produce a new value with the same exact state.
      Specified by:
      copy in interface RandomnessSource
      Specified by:
      copy in interface StatefulRandomness
      Returns:
      a copy of this StatefulRandomness

    • getState

      public long getState()
      Description copied from interface: StatefulRandomness
      Get the current internal state of the StatefulRandomness as a long.
      Specified by:
      getState in interface StatefulRandomness
      Returns:
      the current internal state of this object.

    • setState

      public void setState​(long state)
      Description copied from interface: StatefulRandomness
      Set the current internal state of this StatefulRandomness with a long.
      Specified by:
      setState in interface StatefulRandomness
      Parameters:
      state - a 64-bit long. You should avoid passing 0, even though some implementations can handle that.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • equals

      public boolean equals​(Object o)
      Overrides:
      equals in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • halton

      public static int[] halton​(int width, int height, int index, int[] point)
      Convenience method that gets a quasi-random 2D point between integer (0,0) inclusive and (width,height) exclusive and fills it into point. This is roughly equivalent to creating two VanDerCorputQRNG generators, one with new VanDerCorputQRNG(2, index) and the other with new VanDerCorputQRNG(39, index), then getting an x-coordinate from the first with (int)(nextDouble() * width) and similarly for y with the other generator. The advantage here is you don't actually create any objects using this static method, only assigning to point, if valid. You might find an advantage in using values for index that start higher than 20 or so, but you can pass sequential values for index and generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but it is true for this one.
      Parameters:
      width - the maximum exclusive bound for the x-positions (index 0) of points this can return
      height - the maximum exclusive bound for the y-positions (index 1) of points this can return
      index - an int that, if unique, positive, and not too large, will usually result in unique points
      point - an int array that will be modified; should have length 2; if null or too small, a new array will be created
      Returns:
      point after modifications to the first two items, or a new array if point is null or too small

    • halton

      public static Coord halton​(int width, int height, int index)
      Convenience method that gets a quasi-random Coord between integer (0,0) inclusive and (width,height) exclusive and gets the corresponding Coord from the Coord pool. This is roughly equivalent to creating two VanDerCorputQRNG generators, one with new VanDerCorputQRNG(2, index) and the other with new VanDerCorputQRNG(39, index), then getting an x-coordinate from the first with (int)(nextDouble() * width) and similarly for y with the other generator. You might find an advantage in using values for index that start higher than 20 or so, but you can pass sequential values for index and generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but it is true for this one.
      Parameters:
      width - the maximum exclusive bound for the x-positions (index 0) of points this can return
      height - the maximum exclusive bound for the y-positions (index 1) of points this can return
      index - an int that, if unique, positive, and not too large, will usually result in unique points
      Returns:
      point after modifications to the first two items, or a new array if point is null or too small

    • halton

      public static Coord halton​(int width, int height, int xOffset, int yOffset, int index)
      Convenience method that gets a quasi-random Coord between integer (0,0) inclusive and (width,height) exclusive and gets the corresponding Coord from the Coord pool. This is roughly equivalent to creating two VanDerCorputQRNG generators, one with new VanDerCorputQRNG(2, index) and the other with new VanDerCorputQRNG(39, index), then getting an x-coordinate from the first with (int)(nextDouble() * width) and similarly for y with the other generator. You might find an advantage in using values for index that start higher than 20 or so, but you can pass sequential values for index and generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but it is true for this one.
      Parameters:
      width - the width of the area this can cover
      height - the height of the area this can cover
      xOffset - the lowest x-coordinate this can produce, and also added to width to get the upper bound on x
      yOffset - the lowest y-coordinate this can produce, and also added to height to get the upper bound on y
      index - an int that, if unique, positive, and not too large, will usually result in unique points
      Returns:
      point after modifications to the first two items, or a new array if point is null or too small

    • halton

      public static int[] halton​(int width, int height, int depth, int index, int[] point)
      Convenience method that gets a quasi-random 3D point between integer (0,0,0) inclusive and (width,height,depth) exclusive. This is roughly equivalent to creating three VanDerCorputQRNG generators, one with new VanDerCorputQRNG(2, index) another with new VanDerCorputQRNG(3, index), and another with new VanDerCorputQRNG(5, index), then getting an x-coordinate from the first with (int)(nextDouble() * width) and similarly for y and z with the other generators. The advantage here is you don't actually create any objects using this static method, only assigning to point, if valid. You might find an advantage in using values for index that start higher than 20 or so, but you can pass sequential values for index and generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but it is true for this one.
      Parameters:
      width - the maximum exclusive bound for the x-positions (index 0) of points this can return
      height - the maximum exclusive bound for the y-positions (index 1) of points this can return
      depth - the maximum exclusive bound for the z-positions (index 2) of points this can return
      index - an int that, if unique, positive, and not too large, will usually result in unique points
      point - an int array that will be modified; should have length 3; if null or too small, a new array will be created
      Returns:
      point after modifications to the first two items, or a new array if point is null or too small

    • halton

      public static Coord3D halton​(int width, int height, int depth, int index)
      Convenience method that gets a quasi-random Coord3D between integer (0,0,0) inclusive and (width,height,depth) exclusive. This is roughly equivalent to creating three VanDerCorputQRNG generators, one with new VanDerCorputQRNG(2, index) another with new VanDerCorputQRNG(3, index), and another with new VanDerCorputQRNG(5, index), then getting an x-coordinate from the first with (int)(nextDouble() * width) and similarly for y and z with the other generators. This overload always creates a new Coord3D object, so you might prefer halton(int, int, int, int, int[]), which can reuse an int array. You might find an advantage in using values for index that start higher than 20 or so, but you can pass sequential values for index and generally get points that won't be near each other; this is not true for all parameters to Halton sequences, but it is true for this one.
      Parameters:
      width - the maximum exclusive bound for the x-positions (index 0) of points this can return
      height - the maximum exclusive bound for the y-positions (index 1) of points this can return
      depth - the maximum exclusive bound for the z-positions (index 2) of points this can return
      index - an int that, if unique, positive, and not too large, will usually result in unique points
      Returns:
      a new Coord3D with x,y,z between 0,0,0 (inclusive) and width,height,depth (exclusive)

    • determine

      public static double determine​(int base, int index)
      Convenience method to get a double from the van der Corput sequence with the given base at the requested index without needing to construct a VanDerCorputQRNG. You should use a prime number for base; 2, 3, 5, and 7 should be among the first choices to ensure optimal quality unless you are scrambling the index yourself. If speed is the priority, then larger prime bases counter-intuitively perform better than small ones; 0x1337, 0xDE4D, 0x510B and 0xACED are all probable primes (using BigInteger.isProbablePrime(int)) that may do well here for speed but will likely require some basic scrambling of the index order. This method on its own does not perform any scrambling on index other than incrementing it and ensuring it is positive (by discarding the sign bit; for all positive index values other than 0x7FFFFFFF, this has no effect). If you want to quickly scramble an int index i for this purpose, try (i ^ (i << 7 | i >>> 25) ^ (i << 19 | i >>> 13)), which may compile to SSE instructions on recent desktop processors and won't risk losing precision on GWT.
      Uses the same algorithm as determine2(int) when base is 2, which should offer some speed improvement. The other bases use code adapted from Alan Wolfe's blog, which turned out to be a lot faster than the previous way I had it implemented.
      Parameters:
      base - a prime number to use as the base/radix of the van der Corput sequence
      index - the position in the sequence of the requested base, as a non-negative int
      Returns:
      a quasi-random double between 0.0 (inclusive) and 1.0 (exclusive).

    • determine2

      public static double determine2​(int index)
      Convenience method to get a double from the van der Corput sequence with the base 2 at the requested index without needing to construct a VanDerCorputQRNG. This does not perform any scrambling on index other than incrementing it and ensuring it is positive (by discarding the sign bit; for all positive index values other than 0x7FFFFFFF (Integer.MAX_VALUE), this has no effect).
      Because binary manipulation of numbers is easier and more efficient, the technique used by this method is also used by determine(int, int) when base is 2, and should be faster than other bases.
      Parameters:
      index - the position in the base-2 van der Corput sequence, as a non-negative int
      Returns:
      a quasi-random double between 0.0 (inclusive) and 1.0 (exclusive).

    • determine2_scrambled

      public static double determine2_scrambled​(int index)
      Method to get a double from the van der Corput sequence with the base 2 at a scrambling of the requested index without needing to construct a VanDerCorputQRNG. This performs different scrambling on index than the instance methods on this class perform, and it seems to do well enough while being a little simpler. This is meant to be usable as an alternative to a different base for a van der Corput sequence when you need two different sequences, and are already using base 2 via determine2(int).
      Because binary manipulation of numbers is easier and more efficient, this method should be somewhat faster than the alternatives, like determine(int, int) with base 2. It should take only slightly longer to run than determine2(int), due to the brief amount of time needed to scramble the index.
      Parameters:
      index - the position in the sequence of the requested base
      Returns:
      a quasi-random double between 0.0 (inclusive) and 1.0 (exclusive).

    • determineMixed

      public static double determineMixed​(int index)
      Chooses one sequence from the van der Corput sequences with bases 2, 3, and 5, where 5 is used 1/8 of the time, 3 is used 3/8 of the time, and 2 is used 1/2 of the time, and returns a double from the chosen sequence at the specified index. The exact setup used for the choice this makes is potentially fragile, but in certain circumstances this does better than SobolQRNG at avoiding extremely close values (the kind that overlap on actual maps). Speed is not a concern here; this should be very much fast enough for the expected usage in map generation (it's used in GreasedRegion.quasiRandomSeparated(double).
      Parameters:
      index - the index to use from one of the sequences; will also be used to select sequence
      Returns:
      a double from 0.0 (inclusive, but extremely rare) to 1.0 (exclusive); values will tend to spread apart

    • weakDetermine

      public static float weakDetermine​(int index)
      Given any int (0 is allowed), this gets a somewhat-sub-random float from 0.0 (inclusive) to 1.0 (exclusive) using the same implementation as NumberTools.randomFloat(long) but with index alterations. Only "weak" because it lacks the stronger certainty of subsequent numbers being separated that the Van der Corput sequence has. Not actually sub-random, but should be distributed fairly well (internally uses ThrustAltRNG's algorithm, which does not guarantee that its outputs are unique).
      Not all int values for index will produce unique results, since this produces a float and there are less distinct floats between 0.0 and 1.0 than there are all ints (1/512 as many floats in that range as ints, specifically). It should take a while calling this method before you hit an actual collision.
      Parameters:
      index - any int
      Returns:
      a float from 0.0 (inclusive) to 1.0 (exclusive) that should not be closely correlated to index

    • weakSignedDetermine

      public static float weakSignedDetermine​(int index)
      Like weakDetermine(int), but returns a float between -1.0f and 1.0f, exclusive on both. Uses NumberTools.randomSignedFloat(long) internally but alters the index parameter so calls with nearby values for index are less likely to have nearby results.
      Parameters:
      index - any int
      Returns:
      a sub-random float between -1.0f and 1.0f (both exclusive, unlike some other methods)

    • altDetermine

      public static double altDetermine​(long base, int index)
      Similar to determine(int, int), but can take bases that aren't prime and can sometimes produce a Halton-like sequence with almost-as-good distance between points. The base is allowed to be any odd long, (negative bases are allowed). The index can technically also be negative, and if this is given 0 it will not return any specific number (it will vary with the base). This returns a double between 0.0 inclusive and 1.0 exclusive. Better results have been found with larger bases (points tend to be more spread out). It is never as good at spreading out 2D points as a 2,3 Halton sequence, at least for any bases tried so far.
      Earlier versions of this method wound up only producing points on parallel lines in 2D, never placing points in between those lines. This sometimes formed a hex-like grid that, as hexagons do, has optimal packing properties, which made the optimal distance seem very good despite the points having a clear pattern. This can still sometimes be useful; when you want optimal distance and don't have a case where a clear pattern on a grid is an issue, it can have high performance. The code for the old way is small, though not simple: ((base * Integer.reverse(index) << 21) & 0x1fffffffffffffL) * 0x1p-53, where base is an odd long and index is any int. It works best in one dimension.
      Parameters:
      base - any odd long
      index - any int
      Returns:
      a double between 0.0 inclusive and 1.0 exclusive

    • planarDetermine

      public static double planarDetermine​(long base, int index)
      A quasi-random number generator of doubles between 0.0 inclusive and 1.0 exclusive, but that has issues when it would be used like a Halton sequence. Only ideal in 1D, this produces well-separated points that are aligned to parallel hyperplanes when called with different bases and each base used as an axis for more than 1 dimension. This can produce points with more separation in 2D than a Halton sequence can, but not often. Two bases that do this when used together are the ints 0xDE4DBEEF and 0x1337D00D (or in decimal, -565330193 and 322424845; note that 0xDE4DBEEF is a negative integer); they were tried as a gimmick but nothing else turned out better. They do still produce points on parallel lines, and like all bases, never points between those lines.
      Note, the source of this method is one line, and you may see benefits from copying that code into the call-site with minor modifications. This returns (((base * Integer.reverse(index)) << 21) & 0x1fffffffffffffL) * 0x1p-53;, where base is a long and index is an int (as in the method signature). The multiplier 0x1p-53 is a very small hexadecimal double literal, using the same syntax as other parts of SquidLib use for packed floats; using this helps avoid precision loss. If you want a range larger than 0.0 to 1.0, you can change the multiplier 0x1p-53 to some other constant, like declaring final double upTo100 = 0x1p-53 * 100.0 before some code that wants quasi-random numbers between 0.0 inclusive and 100.0 exclusive, then using (((base * Integer.reverse(index)) << 21) & 0x1fffffffffffffL) * upTo100; to get those numbers. It isn't precise to use this technique to get numbers with an upper bound less than 1.0, because 0x1p-53 is about as small as a double can get with precision intact. In that case, you can use (((base * Integer.reverse(index)) << 8) & 0xffffffffffL) * smallBound; where smallBound has been declared as final double smallBound = 0x1p-40 * 0.05; (where 0.05 can be switched out for any double between 1.0/8192.0 and 1.0).
      Parameters:
      base - any odd long; the most significant 21 bits (except the sign bit) are effectively ignored
      index - any int; if 0 this will return 0
      Returns:
      a double between 0.0 inclusive and 1.0 exclusive

    • haltoid

      public static Coord haltoid​(int seed, int width, int height, int xOffset, int yOffset, int index)
      Samples a quasi-random Coord sequence that is almost unique to the given seed, getting a Coord with x between xOffset (inclusive) and width + xOffset (exclusive), y between yOffset (inclusive) and height + yOffset (exclusive). The seed is "almost" unique because even seeds are discouraged; there is an identical sequence for every even seed produced by some odd seed. This generates a not-very random number, reverses its bits as other methods in this class do, then treats that single 32-bit int as two coordinates on a Z-order curve to get separate x and y from them. In practice these Coords are very well-dispersed if only a small amount are sampled and all the index values are close-by, and get closer together as more are sampled. Unlike the Halton sequence, this has very different results with different seeds (Halton only allows bases to be changed), and doesn't involve any division, modulus, conditionals, or loops.
      Parameters:
      seed - an int seed that should be an odd number
      width - the width of the area this can cover
      height - the height of the area this can cover
      xOffset - the lowest x-coordinate this can produce, and also added to width to get the upper bound on x
      yOffset - the lowest y-coordinate this can produce, and also added to height to get the upper bound on y
      index - the index in the sequence, almost always a positive int that increases by 1 with each call
      Returns:
      a Coord between (xOffset, yOffset) inclusive and (width+xOffset, height+yOffset) exclusive

    • roberts

      public static int roberts​(int span, int offset, int index)
      Martin Roberts' "unreasonably effective" quasi-random int sequence based on the golden ratio. See his blog for more detailed info, but this can be summarized as being extremely good at separating outputs at the expense of seeming less random. Produces an int between offset (inclusive) and offset + span (exclusive), with the int at each index likely to be different for at least span / 4 indices (very low spans may offer less of a guarantee).
      Note, use roberts(int, int, int, int, int) for 2D points and this method for 1D values; the same properties won't be preserved if you use a 1D Roberts sequence in 2D.
      Parameters:
      span - the size of the range this can return
      offset - the minimum value this can return
      index - the index of the int in the 1D Roberts sequence; should be greater than 0, but not required to be
      Returns:
      an int between offset inclusive and offset+span exclusive

    • roberts

      public static Coord roberts​(int width, int height, int xOffset, int yOffset, int index)
      Martin Roberts' "unreasonably effective" quasi-random point sequence based on a 2D analogue to the golden ratio. See his blog for more detailed info, but this can be summarized as being extremely good at separating points at the expense of seeming less random. Produces a Coord with x between xOffset (inclusive) and xOffset + width (exclusive), and y between yOffset (inclusive) and yOffset + height (exclusive), with the Coord at each index likely to be different for at least width * height / 4 indices (very low sizes may offer less of a guarantee).
      Parameters:
      width - the x-size of the space this can place a Coord
      height - the y-size of the space this can place a Coord
      xOffset - the minimum x-position of a Coord
      yOffset - the minimum y-position of a Coord
      index - the index of the Coord in the 2D Roberts sequence; should be greater than 0, but not required to be
      Returns:
      a Coord with x,y between xOffset,yOffset inclusive and xOffset+width,yOffset+height exclusive