Algorithm - 2023.2 English

Vitis Libraries

Release Date
2023.2 English

The basic element of Mersenne Twister (MT) Algorithm is vector, a \(w\) bits unsigned integer. The MT Algorithm generates a sequence of vectors, which are considered to be uniform distributed in \((0, 2^w - 1)\). These vectors could be mapped to (0,1) after dividing by \(2^w\).

The basic algorithm is composed of two parts. First part is an iterative formula as shown below:

\[X_{k + n} = X_{k + m} \bigoplus (X_{k}^u|X_{k+1}^l)A\]
Diagram of MCEuropeanHestonEngine

Where \(X_{k + n}\) denotes the \(k\), \(X_1\),…, \(X_{n - 1}\) as initial vectors. \(X_{k}^u\) means the upper \(w - r\) bits of \(X_{k}\), \(X_{k + 1}^u\) means the lower \(r\) bits of \(X_{k + 1}\). \((X_{k}^u|X_{k+1}^l)\) is just combination of upper \(w - r\) bits of \(X_{k}\) and lower \(r\) bits of \(X_{k + 1}\). \(\bigoplus\) is bitwise addition. The multiplication of \(A\) could be done by bits operations:

\[XA = shiftright(X) \:\:\: if X[0] = 0\]
\[XA = shiftright(X)\bigoplus a \:\:\: if X[0] = 1\]

Where \(a\) is a constant vector.

The second part is tempering, which consists of four steps below.

\[Y = X \bigoplus (X >> u)\]
\[Y = Y \bigoplus ((Y << s) \:\: AND \:\: b )\]
\[Y = Y \bigoplus ((Y << t) \:\: AND \:\: c )\]
\[Z = Y \bigoplus (Y >> l)\]

Where \(u\), \(s\), \(t\), and \(l\) are constant parameters indicate shift length, \(b\) and \(c\) are two const vectors.

A combination of \(w\), \(n\), \(r\), \(m\), \(u\), \(s\), \(t\), \(l\), \(a\), \(b\), \(c\) determines a variation of Mersenne Twister. Only a limited combination could work.