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

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

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

피보나찌 수열의 일반항은 F0=0, F1=1 에서 시작하지만, ZFanta 님의 문제를 보면, F0=1, F1=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다.



Trackback 0 Comment 18
  1. Favicon of http://minimonk.tistory.com BlogIcon 구차니 2009.06.15 18:00 address edit & delete reply

    전 적절하게 낭비되면서 가독성이 좋은게 좋아요 ㅋㅋ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.06.15 19:31 address edit & delete

      사실, 컴파일러 단에서 최적화를 하기 때문에 너무 무리할 필요는 없을 것 같습니다.
      하지만, 이 코드들에서는 첫번째 코드에 비해 루프가 1/3로 줄어들기 때문에 충분히 가치가 있을 것 같군요. :)

  2. Favicon of http://minimonk.tistory.com BlogIcon 구차니 2009.06.15 19:42 address edit & delete reply

    c 레벨에서 확 주는걸로 보이긴 하지만,
    어셈레벨로 봐야지 얼마나 효율적이 되었을지 알것 같은데..
    어셈은 내공부족이라서 말이죠 ㅋ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.06.15 19:57 address edit & delete

      실제적인 최적화는 2번째에서 다 이루어져있습니다.

      첫번째 코드는 F1, F2를 계속 계산하는 방식이고,
      두번째 이후의 코드는 한 루프에 3개씩 계산하는 방식입니다.

      세번째부터는 C언어 소스 수준에서의 최적화입니다.

  3. pardonk 2009.06.15 21:05 address edit & delete reply

    한국말인데 중국말 같네요. OTLOTL

  4. Favicon of http://zfanta.com BlogIcon  환타 2009.06.17 20:32 address edit & delete reply

    읽기 쉽게 만든다는 게 최적화에는 별 신경을 쓰지 않은 것 같네요.
    다음부터는 더 열심히 해보겠습니다 ㅎㅎ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.06.17 22:07 address edit & delete

      즐프하세요~

  5. JAFO 2009.06.22 01:00 address edit & delete reply

    #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);
    }
    }

    이부분은 최적화 된것이 아닌것 같은데요
    아미도 컴파일러가 이것을 번역을 하면

    #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;
    }
    }

    이렇게 만들어 버릴테니깐요.....

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.06.22 08:56 address edit & delete

      저렇게 무식하게 코드를 쓰는 경우는 (컴파일러에 따라서는) 메모리에 넣지 않고 레지스터 내에서만 처리해주는 경우가 있습니다.
      그런 최적화를 기대하는 거죠.

      하지만... [Writing Solid Code] 같은 책을 보면, 저래봤자 얻을 수 있는 이득은 전혀 없다는 거... ㅋ

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.10 02:01 address edit & delete

      직접 돌려서 확인해보니 백푸로 동일하게 만들어주더군요. You win!

  6. 김우승 2009.09.12 21:26 address edit & delete reply

    사실 f3 = f1 + (f2 = (f1 = f2 + f3) + f3);는 C의 경우에 결과가 정의되지 않는 source 입니다.
    Java의 경우에는 BLUEnLIV 님의 의도대로 동작하지만요.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.14 03:09 address edit & delete

      ISO/IEC 9899:201x에 의하면

      [q]An assignment expression has the value of the left operand after the assignment, but is not an lvalue.[/q]

      라고 되어있는데요...

  7. 김우승 2009.09.14 11:26 address edit & delete reply

    9899:201x 라면 새로 개정준인 초안 말씀이신가요?
    상당히 신식이시네요.

    개정초안을 말씀하신 것 같아 n1362에서 찾아봤습니다.
    말씀하신 문장이 있는 문단의 마지막 두 문장은 다음과 같군요.

    The side effect of updating the stored value of the left operand is sequenced after the value computations of the left and right operands. The evaluations of the operands are unsequenced.

    주어진 수식에서 f1은 두번 등장합니다. 원하시는 결과를 얻을려면 앞의 f1의 평가값(evaluation)이 뒤의 f1이 이루는 부분수식(f1 = f2 + f3)의 평가값과 동일하기 위하여 부분수식의 side effect가 완료된 후에 이루어져야 합니다. 하지만 수식의 피연산자 평가순서는 몇개의 연산자를 제외하고 정해져있지 않기 때문에 앞의 f1을 뒤의 f1의 결과값으로 평가할 것이라고 보장할 수 없습니다.

    위의 답글에서 제가 실수했는데요. Java로 한번 test 해보세요. 다른 결과를 얻으실 수 있을 겁니다. Java의 경우는 기본적으로 왼쪽우선으로 값을 평가하니까요. 그리고 그런 결과는 C에서도 가능한 결과입니다.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.14 14:37 address edit & delete

      제가 제대로 이해했나 모르겠는데, 조금 알 것 같습니다.

      1. 대입문에서 f1이 식과 같이 두 번 등장한 경우는 사실상 정의되어 있지 않다.

      2. 특히, 괄호를 먼저 계산한다고 정의되어있지 않다.

      3. 자바는 아예 왼쪽 우선이다.

      사실 표준은 별 관심 없는 단무지 개발자라 표준을 더 따지긴 힘들고(귀찮고... ^^) 저런 복잡한 식은 안 쓰는 것이 상책이겠군요.
      매번 좋은 답글 감사드립니다.

  8. JAFO 2009.09.15 00:27 address edit & delete reply

    제가 무식해서 인지 몰라도 JAVA이건 C이건 같은 머신에서 동작하는 한, 컴파일러가 삽질하지 않는다면 최적화의 길은 한가지 입니다. 결국 같은 머신에서는 컴파일러가 최적의 솔루션을 찾아 준다면, 그중에 하나는 최소한의 레지스터에 넣고 빼고가 최적 결과가 되는 것이 정상이며, 또 한가지 최적화가 있다면 레지스터를 많이 쓰더라도 캐쉬가 허용하는 범위에서 읽고 쓰고의 연속동작으로 순차적인 메모리 접근성을 갖는다면 그 또한 최적의 속도를 갖게 됩니다.

    다시말해 레지스터가 얼마나 많이 선언되는 지도 최적화의 방법이며, 메모리에서 읽고 쓰고 연산하고 하는 동작이 얼마나 가까운 캐쉬에서 되느냐도 최적화에 중요한 요인으로 작용하는 것 같습니다. 이 것이 속도의 최적화냐 메모리의 최적화냐의 갈림길로, 어떤 방법이 얼마나 속도에 또는 메모리에 좋은 영향을 미치는 지는 사용자의 프로그래밍 실력에 달린 것 같습니다.

    결과적으로 메모리를 많이 쓰더라도 메모리 간의 연관성이 얼마나 가까우냐에 따라서 메모리를 적게 쓰는 프로그램보다 연산 속도가 오히려 빠를 수도 있고 그 반대의 경우도 있다는 겁니다.

    저는 잘 모르겠습니다. 컴파일러에 대한 표준화? 정의? 그런거 잊은지 오래된 것 같습니다.
    같은 표준을 따르는 컴파일러에서도 성능차이가 나고 항상 같은 결과를 보여 줄 것만 같은 컴파일러에서도 배신을 당해온 저에게는 일단 컴파일하고 ASM을 보기전까지는 그 무엇도 믿기 싫습니다. 그냥 지금까지 프로그래밍 했던 기억에 의존할 뿐입니다. 버전을 달리하는 최신의 컴파일러에서도 항상 똑같은 결과를 기대할 수 없듯이.......

    이상 술머고 쓴 답글이라서 좀 글이 어설풀 수 있습니다.
    지적은 겸허이 받아 드리겠습니다.

    • Favicon of http://zockr.tistory.com BlogIcon BLUEnLIVE 2009.09.15 00:54 address edit & delete

      사실, 원론이나 이론의 문제도 중요하지만, 우리가 실무에서 부딛히는 건 언제나 "현실"의 문제이지 않습니까...
      실제로 업무를 할 때는 JAFO 님의 의견에 10000% 동의할 수 밖에 없죠. 언제나 현실은 시궁창... [emo=062]

  9. 김우승 2009.09.18 01:06 address edit & delete reply

    저는 Assembly를 잘 못합니다. 그런데 Assembly는 믿을만한가요?
    우리는 항상 다른 machine을 사용하기 때문에 고급언어가 있는 것 아닌가요?
    지금까지 프로그래밍 했던 기억에 의존하신다는 말씀은 조금 다르긴 하지만 공감하는 바입니다.