Top Qs
Timeline
Chat
Perspective
Subtract with carry
Pseudorandom number generator algorithm From Wikipedia, the free encyclopedia
Remove ads
Subtract-with-carry (SWC) is a pseudorandom number generator created by George Marsaglia and Arif Zaman in 1991.[1] It falls into a class of generators known as lagged Fibonacci generators, where each new number in the sequence is a function of two previous numbers at fixed distances ("lags").
![]() | This article may be too technical for most readers to understand. (July 2013) |
SWC is one of three random number generator engines included in the standard C++11 library.[2] It belongs to a family of generators that also includes add-with-carry and subtract-with-borrow engines.[1]
Remove ads
Algorithm
Summarize
Perspective
The subtract-with-carry algorithm's state is defined by a list of R numbers and a "carry" value, where R is the "long lag". The initial values for this state, known as the "seed," can be chosen arbitrarily.
To generate the next number in the sequence, the algorithm uses two values from its state list: the value at the "short lag" position (S steps ago) and the value at the "long lag" position (R steps ago). The new number is calculated by subtracting the long-lag value and the current carry bit from the short-lag value.[3]
If this subtraction results in a negative number (a "borrow"), the result is adjusted by adding a large constant M (the modulus), and the carry for the next step is set to 1. Otherwise, the carry is set to 0. The newly generated number replaces the oldest number in the list, and the process repeats.
Example
A simple example can illustrate the process. Let the parameters be:
- Modulus M = 10
- Long lag R = 3
- Short lag S = 1
- Initial state (seed): a list of 3 numbers and an initial carry .
To generate the next number, :
- Identify the short-lag value and the long-lag value .
- Perform the subtraction: → .
- Since the result is negative, a borrow occurs. The new carry becomes 1.
- The new number is the result modulo M: .
- The state is updated. The list becomes , and the carry is now 1 for the next step.
This process can be repeated to generate a long sequence of pseudorandom numbers.
Formal definition
The sequence generated by the subtract-with-carry engine is described by the recurrence relation:
where the new carry, , is defined as:
The lags must satisfy the condition . The modulus M is typically a power of 2, such as , where W is the word size of the state sequence in bits.[1]
Remove ads
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads