squidpony.squidmath.TangleRNG

All Implemented Interfaces:: Serializable, RandomnessSource, SkippingRandomness

public final class TangleRNG
extends Object
implements RandomnessSource, SkippingRandomness, Serializable

A very fast generator on 64-bit systems that allows choosing any of 2 to the 63 odd-number streams. Each stream changes the set of possible outputs this can produce (amending the main flaw of ThrustAltRNG). This does well in PractRand quality tests, passing 32TB with one minor anomaly (it shares a lot of structure with ThrustAltRNG, which does very well in PractRand's testing as well as TestU01's BigCrush). It also outperforms just about everything in BumbleBench benchmarks, making it arguably the fastest random number generator algorithm here that can produce all long values (it just needs multiple generator objects to do so, all seeded differently).
Because this can produce multiple occurrences of any number in its sequence (except 0, which it should always produce once over its period of 2 to the 64), it can be considered as passing the "birthday problem" test; after running this test provided by Melissa E. O'Neill on Tangle, it correctly has 9 repeats compared to an expected 10, using the Skipping adapter to check one out of every 65536 outputs for duplicates. A generator that failed that test would have 0 repeats or more than 20, so Tangle passes. ThrustAltRNG probably also passes (or its structure allows it to potentially do so), but LightRNG, LinnormRNG, MizuchiRNG, and even ThrustRNG will fail it by never repeating an output. Truncating the output bits of any of these generators will allow them to pass this test, at the cost of reducing the size of the output to an int instead of a long (less than ideal). Notably, an individual Tangle generator tends to be able to produce about 2/3 of all possible long outputs, with roughly 1/3 of all outputs not possible to produce and another 1/3 produced exactly once. These are approximations and will vary between instances. The test that gave the "roughly 2/3 possible" result gave similar results with 8-bit stateA and stateB and with 16-bit stateA and stateB, though it could change with the 64-bit states Tangle actually uses.
The name "Tangle" comes from how the two states of this generator are "tied up in each other," with synchronized periods of 2 to the 64 (stateA) and 2 to the 63 (stateB) that repeat as a whole every 2 to the 64 outputs. Contrary to the name, Tangle isn't slowed down at all by this, but the period length of the generator is less than the maximum possible (which OrbitRNG has, though that one is slowed down).
See also OrbitRNG, which gives up more speed but moves through all 2 to the 64 long values as streams over its full period, which is 2 to the 128 (with one stream) instead of the 2 to the 64 (with 2 to the 63 streams) here. There's also SilkRNG, which is like OrbitRNG but uses 32-bit math and is GWT-optimized.
This added a small extra step to the generation on March 4, 2020; the extra step reduces correlation between streams by further randomizing the output. Without this step (an additional right-xorshift by 6), nearby stateA or stateB values would often produce visibly similar sequences; with the step they are much less similar and more random. The additional step slows down TangleRNG by a very small amount. This edit also added getStream(), which may have a use somewhere (maybe diagnosing possible problems?).
Created by Tommy Ettinger on 7/9/2018.

See Also:: Serialized Form

Constructor Summary

Constructors

Constructor Description

TangleRNG()
Creates a new generator seeded using Math.random.

TangleRNG(long seed)

TangleRNG(long seedA, long seedB)

Method Summary

Modifier and Type	Method	Description
`TangleRNG`	`copy()`	Produces a copy of this RandomnessSource 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.
`boolean`	`equals(Object o)`
`long`	`getStateA()`	Get the "A" part of the internal state as a long.
`long`	`getStateB()`	Get the "B" part of the internal state as a long.
`long`	`getStream()`	Gets a long that identifies which stream of numbers this generator is producing; this stream identifier is always an odd long and won't change by generating numbers.
`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.
`long`	`nextLong()`	Using this method, any algorithm that needs to efficiently generate more than 32 bits of random data can interface with this randomness source.
`void`	`setStateA(long stateA)`	Set the "A" part of the internal state with a long.
`void`	`setStateB(long stateB)`	Set the "B" part of the internal state with a long; the least significant bit is ignored (will always be odd).
`long`	`skip(long advance)`	Advances or rolls back the SkippingRandomness' state without actually generating each number.
`String`	`toString()`

Methods inherited from class java.lang.Object

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

Constructor Details
- TangleRNG
  
  public TangleRNG()
  
  Creates a new generator seeded using Math.random.
- TangleRNG
  
  public TangleRNG(long seed)
- TangleRNG
  
  public TangleRNG(long seedA, long seedB)
Method Details
- getStateA
  
  public long getStateA()
  
  Get the "A" part of the internal state as a long.
  
  Returns:
  
  the current internal "A" state of this object.
- setStateA
  
  public void setStateA(long stateA)
  
  Set the "A" part of the internal state with a long.
  
  Parameters:
  
  stateA - a 64-bit long
- getStateB
  
  public long getStateB()
  
  Get the "B" part of the internal state as a long.
  
  Returns:
  
  the current internal "B" state of this object.
- setStateB
  
  public void setStateB(long stateB)
  
  Set the "B" part of the internal state with a long; the least significant bit is ignored (will always be odd).
  
  Parameters:
  
  stateB - a 64-bit long
- next
  
  public final int next(int bits)
  
  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
- nextLong
  
  public final long nextLong()
  
  Using this method, any algorithm that needs to efficiently generate more than 32 bits of random data can interface with this randomness source.
  Get a random long between Long.MIN_VALUE and Long.MAX_VALUE (both inclusive).
  
  Specified by:
  
  nextLong in interface RandomnessSource
  
  Returns:
  
  a random long between Long.MIN_VALUE and Long.MAX_VALUE (both inclusive)
- copy
  
  public TangleRNG copy()
  
  Produces a copy of this RandomnessSource 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 need 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
  
  Returns:
  
  a copy of this RandomnessSource
- 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
- skip
  
  public long skip(long advance)
  
  Advances or rolls back the SkippingRandomness' state without actually generating each number. Skips forward or backward a number of steps specified by advance, where a step is equal to one call to nextLong(), and returns the random number produced at that step. Negative numbers can be used to step backward, or 0 can be given to get the most-recently-generated long from nextLong().
  
  Specified by:
  
  skip in interface SkippingRandomness
  
  Parameters:
  
  advance - Number of future generations to skip over; can be negative to backtrack, 0 gets the most-recently-generated number
  
  Returns:
  
  the random long generated after skipping forward or backwards by advance numbers
- getStream
  
  public long getStream()
  
  Gets a long that identifies which stream of numbers this generator is producing; this stream identifier is always an odd long and won't change by generating numbers. It is determined at construction and will usually (not always) change if setStateA(long) or setStateB(long) are called. Each stream is a probably-unique sequence of 2 to the 64 longs, where approximately 1/3 of all possible longs will not ever occur (while others occur twice or more), but this set of results is different for every stream. There are 2 to the 63 possible streams, one for every odd long.
  
  Returns:
  
  an odd long that identifies which stream this TangleRNG is generating from

Constructor	Description
`TangleRNG()`	Creates a new generator seeded using Math.random.
`TangleRNG(long seed)`
`TangleRNG(long seedA, long seedB)`

Class TangleRNG

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Details

Method Details