Pagina's

2010/11/27

number of bits of factorial, approximation of bitlength factorial

// 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;
    }
}

No comments:

Post a Comment