4,000,000 이하의 피보나찌 수열 중 짝수의 합 구하기

ZFanta님의 블로그를 보니 같은 제목의 글이 하나 올라와있었다.
(태클은 아니지만) 코드가 좀 길어 보이더라. 게다가 메모리의 불필요한 낭비도 좀 보인다.

그래서 같은 프로그램을 한번 만들어봤다.

피보나찌 수열의 일반항은 F₀=0, F₁=1 에서 시작하지만, ZFanta 님의 문제를 보면, F₀=1, F₁=2 라고 명시되어있다.
모든 수열을 배열에 담으면 메모리가 아까우니, f1, f2, ft 3개의 변수만 사용한다.
이 중 계산이 이루어지는 두 항이 f1, f2이고, ft는 임시용이다.

#include <stdio.h>

void main(void)
{
    int f1=1, f2=2, ft;
    int iSum=0;    // 합을 저장
    while (f2<4000001)    // 4,000,000 이하 == 4,000,001 미만
    {
        if ((f2 & 1) == 0)    // 짝수인가?
        {
            iSum += f2;
            printf("%d -> %d\n", f2, iSum);
        }
        ft = f1 + f2;
        f1 = f2;    // f2 -> f1
        f2 = ft;    // f1+f2 -> f2
    }
}

그런데, 이 코드는 최적화의 여지가 있다.

1. 피보나찌 수열은 언제나 짝-홀-홀이 반복되는 구조이므로 일일이 홀짝 검사할 필요가 없음
2. while() 루프 끝부분의 다음항을 계산하는 부분은 연산 낭비가 심해보임

그런 부분을 정리해보니 아래와 같은 코드가 나온다.

#include <stdio.h>

void main(void)
{
    int f1=1, f2=2, f3=f1+f2;
    int iSum=0;
    while (f2<4000001)
    {
        iSum += f2;
        printf("%d -> %d\n", f2, iSum);
        // 다음 3개의 항을 구함
        f1 = f2 + f3;
        f2 = f1 + f3;
        f3 = f1 + f2;
    }
}

그런데, 역시 합을 구하는 부분과 다음 3개의 항을 구하는 부분은 좀 더 최적화가 필요해보인다.
그것까지 정리한 코드는 아래와 같다.

#include <stdio.h>

void main(void)
{
    int f1=1, f2=2, f3=f1+f2, iSum=0;
    while (f2<4000001)
    {
        printf("%d -> %d\n", f2, iSum+=f2);
        f3 = f1 + (f2 = (f1 = f2 + f3) + f3);
    }
}

여기서 변수명만 i, j, k, l, m으로 수정하면 알아보기 힘든 코드가 된다. 홍홍
아래처럼.

#include <stdio.h>

void main(void)
{
    int i=1, j=2, k=i+j, l=0;
    while (j<4000001)
    {
        printf("%d -> %d\n", j, l+=j);
        k=i+(j=(i=j+k)+k);    // 뭐 하는 놈이게?
    }
}

실행 결과는 아래와 같다.

합은 4,613,732다.