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:

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:

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 = 2M), thường lấy giá trị 232 hoặc 264. Phép toán 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 jk. 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ễ

sửa

Bộ sinh Fibonacci trễ có chu kỳ cực đại (2k − 1)×2M-1 nếu phép cộng hoặc phép trừ được dùng, và (2k − 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à (2k − 1) × 2M−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 = xk + xj + 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[1][2]
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ị jk 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ẻ.[3]

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

Các khuyết điểm của LFG

sửa

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  ,  , và  , theo tên của chính bộ sinh đó... Mặc dù tương quan được phân phối trên   của chính bộ sinh, chúng vẫn có thể dẫn tới các lỗi nghiêm trọng".[5] 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.[4]

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.[cần dẫn nguồ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

sửa

Xem thêm

sửa

Tham khảo

sửa
Toward a universal random number generator, G.Marsaglia, A.Zaman
  1. ^ “RN Chapter”. www.ccs.uky.edu. Bản gốc lưu trữ ngày 9 tháng 3 năm 2004. Truy cập ngày 13 tháng 1 năm 2022.
  2. ^ “SPRNG: Scalable Parallel Pseudo-Random Number Generator Library”. Bản gốc lưu trữ ngày 14 tháng 6 năm 2010. Truy cập ngày 11 tháng 4 năm 2005.
  3. ^ Parameterizing Parallel Multiplicative Lagged-Fibonacci Generators, M.Mascagni, A.Srinivasan
  4. ^ a b "Uniform random number generators for supercomputers", Richard Brent, 1992
  5. ^ "Four-tap shift-register-sequence random-number generators", Robert M. Ziff, Computers in Physics, 12(4), Jul/Aug 1998, pp. 385–392