เลขฟีบอนัชชีขนาดใหญ่ใน C#

การคำนวณเลขฟีบอนัชชีขนาดใหญ่ใน C#

เลขฟีบอนัชชีเติบโตอย่างรวดเร็ว ตัวที่ 47 แล้วเกิน int.MaxValue (2,147,483,647) ต้องใช้ long (ถึงตัวที่ 92) หรือ BigInteger สำหรับตัวเลขใหญ่แบบไม่จำกัด

ใช้ long (64-bit) - จำกัดถึงตัวที่ 92

using System;

public class Demo
{
    public static void Main()
    {
        long val1 = 0, val2 = 1, val3;
        int n = 92; // สูงสุดสำหรับ long

        Console.WriteLine("ลำดับฟีบอนัชชี (long):");
        Console.Write(val1 + " " + val2 + " ");

        for (int i = 2; i < n; i++)
        {
            val3 = val1 + val2;
            Console.Write(val3 + " ");
            val1 = val2;
            val2 = val3;
        }
    }
}

ใช้ BigInteger (ไม่จำกัดขนาด) - แนะนำสำหรับเลขใหญ่จริง

using System;
using System.Numerics; // ต้องเพิ่ม reference System.Numerics

public class Demo
{
    public static void Main()
    {
        BigInteger val1 = 0, val2 = 1, val3;
        int n = 100; // คำนวณ 100 ตัวแรกได้เลย

        Console.WriteLine("ลำดับฟีบอนัชชี 100 ตัวแรก (BigInteger):");
        Console.Write(val1 + " " + val2 + " ");

        for (int i = 2; i < n; i++)
        {
            val3 = val1 + val2;
            Console.Write(val3 + " ");
            val1 = val2;
            val2 = val3;
        }
        
        Console.WriteLine($"\n\nตัวที่ 100 มี {val3.ToString().Length} หลัก");
    }
}

ผลลัพธ์ตัวอย่าง (บางส่วน)

ลำดับฟีบอนัชชี 100 ตัวแรก (BigInteger):
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 ...

ตัวที่ 100 มี 21 หลัก
ค่า F(100) = 354224848179261915075

การคำนวณแบบมีประสิทธิภาพ (Fast Doubling)

สำหรับเลขฟีบอนัชชีตัวที่ n โดยตรง (O(log n)):

public static BigInteger Fibonacci(int n)
{
    if (n <= 1) return n;
    
    BigInteger a = 0, b = 1;
    int highestBit = 31 - LeadingZeroCount(n); // หา bit สูงสุด
    
    for (int i = highestBit; i >= 0; i--)
    {
        // Double step
        BigInteger d = a * (b * 2 - a);
        BigInteger e = a * a + b * b;
        a = d;
        b = e;
        
        // Add step if bit is set
        if ((n & (1 << i)) != 0)
        {
            BigInteger c = a + b;
            a = b;
            b = c;
        }
    }
    return a;
}

สรุปการเลือกชนิดข้อมูล