Optimize a algorithm that find a specific Fibonacci number

Question

Given an number A, I want to find the Ath Fibonacci number that is multiple of 3 or if the number representation has at least a 3 on it.

Example:

Fibonacci > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

Input: 1, Output: 3;

3 is the first Fibonacci number that is multiple of 3 or has an 3 on it.

Input: 3, Output: 21;

21 is the third Fibonacci number that is multiple of 3 or has an 3 on it.

Edit: Variable type changed to unsigned long long int and ajust on Fibonacci generator. Thanks @rcgldr and @Jarod42 for the help!

My code:

#include<bits/stdc++.h>

using namespace std;

int tem(unsigned long long int i){

    while(i != 0){
        if(i%10 == 3){
            return true;
        }
        i = i/10;
    }
    return false;
}

int main(){

    int a, count = 0;
    unsigned long long int f1 = 1, f2 = 1;

    while(scanf("%d", &a) != EOF){
        for(unsigned long long int i = 2; i > 0; i++){
            i = f1 + f2;
            f1 = f2;
            f2 = i;
                if((i%3 == 0) || tem(i)){
                    count++;
                    if(count == a){
                        cout << i << endl;
                        break;
                    }
                }

        }
    }
}

When A > 20, it starts to slow down. Makes sense because it tends to be exponecial. My code is not very efficient, but I didn't find an better logic to use.

I looked into these links, but didn't find an conclusion:

1 - Recursive Fibonacci

2 - Fibonacci Optimization

Any ideas? Thanks for the help!

Answer 1

You can speed up the Fibonacci part using this sequence

uint64_t f0 = 0;    // fib( 0)
uint64_t f1 = 1;    // fib(-1)
int n = ... ;       // generate fib(n)
    for(int i = 0; i < n; i++){
        std::swap(f0,f1);
        f0 += f1;
    }

Note Fib(93) is the maximum Fibonacci number that fits in a 64 bit unsigned integer, it also has a 3 in it. Fib(92) is the maximum Fibonacci number that is a multiple of 3.

I used this example code to find all of the values (a ranges from 0 to 62), it seems to run fairly fast, so I'm not sure what the issue is. Is optimization enabled?

#include <iostream>
#include <iomanip>

typedef unsigned long long uint64_t;

int tem(uint64_t i){
    while(i != 0){
        if(i%10 == 3)
            return true;
        i = i/10;
    }
    return false;
}

int main(){
    int a = 0, n;
    uint64_t f0 = 1, f1 = -1;  // fib(-1), fib(-2)

    for(n = 0; n <= 93; n++){
        std::swap(f0, f1);     // f0 = next fib
        f0 += f1;
        if((n&3) == 0 || tem(f0)){
            std::cout << std::setw( 2) << a << " " 
                      << std::setw( 2) << n << " "
                      << std::setw(20) << f0 << std::endl;
            a++;
        }
    }
    return 0;
}

Depending on the compiler, i%10 and i/10 may use a multiply by "magic number" and shift to replace divide by a constant. Code generated by Visual Studio 2015 for tem(), which is fairly "clever":

tem     proc                                ;rcx = input
        test    rcx,rcx                     ; return false if rcx == 0
        je      SHORT tem1
        mov     r8, 0cccccccccccccccdh      ;magic number for divide by 10
tem0:   mov     rax, r8                     ;rax = magic number
        mul     rcx                         ;rdx = quotient << 3
        shr     rdx, 3                      ;rdx = quotient
        lea     rax, QWORD PTR [rdx+rdx*4]  ;rax = quotient*5
        add     rax, rax                    ;rax = quotient*10
        sub     rcx, rax                    ;rcx -= quotient * 10 == rcx % 10
        cmp     rcx, 3                      ;br if rcx % 10 == 3
        je      SHORT tem2
        mov     rcx, rdx                    ;rcx = quotient  (rcx /= 10)
        test    rdx, rdx                    ;loop if quotient != 0
        jne     SHORT tem0
tem1:   xor     eax, eax                    ;return false
        ret     0

tem2:   mov     eax, 1                      ;return true
        ret     0

tem     endp

Answer 2

Just pointing out some obvious coding errors

for(unsigned long long int i = 2; i > 0; i++)

is redundant.

for(;;){ 
  unsigned long long i = f1+f2;

should suffice. Secondly

return 0; 

is meaningless because it breaks out of the while loop. A break would be better.

Answer 3

There's a clever way to do Fibonacci.

http://stsievert.com/blog/2015/01/31/the-mysterious-eigenvalue/

Code's in python and is just for the nth number, but I think you get the idea.

def fib(n):
    lambda1 = (1 + sqrt(5))/2
    lambda2 = (1 - sqrt(5))/2
    return (lambda1**n - lambda2**n) / sqrt(5)
def fib_approx(n)
    # for practical range, percent error < 10^-6
    return 1.618034**n / sqrt(5)