Thuật toán tính căn bậc 2

Mở đầu

Vào khoảng trong thời hạn 2002, 2003, khi mã mối cung cấp của tựa trò chơi Quake 3 Arena được đưa thành mã nguồn mở, tín đồ ta vẫn tìm ra một hàm tính ra được giá trị nghịch hòn đảo của căn bậc 2 một cách nhanh chóng, theo thông tin được biết đến rộng rãi với cái thương hiệu 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 thường được sử dụng trong các phép tính vector. Cùng với một trò chơi 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, thân phụ đẻ của loại game Quake được nhắc tới như người đưa thuật toán trở buộc phải phổ biến, dẫu vậy những cài đặt đầu tiên đã có Gary Tarolli thực hiện trên máy vi 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 2

Thực sự để tính xê dịch căn bậc 2 của một số, có không ít phương pháp. Dựa theo bài viết Methods of computing square roots , ta hoàn toàn có thể thấy, các cách thức trên đều dựa vào việc đưa ra một dãy vô hạn, một bí quyết truy hồi dẫn đến kết quả của phép tính căn bậc 2. Bằng việc tái diễn công thức mang lại độ chính xác tùy ý, ta rất có thể đưa ra kết quả với độ đúng chuẩn tùy ý.

Mô tả phương pháp BabylonVí dụ, nhằm 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, sẽ có những bộ chỉ thị phần cứng riêng biệt để thực hiện việc này, bằng nhiều phương thức khác nhau. Tuy vậy vào thời gian thập niên 90 của rứa kỉ trước, phương thức Fast inverse square root là một cách thức hay, sở hữu lại hiệu quả tính toán cơ mà phần cứng không thể hỗ trợ được.

Cơ sở lý thuyết

Thuật toán được biểu đạt cơ phiên bản như sau:

Chuyển số lịch sự dạng nguyên, tính giao động -1/2 log2(x)Đổi lại số lịch sự dạng số thựcXấp xỉ 1 đợt nữa với cách thức Newton

Xấp xỉ Log2(x)

Biểu diễn số thực x dưới dạng tích của một số thực với 1 lũy vượt của 2.

Sx, là dấu, 0 nếu x > 0, là một trong nếu x Ex = ex + B là "biased exponent", cùng với B = 127 là cực hiếm "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 mang lại 1, ta có:

Vẽ lên đồ thị để thấy rõ rộng với σ = 0:

Người ta chứng minh được, cùng với σ ≈ 0.0430357, sai số tuyệt đối hoàn hảo sẽ nhỏ dại nhất.

Ta đổi phần thập phân sang trọng 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 xê dịch log ta có:

Suy ra:

Vì

là 1 hằng số, ta rất có thể dễ dàng tính được phần Ix một giải pháp dễ dàng.

Xem thêm: Top 3+ Cách Sửa Lỗi Nhảy Chữ Trong Word 2010, Lỗi Chữ Không Liền Nhau

Phương pháp Newton

Ta sử dụng phương thức Newton nhằm tăng tính chính xác cho thuật toán. Xin đọc bài Newton"s method Ta tất cả công thức:

Tính đạo hàm ta có:

Theo bí quyết Newton, ta có:

Cài đặt thuật toán

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

Nhìn vào đoạn code này, ta thấy nó không được sạch mát lắm ( sử dụng lại biến, không có mang constant, ... ). Mình sẽ giải thích một số dòng không không còn xa lạ lắm nếu như bạn chưa học C. Ở dòng 9, định nghĩa lại con trỏ đẳng cấp float thành kiểu long trên thuộc 1 vùng nhớ, ngược lại với loại 11. Ở mẫu 10, ta có phép toán dịch bit ( Kết luận

Việc giám sát trong tin học luôn có phần nhiều sự khác hoàn toàn với tứ duy toán học tập thuần túy của bọn chúng ta. Tuy vậy những giám sát và đo lường này đều dựa vào những biến đổi rất cơ phiên bản và từ nhiên. Hy vọng chúng ta thấy tốt và bửa ích.