Xem mã nguồn của Bộ sinh Fibonacci trễ

'''Bộ sinh Fibonacci trễ''' (''tiếng anh: Lagged Fibonacci Generator'', hay gọi tắt đi là '''LFG''' hoặc đôi khi là '''LFib''') là ví dụ của [[bộ sinh số giả ngẫu nhiên]]. Lớp các [[bộ sinh số giả ngẫu nhiên]] dựa trên dạng tổng quát của [[dãy Fibonacci]].

Dãy fibonacci được mô tả theo [[liên hệ lặp lại]] sau:

:<math>S_n = S_{n-1} + S_{n-2}</math>

Trong đó mỗi phần tử mới là tổng của hai phần tử cuối trong dãy. Ta tổng quát công thức trên thành như sau:

:<math>S_n \equiv S_{n-j} \star S_{n-k}  \pmod{m},   0 < j < k</math>

Trong đó, trong đó phần tử mới là hợp của hai phần tử trước đó trong dãy. Giá trị ''m'' thường là lũy thừa của 2 (''m'' = 2<sup>''M''</sup>), thường lấy giá trị 2<sup>32</sup> hoặc 2<sup>64</sup>. Phép toán <math>\star</math> ký hiệu [[phép toán hai ngôi]] nói chung. Phép toán này có thể là phép cộng, phép trừ, phép nhân hoặc [[Phép toán thao tác bit|phép toán thao tác từng bit]] ([[phép XOR|XOR]]). Lý thuyết của các bộ sinh số này có thể rất phức tạp và không chỉ đơn giản là chọn bừa các giá trị cho {{var|j}} và {{var|k}}. Các bộ sinh số ngẫu nhiên này cũng rất nhạy cảm với các giá trị và phép toán khởi tạo.

Các bộ sinh số giả ngẫu nhiên dạng này sẽ lưu ''k'' trạng thái (tức là nó có thể nhớ ''k'' giá trị cuối'').

Nếu phép toán được dùng là phép cộng, thì bộ sinh được gọi là ''Bộ sinh Fibonacci trễ cộng tính'' hoặc ALFG, nếu phép nhân được dùng thì nó được gọi là, ''Bộ sinh Fibonacci trễ nhân tính'' hoặc MLFG, còn nếu phép XOR được dùng thì bộ sinh được gọi là ''[[thanh ghi dịch phản hồi tổng quát]] hai số'' hoặc GFSR. Thuật toán [[Mersenne Twister]] là dạng khác của GFSR.  GFSR thường liên hệ với [[thanh ghi dịch phản hồi tuyến tính]], hoặc LFSR.

== Các tính chất của bộ sinh Fibonacci trễ ==
'''Bộ sinh Fibonacci trễ''' có chu kỳ cực đại (2<sup>''k''</sup> − 1)×2<sup>''M''-1</sup> nếu phép cộng hoặc phép trừ được dùng, và (2<sup>''k''</sup> − 1) × ''k'' nếu phép XOR được dùng để làm phép toán. Mặc khác, nếu phép nhân được dùng thì bộ sinh có chu kỳ cực đại là (2<sup>''k''</sup> − 1) × 2<sup>M−3</sup>, hoặc 1/4 của trường hợp phép cộng.

Để các bộ sinh có chu kỳ cực đại thì đa thức sau:

:''y'' = ''x''<sup>''k''</sup> + ''x''<sup>''j''</sup> + 1

phải là [[đa thức nguyên thủy (lý thuyết trường)|đa thức nguyên thủy]] trên các số nguyên dư 2. Một số cặp giá trị của j và k thỏa mãn điều kiện này nằm trong bảng sau. 
{| class="wikitable"
|+ Các cặp bộ đa thức nguyên thủy<ref>{{chú thích web |url=http://www.ccs.uky.edu/csep/RN/RN.html |title=RN Chapter |website=www.ccs.uky.edu |access-date=ngày 13 tháng 1 năm 2022 |archive-url=https://web.archive.org/web/20040309175607/http://www.ccs.uky.edu/csep/RN/RN.html |archive-date=ngày 9 tháng 3 năm 2004 |url-status=dead}}</ref><ref>{{chú thích web |url=http://www.nersc.gov/nusers/resources/software/libs/math/random/www2.0/DOCS/www/parameters.html |title=SPRNG: Scalable Parallel Pseudo-Random Number Generator Library |access-date = ngày 11 tháng 4 năm 2005 |archive-date = ngày 14 tháng 6 năm 2010 |archive-url=https://web.archive.org/web/20100614213822/http://www.nersc.gov/nusers/resources/software/libs/math/random/www2.0/DOCS/www/parameters.html |url-status=dead }}</ref>
|-
| ''j''||  7 ||  5 || 24 || 65 || 128 ||  6 || 31 ||  97 || 353 || 168 || 334 || 273 || 418
|-
| ''k''|| 10 || 17 || 55 || 71 || 159 || 31 || 63 || 127 || 521 || 521 || 607 || 607 || 1279
|-
|}

Danh sách khác cho các giá trị ''j'' và ''k'' nằm trong trang 29 cuốn thứ hai 2 trong ''[[The Art of Computer Programming]]'':

:(24, 55), (38, 89), (37, 100), (30, 127), (83, 258), (107, 378), (273, 607), (1029, 2281), (576, 3217), (4187, 9689), (7083, 19937), (9739, 23209)

Nếu phép cộng được dùng, thì thường yêu cầu ít nhất một giá trị trong ''k'' giá trị được chọn để khởi tạo bộ sinh là lẻ; nếu phép nhân được dùng thì toàn bộ ''k'' giá trị đầu tiên đều phải lẻ.<ref>[http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators] {{Webarchive|url=https://web.archive.org/web/20180721222733/http://www.cs.fsu.edu/~asriniva/papers/mlfg.ps |date=2018-07-21 }}, M.Mascagni, A.Srinivasan</ref>

Hiện ta đang đoán rằng tỷ lệ giữa {{var|j}} và {{var|k}} có liên hệ gần với [[tỷ lệ vàng]].<ref name="uniform">[https://openresearch-repository.anu.edu.au/bitstream/1885/40805/3/TR-CS-92-02.pdf "Uniform random number generators for supercomputers"], Richard Brent, 1992</ref>

== Các khuyết điểm của LFG ==
Trong các bài viết về thanh ghi dịch, [[Robert M. Ziff]] có nói đến các bộ sinh Fibonacci trễ dùng phép toán XOR, phát biểu rằng "Các bộ sinh số ngẫu nhiên này, đặc biệt là các bộ sinh dùng hai số như R(103, 250), có một số khuyết điểm lớn.  [[George Marsaglia|Marsaglia]] đã quan sát thống kê của R(24, 55) và các bộ sinh nhỏ hơn, khuyên không nên dùng các bộ sinh dạng này.  ... Vấn đề cơ bản của các bộ sinh R(a, b) là trong đó thường có tương quan ba điểm giữa <math>x_{n}</math>, <math>x_{n-a}</math>, và <math>x_{n-b}</math> được sinh bởi chính bộ sinh đó... Mặc dù tương quan được phân phối trên khoảng <math>p = max(a, b, c, \ldots)</math> của chính bộ sinh, chúng vẫn có thể dẫn tới các lỗi nghiêm trọng".<ref>[https://arxiv.org/abs/cond-mat/9710104 "Four-tap shift-register-sequence random-number generators"], Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392</ref> Song, bài viết chỉ nhắc đến các LFG chuẩn trong đó mỗi số dựa trên hai số trước đó. Các LFG dùng ba số đã giải quyết được một số vấn đề thống kê như [[kiểm tra Diehard test|khoảng cách sinh nhật]] và kiểm tra bộ ba tổng quát.<ref name="uniform" />

Việc khởi tạo các bộ LFG cũng là vấn đề phức tạp. Đầu ra của LFG rất nhạy với các giá trị khởi tạo, và các lỗi thống kê không chỉ có thể xuất hiện 1 lần mà còn theo có thể xuất hiện theo chu kỳ trong dãy đầu ra, do đó yêu cầu cần phải được xử lý rất cẩn thận.{{citation needed|date=June 2008}} Một vấn đề khác của LFG là lý thuyết toán học đứng đằng sau bộ sinh vẫn còn chưa được hoàn thiện, do đó hiện tại ta buộc phải dựa trên kiểm tra thống kê thay vì kiểm tra lý thuyết.

== Sử dụng ==
* [[Freeciv]] sử dụng bộ sinh Fibonacci trễ với {j = 24, k = 55} cho sinh số ngẫu nhiên.
* [[Thư viện Boost]] có bao gồm bộ sinh Fibonacci trễ.
* [[Trừ cùng nhớ]], bộ sinh này được cài trong thư viện của [[C++11]].
* [[Cơ sở dữ liệu Oracle]] cài bộ sinh này trong gói DBMS_RANDOM (có trong Oracle 8 và các bản mới hơn).

== Xem thêm ==
* [[Bộ sinh đồng dư tuyến tính]]
* [[ACORN (PRNG)|Bộ sinh ACORN]]
* [[Mersenne Twister]]
* [[Xoroshiro128+]]
* [[FISH (mã hóa)]]
* [[Pike (mã hóa)|Pike]]
* [[Mã hóa VIC]]

== Tham khảo ==
:[https://web.archive.org/web/20100610050921/http://stat.fsu.edu/techreports/M766.pdf Toward a universal random number generator], G.Marsaglia, A.Zaman
{{tham khảo}}

{{DEFAULTSORT:Lagged Fibonacci Generator}}
[[Thể loại:Bộ sinh số giả ngẫu nhiên]]
[[Thể loại:Số Fibonacci]]