Section 3.2.1.2 của "The art of computer programming" (part 2)

math

(newbie lập trình) #1

Mình không hiểu phần:
Therefore the period is length of m if and only if the period of the senquence with X0 = 0 is of length m


Và bổ đề R khi p = 2 ở phần:
These arguments show that it is necessary in general to have a = 1+q.p^f,where p^f>2 and q is not a multiple of p,whenever k= p^e

Mình có ba câu hỏi:

  • Tại sao khi dãy có length m tại X0 = 0 ta suy ra dãy có length m với X0 trong khoảng [1;m] ?
  • Tại sao phải xét riêng trường hợp p=2 trong khi có thể dùng cách tương tự như khi p>2 để chứng minh?
  • Nếu cần xét riêng thì tại sao a = 1 +qp^f ?

(rogp10) #2
  1. Do mod m và [1…m-1] chỉ có m-1 phần tử, không đủ nên phải có 0. Ta có dãy vô hạn tuần hoàn rồi thì bắt đầu chỗ nào cũng như nhau thôi, ý câu đó là vậy.

Thay p = 2 và với a = 4k+3, đồng dư thức trở thành a^(2^(e - 1) - 1)/(a - 1) = 0 (mod 2^e)

tức là tạch, chu kì tối đa 2^(e-1).


(newbie lập trình) #3

Anh giải thích rõ hơn chỗ “dãy vô hạn rồi thì bắt đầu chỗ nào cũng như nhau thôi” được không ạ ? :frowning:


(rogp10) #4

Cụ thể là ntn: “Chạy một vòng sân” nghĩa là chạy trên chu vi (hay đường piste :smiley: ) của sân về điểm xuất phát. Vậy bắt đầu chỗ nào không quan trọng, đủ một vòng thôi :smiley: Không mất tính tổng quát, chọn x0 = 0.


Hệ thức x[n+1] = (a*x[n] + c) mod m ứng với sơ đồ Horner sau:

  | X0 c  c  c  ...
-------------------
a | X0 X1 X2 X3 ...

tức là đa thức g(y) = X0*y^n + c*(y^(n-1) + y^(n-2) + ... + 1)
hay x[n] = g(a) mod m.

Khử X0 bằng cách gán cho nó là zero. Số hạng còn lại là lũy thừa mod nhân với hằng số nên phải có chu kì.


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?