Помогите пожалуйста разобраться с методом генерации ДСЧ Фибоначчи или иначе его называют Метод Фибоначчи с запаздываниями. Честно говоря информации по данному методу в интернете найти практически не удалось, везде так или иначе цитируют материал из википедии(или наоборот). Там указано две непонятных формулы, непонятных в том смысле что непонятно что они должны делать и главное как) Так что прошу тех, кому известен такой метод не по наслышке рассказать о нем по подробнее, буду очень признателен)
Ну, почему же только из Википедии? Не только. По крайней мере, на английском языке есть достаточно информации. Начиная http://sprng.fsu.edu/Version4.0/generators.html . Там есть описания Multiplicative Lagged Fibonacci Generator и Modified Lagged Fibonacci Generator со ссылками на детальные разборы алгоритмов. Правда, ссылки битые, но по названию статей гуглится на раз-два: http://docs.google.com/viewer?a=v&q=cache:HyfJoGJWezYJ:citeseerx.ist.psu.edu/viewdoc/download%3Fdoi%3D10.1.1.48.177%26rep%3Drep1%26type%3Dpdf+parallel+Lagged-Fibonacci+pseudorandom+number+generator&hl=ru&pid=bl&srcid=ADGEESiN5Fa9J8pWXFU6dWZyr4I8OYdQne-4zayHcXLvN7baxVBxWMN7Xexsdl1I1Rux0ScQBFuM4u4SUGFvdGl3ZGmYp-F35lqJFcNw4976SglsJan5n_c0RgndIGPEoZAxl7HG0t5M&sig=AHIEtbS9IhhbHAcnr9UWM_CT1C-tkRLb7g
> Там указано две непонятных формулы, непонятных в том смысле что непонятно что они должны делать и главное как)
На самом деле формула одна:
a[i] = frac(a[i-97]-a[i-33]);
То есть простой ряд Фибоначчи, но берётся только дробная часть.
> При реализации через целые числа достаточно формулы Xk = X[k − a] − X[k − b] (при этом будут происходить арифметические переполнения).
(это моя правка, кстати)
Для реализации на компе надо вместо бесконечной последовательности взять конечную, но циклическую.
{$R-}
const
FibCount = 1 shl 7;
a = 97;
b = 33;
var
N: integer;
Fibs: array [0 .. FibCount - 1] of cardinal;
function Random: cardinal;
begin
Fibs[N] := Fibs[(N - a) and (FibCount - 1)] - Fibs[(N - b) and (FibCount - 1)]
Result := Fibs[N];
N := (N + 1) and (FibCount - 1);
end;
procedure Randomize;
var
i: integer;
begin
Fibs[0] := GetTickCount;
for i := 1 to FibCount - 1 do
Fibs[i] := Fibs[i - 1] * 1664525 + 1013904223;
end;