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:

$S_{n}=S_{n-1}+S_{n-2}$

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:

$S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},0<j<k$

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^M), thường lấy giá trị 2³² hoặc 2⁶⁴. Phép toán $\star$ 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 từng bit (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 j và 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^k − 1)×2^M-1 nếu phép cộng hoặc phép trừ được dùng, và (2^k − 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^k − 1) × 2^M−3, 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^k + x^j + 1

phải là đ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.

Các cặp bộ đa thức nguyên thủy

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ẻ.

Hiện ta đang đoán rằng tỷ lệ giữa j và k có liên hệ gần với tỷ lệ vàng.

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. 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 đó ta thường có tương quan ba điểm giữa $x_{n}$, $x_{n-a}$, và $x_{n-b}$, theo tên của chính bộ sinh đó... Mặc dù tương quan được phân phối trên $p=max(a,b,c,\ldots )$ của chính bộ sinh, chúng vẫn có thể dẫn tới các lỗi nghiêm trọng". 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ư khoảng cách sinh nhật và kiểm tra bộ ba tổng quát.

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. 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
• Bộ sinh ACORN
• Mersenne Twister
• Xoroshiro128+
• FISH (mã hóa)
• Pike
• Mã hóa VIC

Tham khảo

Toward a universal random number generator, G.Marsaglia, A.Zaman