BK Technical E-magazine!

Internet là một kho kiến thức khổng lồ của nhân loại. Tuy nhiên không dễ gì tìm ra các kiến thức bạn cần trong cái kho đó.
TB lập ra topic này với mục đích là nơi để chúng ta sưu tầm các kiến thức khoa học kỹ thuật bổ ích trên Internet, dịch rồi post vào đây để mọi người cùng đọc ( tất nhiên không phải tiếng Việt-nếu tiếng Việt chỉ cần đưa link ). Nếu ai tự viết bài được thì càng hay. Chúng ta sẽ post lên đây các bài viết về khoa học kỹ thuật(Bách Khoa mà).
Sinh viên chúng ta chắc chắn từng sục sạo trên Internet để tìm các tài liệu phục vụ cho học tập. Khi chúng ta tìm được tài liệu hay, xin hãy sưu tầm lại để mọi người cùng đọc.
Mọi người thấy thế nào?


Welcome to VietVoice Entertainment:
http://www.vietvoice.net

Đồng ý hai tay, chú TieuBao mở hàng đi nào!

Monash university
Lecture 33. Random Number Generators
John Stillwell
One of the commonest applications of congruences is to generate "random" numbers for computer simulations of random processes.
Typically, a "seed" is used to generate a sequence of numbers by repeated substitution in a formula
xi = axi ^' 1 + c mod m
(We write n mod m for the remainder when n is divided by m. There is no harm in confusing this with n (mod m), because if q = n mod m then q * n (mod m).)
Such a formula is called a congruential pseudorandom number generator.
33.1 An actual example
xi = 4253261xi ^' 1 + 372837 mod 2 24 was used in an early version of BASIC. Any value of x0 gives an apparently random sequence.
E.g. x0 = 0 generates
0
372837
7765190
4398067
11413782
15605681
6176418
2364191
13454008
15104445
16260158
8774411
Of course, the sequence is not really random. Since all xi , are < 2 24 eventually a value will be repeated, after which the sequence between the repeated values will repeat
endlessly.
In fact, it is conceivable that the sequence repeats after a few more steps, in which case it is far from random.
33.2 A desirable property
If we are using xi = axi ^' 1 + c mod m it
is desirable that the sequence generated by 0 include all the numbers 0; 1; 2; : : :;m ^' 1.
This implies that repetition does not occur for the longest possible time (namely, m steps), and also that any number (mod m) leads to a cycle m steps long, since any number belongs to the sequence generated by 0, which repeats, and hence can be started anywhere.In particular, there are no "bad seeds" - numbers that lead to short cycles.
Example. xi = 3x i ^' 1+ 2 mod 17
x0 = 0 generates all the numbers except 16: 0; 2; 8; 9; 12; 4; 14; 10; 15; 13; 7; 6; 3; 11; 1; 5; 0; : : : 16 is a "bad seed" because 3 * 16 + 2 mod 17 = 50 mod 17 = 16; hence it generates the sequence 16; 16; 16; : : :.
33.3 Causes of short cycles
To see what may be necessary to generate all
numbers < m, we consider more examples.
Example. xi = 3x i ^' 1+ 1 0 mod 16
x0 generates 0; 10; 8; 2; 0; : : :, after which the sequence 0; 10; 8; 2 repeats endlessly. Hence
x0 = 0 generates only four numbers < 16.
Được babystar sửa chữa / chuyển vào 02:00 ngày 24/01/2003
Được babystar sửa chữa / chuyển vào 02:09 ngày 24/01/2003

This is a particular case of the following result.
If gcd(c; m) =d, thenddivides all numbers generated by 0.
This follows by induction on i.
Base step. x1 = a * 0 +c mod m =c mod m, which is divisible by d since c and m are.
Induction step. If x i ^' 1 is divisible by d, so is ax i ^' 1 + c (since x i ^' 1 and c are), and hence so is
xi = ax i ^' 1 + c mod m
(since d divides m, and doing a "mod m" means subtracting some multiple of m, hence some multiple of d).
Example. xi = 2x i ^' 1+ 1 mod 16
x0 = 0 generates 0; 1; 3; 7; 15; 15; 15; : : :Here
the repeating sequence begins after four steps, and has only a single term (15). Five numbers are in the sequence generated by 0, four numbers are in the sequence generated
by 1, etc.
This is due to the following result. If a prime p divides both a and m (i.e. if gcd(a; m) > 1), then all numbers generated
by c are * c (mod p).
Again we use induction on i.
Base step. x0 = c * c (mod m).
Induction step. If x i ^' 1 c (mod p), then
ax i ^' 1 + c * 0 +c * c(mod p);
since a * 0 (modp), hence we also have
xi = ax i ^' 1 + c mod m * c (mod p);
since doing "mod m" means subtracting some multiple of m, hence subtracting somemultiple of p.
33.4 Necessary and suffcient con***ions for long cycles
It follows from the two results above that if ax i ^' 1 +c mod m generates all numbers < m then we necessarily have
gcd(c; m) =1,
gcd(a; m) =1.
However, these con***ions are not suffcient.
Example. xi = 3x i ^' 1+ 5mod16
x0 = 0 generates only half the numbers <16, namely 0; 5; 4; 1; 8; 13; 12; 9; 0; : : x0 = 2 generates the other half.)
It can be shown the following con***ionsare necessary and suffcient for all numbers < m to be generated by ax i ^' 1 + c mod m.
gcd(c; m) =1,
each prime dividing m divides a ^' 1(which implies gcd(a; m) =1)
4 divides a ^' 1 if 4 divides m.
Notice that the generator
xi = 4253261x i ^' 1 + 372837 mod 2 24
satisffes these con***ions because the only prime dividing m = 2 24 is 2, and a and c are odd, hence
gcd(c; m) =1,
the prime 2 dividing m divides a ^' 1
(since a ^' 1 is even),
4 divides m and 4 divides a ^' 1
(since a ^' 1 = 4253260).
Hence, with this generator, all the numbers < 2 24 occur before a value is repeated.
Em thấy hay thì post vào, chứ em đọc chưa hiểu hết
Có ai dịch giúp với
Được babystar sửa chữa / chuyển vào 11:19 ngày 24/01/2003

Dành cho năm 1 (môn toán)
http://www.maths.monash.edu.au/eng1901/eng1901l.shtml
http://www.maths.monash.edu.au/eng1902/eng1902l.htm