// an approximation for a factorial: // // http://mathworld.wolfram.com/StirlingsApproximation.html // // n! ~ ((2*n+1/3)*Pi)^0.5 * n^n * e^-n // // for the number of bits of a factorial we get: // // bL_FAC = n * (Math.Log(n) - 1) * 1.44269504088896 // + Math.Log(n + 1 / 6) * 0.72134752044448 // + 2.32574806473616 // // upto 2000000! the function "approximate_bL_FAC" is exact, // probably it will stay exact for much larger values, // let's say the approximation is close. // using System; using Xint = System.Numerics.BigInteger; class Program { public static int approximate_bL_FAC(int n) { if (n <= 2) return (n >> 1) + 1; return (int)(n * (Math.Log(n) - 1) * 1.44269504088896 + Math.Log(n + 1 / 6) * 0.72134752044448 + 2.32574806473616); } static void Main() { Console.WriteLine(System.DateTime.Now); int n = 1; Xint F = 1; while (n <= 2000000) // about eight hours on my PC { F *= n; if (bL(F) - approximate_bL_FAC(n) != 0) Console.WriteLine(n); n++; } Console.WriteLine(System.DateTime.Now); Console.WriteLine("READY"); Console.ReadLine(); } public static int bL(Xint U) { byte[] bytes = (U.Sign * U).ToByteArray(); int i = bytes.Length - 1; return (i << 3) + 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
2010/11/27
number of bits of factorial, approximation of bitlength factorial
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment