Header Ads

Home thuat toan nhan binh phuong Thuật toán bình phương và nhân

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

10:32
Read
Thuật toán bình phương và nhân là thuậ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}

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.

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.





theo : http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_b%C3%ACnh_ph%C6%B0%C6%A1ng_v%C3%A0_nh%C3%A2n








Tags :

No comments:

Subscribe to: Post Comments ( Atom )
Powered by Blogger.