Thuật toán bình phương và nhân

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Thuật toán bình phương và nhânthuật toán tính nhanh lũy thừa tự nhiên của một số (thực hoặc nguyên), trong trường hợp cơ số là số nguyên có thể được rút gọn theo một môđun nào đó.

Phép nâng lên lũy thừa tự nhiên bậc n của số x (x được gọi là cơ số) được định nghĩa từ hệ thức

x^n = \begin{matrix} \underbrace{ x*x*...*x}\\ n\end{matrix}

Với n lớn số phép nhân là rất lớn.

Ví dụ[sửa | sửa mã nguồn]

Chắng hạn với n=35 quá trình tính x^{35} qua 35 bước: 1\Rightarrow x\Rightarrow x^2=x*x\Rightarrow x^3=x^2*x\Rightarrow...\Rightarrow x^{35}=x^{34}*x
Ta nhận xét rằng có thể giảm bớt số phép nhân chẳng hạn với dãy phép tính

1\Rightarrow x\Rightarrow x^2=x*x,\Rightarrow x^4=(x^2)^2,\Rightarrow x^8=(x^4)^2
\Rightarrow x^{16}=(x^8)^2\Rightarrow x^{17}=x^{16}*x, \Rightarrow x^{34}=(x^{17})^2\Rightarrow x^{35}=x^{34}*x.

Công thức đệ quy[sửa | sửa mã nguồn]

Quá trình tính toán trên chính là quá trình tính nhờ công thức đệ quy

  1. Với n=0 thì x^n=1
  2. Với n>0 ta có công thức

f(n) = \begin{cases} (x^k)^2, & \mbox{khi }n=2k \\ (x^k)^2*x, & \mbox{khi }n=2k+1 \end{cases}

Như vậy phép tính x^n được quy về một số phép bình phương và phép nhân do vậy mà có tên gọi thuật toán bình phương và nhân.

Giải thuật đệ quy[sửa | sửa mã nguồn]

Giải thuật sau tính đệ quy x^n\pmod m

Function Square_Multi (int x, n, m){
 Var Int Power
 If n=0 then return 1
 Else {
     n:=LShift(n,1) 
     Power:= Square_Multi (int x, n, m)
     Power:=(Power^2) mod m
        If n BitAnd 1 =0 then 
          Return Power
        Else  
         Return (Power*x) mod m 
     } 
  }

Đoạn code viết bằng java:

public static int binhphuong (int x,int n,int m)
{
  int p;
  if (n==0) then return 1;
  p=binhphuong(x,n/2,m);
  if (n%2==0) 
     return (p*p)%m;
  else
     return (p*p*x)%m;
}

Chú ý rằng một số tự nhiênchẵn hay lẻ chỉ phụ thuộc vào bít số 0 của nó nên trong giải thuật trên ta sử dụng toán tử AndBit để xác định tính chãn lẻ của n và sử dụng phép LShif để tính phần nguyên của n/2.

Giải thuật không đệ quy[sửa | sửa mã nguồn]

Trong giải thuật đệ quy trên đây ta xét tính chẵn lẻ của n và liên tục chia n cho 2 lấy phần nguyên cho đến khi n=0. Thực chất quá trình này chính là tìm các bít của n. Do đó ta có thể thực hiện phép đổi ra số nhị phân trước sau đó tính lũy thừa theo quy tắc bình phươngnhân.

Giải thuật[sửa | sửa mã nguồn]

Đổi n ra số nhị phân ghi vào mảng  b[1..k]

Function Power_Modulo(Int x,n,m){
Var Int Power:=1 For i=1 to k do { Power:=(Power^2) mod m If b[i]=1 then Power:=(Power*x) mod m Return Power }

Ví dụ[sửa | sửa mã nguồn]

Trong ví dụ sau ta tính {37}^{27}\pmod {101}.

Đổi n=27 ra số nhị phân ta được 27= 11011_{(2)}.

Bảng sau đây tính toán từng bước theo giá trị của các bít của 27.

Khởi tạo p=1.

b[i] p=p^2 p=p\pmod {101} p*x p=\pmod {101}
1 1^2=1 1 1*37=37 37
1 37^2=1369 56 56*37=2072 52
0 52^2=2704 78 - 78
1 78^2=6084 24 24*37=888 80
1 80^2=6400 37 37*37=1369 56

Như vậy ta có

{37}^{27}\pmod {101} =56

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]