Вычитание с переносом

Вычитание с переносом — это генератор псевдослучайных чисел : один из многих алгоритмов, предназначенных для создания длинной серии случайных чисел на основе небольшого количества исходных данных. Это тип Фибоначчи с запаздыванием, предложенный Джорджем Марсальей и Арифом Заманом в 1991 году. «Лагированный Фибоначчи» относится к тому факту, что каждое случайное число является функцией двух предыдущих чисел с некоторыми заданными фиксированными смещениями или «лагами».

Алгоритм

Последовательность, сгенерированная механизмом вычитания с переносом, может быть описана рекуррентным соотношением :

$x(i)=(x(i-S)-x(i-R)-cy(i-1))\ {\bmod {\ }}M$

где $cy(i)={\begin{cases}1,&{\text{if }}x(i-S)-x(i-R)-cy(i-1)<0\\0,&{\text{otherwise}}\end{cases}}$.

Константы S и R известны как короткие и длинные задержки соответственно. Следовательно, выражения $x(i-S)$ и $x(i-R)$ соответствуют S -му и R -му предыдущим членам последовательности. S и R удовлетворяют условию $0<S<R$. Модуль M имеет значение $M=2^{W}$, где W — размер слова последовательности состояний в битах, а $W>0$.

Двигатель вычитания с переносом является одним из семейства генераторов, которое включает в себя механизмы сложения с переносом и вычитания с заимствованием .

Это один из трех механизмов генератора случайных чисел, включенных в стандартную библиотеку C++11 .