Thuật Toán Tính Căn Bậc 2 – Tìm Căn Bậc Hai (Không Sử Dụng Hàm Sqrt) Trong C

Mở đầuMở đầu

Vào khoảng những năm 2002, 2003, khi mã nguồn của tựa game Quake 3 Arena được chuyển thành mã nguồn mở, người ta đã tìm ra một hàm tính ra được giá trị nghịch đảo của căn bậc 2 một cách nhanh chóng, được biết đến rộng rãi với cái tên Fast inverse square root. Vào thời điểm đó, phép tính căn bậc 2 là một phép tính tốn nhiều tài nguyên, mà lại rất hay được sử dụng trong các phép tính vector. Với một game 3d đột phá vào thời điểm đó như Quake 3, thì sử dụng rất nhiều các phép tính dạng này. Mặc dù John Carmack, cha đẻ của dòng game Quake được nhắc đến như người đưa thuật toán trở nên phổ biến, nhưng những cài đặt đầu tiên đã được Gary Tarolli thực hiện trên máy tính SGI Indigo.

Bạn đang xem: Thuật toán tính căn bậc 2

Cách máy tính tính căn bậc 2Cách máy tính tính căn bậc 2Thực sự để tính xê dịch căn bậc 2 của một số ít, có rất nhiều chiêu thức. Dựa theo bài viết Methods of computing square roots, ta hoàn toàn có thể thấy, những chiêu thức trên đều dựa trên việc đưa ra một dãy vô hạn, một công thức truy hồi dẫn đến hiệu quả của phép tính căn bậc 2. bằng việc tái diễn công thức đến độ đúng chuẩn tùy ý, ta hoàn toàn có thể đưa ra hiệu quả với độ đúng chuẩn tùy ý .Mô tả giải pháp BabylonVí dụ, để tính căn bậc 2 của 125348, ta sẽ tính như sau :

Trên các máy tính hiện đại ngày nay, đã có các bộ chỉ thị phần cứng riêng để thực hiện việc này, bằng nhiều phương pháp khác nhau. Tuy nhiên vào thời điểm thập niên 90 của thế kỉ trước, phương pháp Fast inverse square root là một phương pháp hay, mang lại hiệu quả tính toán mà phần cứng chưa thể cung cấp được.

Cơ sở lý thuyếtCơ sở triết lýThuật toán được diễn đạt cơ bản như sau :Chuyển số sang dạng nguyên, tính xấp xỉ -1/2 log2(x)Đổi lại số sang dạng số thựcXấp xỉ 1 lần nữa với phương pháp Newton

Xấp xỉ Log2(x)

Chuyển số sang dạng nguyên, tính giao động – 1/2 log2 ( x ) Đổi lại số sang dạng số thựcXấp xỉ 1 lần nữa với giải pháp NewtonBiểu diễn số thực x dưới dạng tích của một số ít thực với một lũy thừa của 2 .Sx, là dấu, 0 nếu x > 0, là 1 nếu x Ex = ex + B là ” biased exponent “, với B = 127 là giá trị ” exponent bias ” ( 8 bits ) Mx = mx × L, với L = 223 ( 23 bits )Ta có :Suy ra :Vì m nằm trong đoạn 0 đến 1, ta có :Vẽ lên đồ thị để thấy rõ hơn với σ = 0 :

Người ta chứng minh được, với σ ≈ 0.0430357, sai số tuyệt đối sẽ nhỏ nhất.

Ta đổi phần thập phân sang dạng số tự nhiên, ta có :Suy ra :

Xấp xỉ 1 trên căn 2 x

Ta có :Dựa theo công thức giao động log ta có :Suy ra :Vìlà một hằng số, ta hoàn toàn có thể thuận tiện tính được phần Ix một cách thuận tiện .Xem thêm : Hướng Dẫn Cách Đổi Tên Facebook Trên Điện Thoại Iphone, Ipad, Laptop

Phương pháp Newton

Ta sử dụng giải pháp Newton để tăng tính đúng chuẩn cho thuật toán. Xin đọc bài Newton ” s method Ta có công thức :Tính đạo hàm ta có :Theo công thức Newton, ta có :Cài đặt thuật toán

Thuật toán phiên bản trong Quake 3, ngôn ngữ C:

Nhìn vào đoạn code này, ta thấy nó không được sạch lắm ( sử dụng lại biến, không định nghĩa constant, … ). Mình sẽ lý giải 1 số ít dòng không quen thuộc lắm nếu bạn chưa học C. Ở dòng 9, định nghĩa lại con trỏ kiểu float thành kiểu long trên cùng 1 vùng nhớ, ngược lại với dòng 11. Ở dòng 10, ta có phép toán dịch bit ( Kết luậnViệc giám sát trong tin học luôn có những sự độc lạ với tư duy toán học thuần túy của tất cả chúng ta. Tuy nhiên những đo lường và thống kê này đều dựa trên những biến hóa rất cơ bản và tự nhiên. Hy vọng những bạn thấy hay và hữu dụng .