Phương pháp đồng dư tuyến tính (cont)
Giá trị khởi động bấts kỳ nào cũng có thể sử dụng được trong việc tạo các số ngẫu nhiên mà không có ảnh hưởng gì đặc biết (dĩ nhiên là ngoại trừ việc giá trị khởi động khác nhau thì tạo thành các chuỗi ngẫu nhiên khác nhau). Thườngthif không cần phải lưu tữ cả chuỗi như chương trình nêu trên. Ngược lại chúng ta đơn giản giữ lại trong một biến toàn cục a, khởi động với một giá trị nào đó, rồi cập nhật bằng phép tính a := (a*b + 1) mod m.
Trong Pascal (và nhiều ngôn ngữ lập trình khác), chúng ta còn một bước nữa mới có thể thực hiện được, bởi vì chúng ta không được phép bỏ qua tình trạng trành : nó được định nghĩa là một trường hợp lỗi mà có thể tạo ra các kết quả không dự đoán được. Giả sử rằng máy vi tính của chúng ta có
word 32 bit, và chúng ta chọn
m = 100000000, b = 31415821, và khởi động
a = 1234567. Tất cả các giá trị này đều nhỏ hơn giá trị tối đa của một số nguyên, nhưng phép toán đầu tiên a*b + 1 đã làm tràn. Phần của kết quả đã gây ra sự tràn là thì không có quan hệ với sự tính toán của chúng ta bởi vì chúng ta chỉ quân tâm đến 8 ký số sau. Một thủ thuật để loại bỏ sự trành là phân nhỏ phép nhân ra làm nhiều phần. Để nhân p và q chúng ta viết
p = 10^4 * p1 + p0 và q = 10^4 * q1 + q0
Do đó kết quả là :
pq = (10^4 * p1 + p0)(10^4 * q1 + q0) = 10^8 * p1q1 + 10^4(p1q0 + p0q1) + p0q0
Bây giờ chúng ta chỉ muốn 8 ký số cho kết quả, vì thế chúng ta có thể bỏ qua số hạng đâu tiên (10^8 * p1q1) và bỏ qua 4 ký số đầu của số hạng thứ 2 (10^4(p1q0 + p0q1)) Điều này dẫn đến chương trình ở trang sau.
Hàm mult trong chương trình này tính
(p*q mod m), không bị trành kh m nhỏ hơn 1/2 giá trị số nguyên tối đa. Kỹ thuật này hiển nhiên có thể đáp ứng với các giá trị m1 khác theo nguyên tắc
m = m1 + m1.
Mã:
Program random (input, output);;
const m = 100000000; m1 = 10000; b = 3141581;
var i, a, N:integer;
function mult(p,q:integer):integer;
var p1,p0,q1,q0 : integer;
begin
p1 := p div m1; p0 = p mod m1;
q1 := q div m1; q0 = q mod m1;
mult := (((p0*q1 + p1*q0) mod m1) * m1 + p0*q0) mod m;
end;
function random:integer;
begin
a := (mult(a,b) + 1) mod m;
random := a;
end;
begin
readln(N,a);
for i:=1 to N do writeln(random);
end.
Khi chạy chương trình với dữ liệu nhập N = 10 và q = 1234567, chương trình tạo được 10 số như sau : 35884508, 80001069, 63512650, 43635651, 1034472, 87181513, 6917174, 209855, 67115956, 59939877. Trong các số này, có vài sự không ngẫu nhiên: ví dụ, các ký số sau cùng (hàng đơn vị) xoay vòng qua các số từ 0 đến 9. Dễ dàng chứng minh được điều này sẽ xảy ra từ công thức. Nói chung các ký số bên phải không thật sự ngẫu nhiên, thực tế đó là nguồn gốc của các lỗi thông thường và quan trọng trong việc sử dụng phương pháp tạo số ngẫu nhiên đồng dư tuyến tính.
(to be cont.)
lấy công rẻ thôi