Pagina's

2012/11/24

A218076 extended

// The next two terms are:
// F(80141430) 49 consecutive zeros, and
// F(84300971) 51 consecutive zeros
// I used Emil Stefanov's wrapper for GMP 
// (The GNU Multiple Precision Arithmetic Library).
// www.emilstefanov.net/Projects/GnuMpDotNet/
// Copied "libgmp-3.dll" to "C:\WINDOWS\System32\"
// This general compilation computes F(10^9) in 42 seconds.
// Two copies of the program below, for example one
// scanning the range 80000000-82000000, the other 
// scanning the range 82000000-84000000, take ~32 hours.
// And... the next term will be larger than 95999999.

using System;
using System.Threading.Tasks;
using Emil.GMP;  // Project>>Add Reference>>Emil.GMP.dll
class F_cz_gmp
{
    static void Main()
    {
        int i = 80000000;                          // 82000000
        int zmax = 48;
        int[] z = { 0, 0 };
        int k = (zmax - 6) / 8;
        Console.WriteLine("first i: " + i);
        BigInt[] F = new BigInt[2];
        F[1] = BigInt.Fibonacci(i - 1, out F[0]);
        for (; i < 82000000; i += 2)               // 84000000
        {
            if (i % 500000 == 0) Console.WriteLine(i + " " + DateTime.Now);
            F[0] += F[1];
            F[1] += F[0];
            Parallel.For(0, 2, (int j) => z[j] = zeros(F[j], zmax, k));
            GC.Collect();
            if (z[0] > zmax)
            {
                zmax = z[0];
                k = (zmax - 6) / 8;
                Console.WriteLine(i + " " + zmax);
            }
            if (z[1] > zmax)
            {
                zmax = z[1];
                k = (zmax - 6) / 8;
                Console.WriteLine((i + 1) + " " + zmax);
            }
        }
        Console.WriteLine("last i: " + (i - 1) + " " + DateTime.Now);
        Console.ReadLine();
    }
    private static int zeros(BigInt F, int zmax, int k)
    {
        byte[] b = F.ToByteArray(); // F.ToUintArray ~4 times faster
        int bL = b.Length;
        int j = 0;
        int z;
        if (b[0] == 0)
        {
            z = 8;
            while (b[++j] == 0) z += 8; // add zerobits
            if (zmax < z + 7)
            {
                z += tz(b[j]);
                if (zmax < z)
                {
                    zmax = z;
                    k = (z - 6) / 8;
                }
            }
        }
        j += k;
        while (j < bL)
        {
            if (b[j] == 0)
            {
                z = 8;
                int j0 = j;
                while (b[--j0] == 0) z += 8; // add zerobits
                while (b[++j] == 0) z += 8;
                if (zmax < z + 14)
                {
                    z += lz(b[j0]);
                    if (zmax < z + 7)
                    {
                        z += tz(b[j]);
                        if (zmax < z)
                        {
                            zmax = z;
                            k = (z - 6) / 8;
                        }
                    }
                }
            }
            j += k;
        }
        return zmax;
    }
    private static int lz(byte b) // leading zeros, b > 0
    {
        return b < 1 << 4 ? b < 1 << 2 ? b < 1 << 1 ? 7 : 6 :
                                         b < 1 << 3 ? 5 : 4 :
                            b < 1 << 6 ? b < 1 << 5 ? 3 : 2 :
                                         b < 1 << 7 ? 1 : 0;
    }
    private static int tz(byte b) // trailing zeros
    {
        return 7 - lz((byte)(b & -(sbyte)b));
    }
}