Tính căn bậc 2 mà không dùng sqrt

Tính căn bậc 2 của một số theo một cách khác

Vấn đề

Trong một buổi phỏng vấn, có một câu hỏi như sau:

Hãy viết chương trình C tính căn bậc 2 của số nguyên x

Trong chớp mắt, bạn có thể đưa ra ngay lời giải với đoạn code ngắn gọn sau:

#include <stdio.h>
#include <math.h>

int main()
{
    int x;
    printf("Input x: ");
    scanf("%d", &x);
    printf("Sqrt of %d = %f\n", x, sqrt(x));
}
Input x: 3
Sqrt of 3 = 1.732051

Chương trình compiled không có một lỗi và ra kết quả đúng.

Đến đây, bạn đã chứng tỏ bạn là người có căn bản. :) Nhưng đời lại không như đồn. <3

Ban phỏng vấn lại đặt ra một câu hỏi rất liên quan:

“Cậu hãy trả lời lại câu hỏi trên, lần này không dùng hàm sqrt của thư viện C”

Câu hỏi bắt đầu khó hơn rồi đấy, bạn đã thấy khoai chưa? Đến đây, nếu bạn không có câu trả lời, tức là bạn còn phải cố gắng rất nhiều nữa.

Vậy làm thế nào mà người ta lại có thể tính ra căn bậc 2 của một số mà không dùng hàm SQRT? Phải chăng là chúng ta sẽ phải viết một thuật toán phức tạp với rất nhiều dòng mã?

Và đây, là câu trả lời cho vấn đề khá hóc búa kia:

Máy tính làm phép tính rất nhanh, thay vì có câu trả lời tuyệt đối, ta có thể bắt nó đoán câu trả lời cho ta!

Căn bậc hai của y được định nghĩa là số x sao cho: x^2 == y hay x = y / x. Nếu x là kết quả thì x = y / x, còn nếu không kết quả sẽ phải là 1 số x’ nằm trong khoảng x và y/x. Ta không biết số này là bao nhiêu, nhưng ta có 1 cách để đoán lấy 1 số trong khoảng này đó là trung bình cộng!

Ví dụ:

Cần tính căn bậc 2 của 3. Ta đoán kết quả là 1.0. Kết quả này không đúng rồi, nên đáp số sẽ nằm trong khoảng 1.0 và 31.0 = 2.0. Lấy trung bình cộng lần 1 ta có kết quả là 1.5. Lại thử với 1.5 và 31.5 = 2.0 ta có kết quả là 1.75! Sau nhiều lần lặp ta sẽ có kết quả tiệm cận với đáp số!

Vì ta không có kết quả chính xác, nên số lần lặp sẽ là vô hạn. Tuy vậy tại mỗi bước lặp, ta sẽ thử xem kết quả đủ chính xác theo yêu cầu chưa. Ví dụ nếu đáp số hiện tại là x = 1.73, x^2 = 2.99 và ta chỉ cần độ chính xác đến 2 số sau dấu phẩy, thì 1.73 là đáp án phù hợp. Do vậy ta sẽ có chương trình tính căn bậc 2 như sau:

#include <stdio.h>
#include <math.h>

#define PRECISE 0.0001f

double mysqrt(int x)
{
    double guess = 1.0f;
    while (fabs(guess*guess - x) >= PRECISE)
        guess = (x/guess - guess) / 2 + guess;
    return guess;
}

int main(void)
{
    int x;
    printf("Input x: ");
    scanf("%d", &x);
    printf("Sqrt of %d = %f\n", x, mysqrt(x));
    return 0;
}
Input x: 3
Sqrt of 3 = 1.732051

Tham khảo

Từ kipalog.com