Pagina's

2012/09/28

Number of bits Fibonacci number

// Binet's formula: 
//
//         Fib(n) = ( Phi^n - (-1)^n / Phi^n ) / 5^(1/2)
//
// Where Phi = (1+5^(1/2))/2 ~ 1.61803398874989484820458683436563811772030917980576....(Knott)
//                           ~ 1.6180339887498948482045868343656381177203+             (Knuth)
//
// For larger values of n:
//
//         Fib(n) ~ Phi^n / 5^(1/2)
//
// For the number of bits, x, of Fib(n):
//
//            2^x ~ Fib(n) ~ Phi^n / 5^(1/2)
//
// Taking natural logarithms:
//
//        ln(2^x) ~ ln(Phi^n / 5^(1/2))
//
// So:
//      x * ln(2) ~ n * ln(Phi) - 1/2 * ln(5)
//              x ~ n * ln(Phi)/ln(2) - ln(5)/ln(2)/2
//
// Using "windows calculator" which seems to have a precision of ~105 bits ~31 decimal digits:
//
//              x ~ n * 0,6942419136306173017387902668986 - 1,1609640474436811739351597147447
//
// A partial bit (digit) is a bit (digit):
//
//        x ~ (int)(n * 0,6942419136306173017387902668986 - 1,1609640474436811739351597147447 + 1)
//
// The mantissa of a double has a precision of 52 bits ~ 16 decimal digits:
//
//        x = (int)(n * 0,6942419136306173 - 0,1609640474436812)
//
// Below it is correct for 0 <= n <= 24 * 10^6, after two days the output is: "R E A D Y"
// Also for n = 5 * 10^8 it's correct
//      for n = 10^9 it seems to be correct too.

using System;
using Xint = System.Numerics.BigInteger;
class bitLength_Fibonacci
{
    private static int bL_F(int n)
    {
        return n < 6 ? ++n / 2 : (int)(0.6942419136306173 * n - 0.1609640474436812);
    }

    static void Main()
    {
        Xint[] F = { 0, 1 };
        for (int n = 1; n <= 24000000; n++)
        {
            F = new Xint[2] { F[1], F[1] + F[0] };
            if (bL(F[0]) != bL_F(n))
            {
                Console.WriteLine(n + "   " + bL(F[0]) + "   " + bL_F(n));
            }
        }
        Console.WriteLine("R E A D Y");
        Console.ReadLine();
    }

    private static int bL(Xint X)
    {
        byte[] bytes = (X.Sign * X).ToByteArray();
        int i = bytes.Length - 1;
        return i * 8 | bitLengthMostSignificantByte(bytes[i]);
    }
    private static int bitLengthMostSignificantByte(byte b)
    {
        return b < 08 ? b < 02 ? b < 01 ? 0 : 1 :
                                 b < 04 ? 2 : 3 :
                        b < 32 ? b < 16 ? 4 : 5 :
                                 b < 64 ? 6 : 7;
    }
}

No comments:

Post a Comment