Pagina's

2012/12/29

A218076 extended with C++

/*
The next term is: F(127495932) with 53 consecutive zeros.
I used Visual C++ 2010 Express, GMP, and MPIR,
see: GMP on windows

The C++ code below is about five times faster than the C# code before.
And... the next term will be larger than 150 * 10^6. 
*/


#include "stdafx.h"
#include "C:\projects\mpir-2.6.0\lib\Win32\Release\gmpxx.h"
#include "ctime"
#include "iostream"
using namespace std;

int lz(unsigned __int8 b)
{
    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;
}

int tz(unsigned __int8 b)
{
    return 7 - lz((unsigned __int8)(b & -(__int8)b));
}

void main()
{
    int i, i0, i1, j, k, z, zmax, size;
    cout << " low: "cin >> i0;
    cout << "high: "cin >> i1;
    cout << "zmax: "cin >> zmax;
    k = (zmax - 6) / 8;
    mpz_t F0, F1;
    mpz_inits(F0, F1, NULL);
    time_t now = time(0); cout << ctime(&now);
    cout << "compute F(" << dec << i1 << ")" << endl ;
    mpz_fib_ui(F0, i1); // mpz_out_str(stdout,16,F0)
    now = time(0); cout << ctime(&now);
    mpz_set(F1, F0);
    cout << "compute F's(" << dec << i0 - 2 << " & " << dec << i0 - 1 << ")" << endl;
    mpz_fib2_ui(F1, F0, i0 - 1);
    now = time(0); cout << ctime(&now) << endl;
    cout << "enter a number: ";
    cin >> i;
    now = time(0); cout << ctime(&now);
    cout << "S T A R T" << endl << endl;
    unsigned __int8 *p , *q;
    for(i = i0; i <= i1; i++)
    {
        if(i % 100000 == 0
        {
            now = time(0); cout << ctime(&now);
            cout << "F(" << dec << i << ")" << endl << endl;
        }
        mpz_add(F0,F0,F1);
        p = (unsigned __int8 *)F0[0]._mp_d;
        j = 1;
        if (*p == 0)
        {
            for (z = 8, p++, j++; *p == 0; p++, j++, z += 8);
            if (zmax < z + 7)
            {
                z += tz(*p);
                if (zmax < z)
                {
                    zmax = z;
                    k = (z - 6) / 8;
                    now = time(0); cout << "  " << ctime(&now);
                    cout << "  LOWZS: " << dec << z <<"  F(" << dec << i << ")" << endl << endl;
                }
            }
        }
        size = mpz_sizeinbase(F0, 256);
        for (j += k, p += k; j < size; j += k, p += k)
        {
            if (*p == 0)
            {
                for (z = 8, q = p - 1; *q == 0; q--, z += 8);
                for (p++, j++; *p == 0; p++, j++, z += 8);
                if (zmax < z + 14)
                {
                    z += lz(*q);
                    if (zmax < z + 7)
                    {
                        z += tz(*p);
                        if (zmax < z)
                        {
                            zmax = z;
                            k = (z - 6) / 8;
                            now = time(0); cout << "  "  << ctime(&now);
                            cout << "  ZEROS: " << dec << z << "  F(" << dec << i << ") :ZEROS" << endl << endl;
                        }
                    }
                 }
            }
        }
        mpz_swap(F0,F1);
    }
    now = time(0); cout << ctime(&now);
    cout << "F(" << dec << i1 << ")" << endl;
    cout << "enter a number: ";
    cin >> i;
    now = time(0); cout << ctime(&now);
    cout << "compute F(" << dec << i1 << ")" << endl ;
    mpz_fib_ui(F0, i1);
    now = time(0); cout << ctime(&now) << endl;
    if (mpz_cmp(F0, F1) != 0cout << endl << "E R R O R ! ! ! !" << endl;
    mpz_clears(F0, F1, NULL);
    cout << "zmax: " << dec << zmax << endl;
    cout << endl << "R E A D Y";
    cin >> i;
}