A218076 three more with C on 64 bits Linux

/*
The next terms are:
F(177416979) with 54 consecutive zeros,
  198423144       56
  275354607       58
Next one will be larger than 3*10^8, presumable 18*10^8.
 
Computed with a new silent cheap PC.


 

 


















CPU: AMD Phenom II X4 965, 3.4 GHz (fastest in GMP benchmarks)
RAM: 8 GB
 OS: Debian 6.0.6 (Squeeze) Kernel Linux 2.6.32-5-amd64
GMP: 5.1.0
GCC: 4.4.5
IDE: MonoDevelop 2.4

Results: Fibonacci(10^9) in 12 seconds, factorial(32*10^6) 30 seconds,
both using 1 core, what will happen with a parallel version of Karatsuba? 
The C code below is about two times faster than the C++ code before,
probably because a 64 bits system is used instead of a 32 bits one,
most time is spent adding big numbers, with 64 bits it should be 
about two times faster, shouldn't it?

Is it possible to approximate the chance which Fibonacci number, F(n),
has a record number of consecutive zeros, z?
For larger values of n it seems to be.
Suppose we write the numbers as a long binary string.
F1=1, F2=1, F3=10, F4=11, F5=101, F6=1000, ...
The long binary string ends with: ...1000 101 11 10 1 1

How many bits are there from F1 up to Fn?
                             F1       F1?  0.7 * 1
                             F1       F2?  0.7 * (1+2)
                             F1       F3?  0.7 * (1+2+3)
                             F1       F4?  0.7 * (1+2+3+4)
                             F1       Fn?  0.7 * n * (n+1) / 2

How many coin flips on average does it take to get z consecutive heads?

Answer: 2^(z+1) - 2

So:     2^(z+1) - 2 = 0.7 * n * (n+1) / 2

For larger values of z (and n):

 n ~ 2.40 * 2^(z/2)

 z ~ 2.89 * ln(n) - 2.53

          n  cz(F(n))  2.89*ln(n)-2.53

          3        1    1 
          6        3    3
         12        4    5
         19        5    6
         38        6    8
         42        7    8
         68       12   10
        243       13   13
        384       14   15
        515       16   16
        740       19   17
       1709       24   19
       5151       27   22
      11049       28   24
      45641       30   28
      94729       31   31
     185610       34   33
     644593       35   36
     726681       39   36
    2296396       40   40
    3098358       42   41
    6178778       43   43
   15743325       45   45 
   22436908       48   46
   80141430       49   50
   84300971       51   50
  127495932       53   51
  177416979       54   52
  198423144       56   53
  275354607       58   54
 
Conclusion: 
A218076 seems to have properties of a random sequence.
Of course it isn't a random sequence, the terms are the: 
Lowest positive indices of Fibonacci numbers whose binary
expansions have record numbers of consecutive zeros.
And...it's getting harder and harder to find new ones.
The next term, with 59 consecutive zeros, will be 
~6.6 times larger than the last term found (50% chance).
*/

#include <stdio.h>
#include <gmp.h>
#include <time.h>

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

time_t rawtime;
struct tm * timeinfo;
char buffer[80];
void printTime()
{
    time( &rawtime);
    timeinfo = localtime(&rawtime);
    strftime (buffer, 80, "%c", timeinfo);
    puts(buffer);    
}

void main ()
{
    int i, i0, i1, j, k, z, zmax, size; 
    printf(" low: "); scanf("%d", &i0);
    printf("high: "); scanf("%d", &i1);
    printf("zmax: "); scanf("%d", &zmax);
    k = (zmax - 6) / 8;
    mpz_t F0, F1;
    mpz_init(F0); mpz_init(F1);
    printTime();    
    printf(" compute F(%d)\n", i1);
    mpz_fib_ui(F0, i1);
    mpz_set(F1, F0); 
    printTime();    
    printf(" compute F's(%d & %d)\n", i0 - 2 , i0 - 1);
    mpz_fib2_ui(F1, F0, i0 - 1); 
    printTime();
    printf("enter a number: "); scanf("%d", &i);
    printTime();
    printf("   S T A R T \n");
    unsigned char *p , *q;     
    for(i = i0; i <= i1; i++)
    {
        if(i % 100000 == 0) 
        {
            printTime();
            printf("F(%d)\n", i);
        }
        mpz_add(F0,F0,F1);
        p = (unsigned char *)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;
                    printTime();
                    printf("  LOWZS: %d F(%d) \n", z, i);                   
                }
            }
        }
        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;
                            printTime();
                            printf("  ZEROS: %d F(%d)  ZEROS \n", z, i);
                        }
                    }
                 }
            }
        }
        mpz_swap(F0, F1);     
    } 
    printTime();
    printf("   R E A D Y\n");
    printf("enter a number: "); scanf("%d", &i);
    printTime();
    printf(" compute F(%d)\n", i1);
    mpz_fib_ui(F0, i1); 
    printTime();
    if (mpz_cmp(F0, F1) != 0) 
    {
        printf("   E R R O R\n");
    }
    else
    {
        printf("  ZMAX: %d \n", zmax);
    }
    mpz_clear(F0); mpz_clear(F1);
}