Tôi thực sự bối rối. Tôi đang cố gắng tính các số Fibonacci, nhưng khi chúng ngày càng lớn hơn, các con số bắt đầu có vẻ sai. Tôi không biết tại sao.

Làm cách nào tôi có thể tính toán các số Fibonacci chính xác bằng công thức Binet, theo hiểu biết của tôi, công thức này luôn trả về một số nguyên?

Đây là thứ tôi đã cố gắng sử dụng.

http://ideone.com/e6t6h

Hãy xem những con số đang tăng lên. Trở nên kỳ lạ?

Ở đây tôi sử dụng cout.precision(15); để in ra

http://ideone.com/XREh2

Ở đây tôi sử dụng cout << fix << blah blah; để in ra;

Ở đây tôi đang sử dụng vòng lặp chương trình để tính toán bằng cách lặp qua nó.

Điều này chính xác hơn việc sử dụng công thức Binet.

Dẫu sao thì. Có ai có bất kỳ mã nào tôi có thể xem để tính F(n) mà không cần sử dụng công thức Binet để lặp qua từng cấp độ của (n) không?

câu trả lời hay nhất

Để tính toán chính xác các số Fibonacci bằng công thức Binet, bạn cần diễn giải chính xác √5. Vì √5 là số vô tỉ nên không dùng đượcgấp đôiđể diễn đạt một cách chính xác. hoặc float , do đó công thức Binet không áp dụng được cho những loại này (tuy nhiên, việc làm tròn trong phép tính có thể dẫn đến kết quả chính xác cho một số đầu vào nhỏ). Vì số Fibonacci là số nguyên nên bạn có thể sử dụng gấp đôi Nhận kết quả chính xác từ công thức Binet. hoặc floatNhận thêm thông số bằng cách làm tròn,

binet kép(unsigned int n)
{
    const tĩnh double phi = (1 + sqrt(5))*0.5;
    fib đôi = (pow(phi,n) - pow(1-phi,n))/sqrt(5);
    vòng quay trở lại(fib);
}

Điều này sẽ có tác dụng với hầu hết tất cả n trả về kết quả đúng đủ nhỏ để kết quả có thể được biểu thị chính xác như gấp đôi .Tuy nhiên, số lượng này không nhiều. gấp đôiThông thường chỉ có độ chính xác 53 bit, do đó chỉ có ít hơn 2⁵³ Số Fibonacci có thể được biểu diễn chính xác như sau gấp đôi (Cộng với một số cái lớn hơn có thể chia hết cho lũy thừa đủ cao là 2). Cái cuối cùng nhỏ hơn 2⁵³ Số Fibonacci là F(77), nhưng F(78) chia hết cho 8, do đó nó cũng có thể được biểu diễn chính xác như sau gấp đôiCó độ chính xác 53 bit. Tuy nhiên, những điều trên chỉ áp dụng được cho n <= 70 tạo ra kết quả đúng ở đây, bắt đầu từ 71, sai số làm tròn quá lớn (BTW, công thức Binet sử dụng đôi Kết quả của ở đây luôn quá lớn nên hãy sử dụng sàn nhà thay vì tròn cũng sẽ là F(71), nhưng không xa hơn).

Không có nhiều số Fibonacci có thể được biểu diễn chính xác bằng cách sử dụng các kiểu dữ liệu tiêu chuẩn, số cuối cùng phù hợp với loại 64-bit (không dấu) là F(93); đối với 128-bit, số cuối cùng là F(186). Đối với một chỉ mục nhỏ như vậy, sẽ thu được rất ít lợi ích với thuật toán lặp đơn giản

fibonacci dài không dấu(unsigned int n)
{
    dài không dấu dài a = 0, b = 1;
    vì(; n > 0; --n)
    {
        b += a;
        a = ba;
    }
    trả lại một;
}

Trừ khi bạn sử dụng bảng tra cứu

const tĩnh không dấu sợi dài dài [94] = { 0, 1, 1, 2, ... , 12200160415121876738ull };

Để có được kết quả chính xác, bạn phải coi √5 (và/hoặc φ) là hằng số ký hiệu và sử dụng nó để tính công thức. Điều này tương đương với công thức trong vòng đánh giá

ℤ[φ] = { a + b*φ : a, b ∈ ℤ }

ℚ(√5) số nguyên đại số trong , sử dụng φ² = 1 + φ Thực tế tương đương với công thức Binet là

φ^n = F(n-1) + φ*F(n)

Có thể được sử dụng để tính toán hiệu quả các số Fibonacci bằng cách lặp lại các bình phương trong các bước O(log n) (nhưng lưu ý rằng F(n) có Θ(n) bit, do đó số thao tác bit không thể nhỏ hơn O(n)). hơn Vanilla Square sử dụng phiên bản hiệu quả hơn một chút

φ^(2n) = (φ^n)² = (F(n-1) + φ*F(n))² = F(n-1)² + φ*2*F(n-1)*F (n) + φ 2*F(n) 2
       = (F(n-1) 2 + F(n) 2) + φ*(2*F(n-1)*F(n) + F(n) 2)

Phát hiện F(2n) = 2*F(n)*F(n-1) + F(n)² = 2*F(n)*F(n+1) - F(n)² = F(n)* (F(n+1) + F(n-1))Và F(2n+1) = F(n) 2 + F(n+1) 2 , sử dụng φ² = 1 + φ .Các công thức này cho phép tính F(2n), F(2n+1) và F(2n+2) từ F(n) và F(n+1) với tối đa hai phép nhân và hai phép cộng/trừ cho mỗi số, trong đó đưa ra thuật toán tính toán các cặp (F(n),F(n+1))Trong các bước O(log n), chỉ có hai số làm trạng thái (Hình vuông lặp lại Vanilla sử dụng bốn số làm trạng thái, yêu cầu nhiều phép nhân hơn).

Thuật toán lặp từ trái sang phải là

sợi dài dài không dấu(unsigned int n){
    nếu (n == 0) trả về 0;
    unsigned int h = n/2, mặt nạ = 1;
    // tìm bit được đặt cao nhất trong n, có thể được thực hiện tốt hơn
    while(mặt nạ <= h) mặt nạ <<= 1;
    mặt nạ >>= 1;
    dài không dấu dài a = 1, b = 1, c; // a = F(k), b = F(k+1), k = 1 ban đầu
    trong khi(mặt nạ)
    {
        c = a*a+b*b; // F(2k+1)
        nếu (n&mặt nạ)
        {
            b = b*(b+2*a); ​​​​// F(2k+2)
            a = c; // F(2k+1)
        } khác {
            a = a*(2*ba); // F(2k)
            b = c; // F(2k+1)
        }
        mặt nạ >>= 1;
    }
    trả lại một;
}

Thay vào đó hãy sử dụng các loại chính xác tùy ý không dấu dài dài , cho phép tính toán nhanh các số Fibonacci lớn. Nhưng tất nhiên, các thư viện có độ chính xác tùy ý thường đi kèm với các hàm Fibonacci được tối ưu hóa của riêng chúng, vì vậy việc tự triển khai nó sẽ hơi khó khăn.

Giới thiệu về c++ - Tính chính xác dãy Fibonacci trong C++? , chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/9645193/