// 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; } }
C# , System.Numerics, Multiplication, Karatsuba, Toom Cook, Division, Burnikel, Ziegler, Factorial, Luschny, Square Root, Zimmermann, Choose, Binomial Coefficient, Permutation, Combination, Eratosthenes, Primes, Fibonacci, Lucas, Pell, Catalan, Fast Random Number Generator, Overton
2012/09/28
Number of bits Fibonacci number
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment