아커만 함수 (Ackermann Function)

프로그래밍/프로그래밍 메모장 2007/03/30 11:12
아커만 함수는 피보나치 함수와 마찬가지로 컴퓨터 과학분야에서 쓰이는
수학함수중의 하나입니다.
주로 벤치마크에서 많이 쓰입니다.

이 함수는 다음과 같이 정의됩니다.

A(m,n) ->  ,   n + 1                      ( m = 0  일때)
               ,   A(m-1 , 1)               ( m > 0 이고 n = 0 일때 )
               ,   A(m-1 , A(m, n-1))   ( m > 0 이고 n > 0 일때)

이 함수가 왜 벤치마크에서 이용되는지는 이 함수의 특성에 있습니다.
이 함수는 아주 적은 수를 넣어도 기하급수적인 리커젼(recursion):재귀호출 을
일으켜 내는 함수
이기 때문입니다.

새로산 컴퓨터나 새로운 언어 또는 컴파일러 등등을 테스트하기 위하여
간단하게 함수를 작성하여 돌려보면 (물론 기준이 될 비교의 대상이 있어야 하겠으니
최소한 두 시스템에서 돌려보아야 하겠습니다.)

대략적으로 얼마만큼 성능이 좋은지 가늠해볼 수 있습니다.

함수정의가 너무 간단하기 때문에 문법만 알고 재귀함수를 지원하는 언어라면
아주 쉽게 모듈을 작성할 수 있습니다.

C  코드의 예입니다.

int Ack(int m, int n)
{
  if (m == 0) return n+1;
  if (n == 0) return Ack(m-1 , 1);
  return Ack(m-1 , Ack(m , n-1));
}

주의!. m이 4를 넘지 않도록 주의합시다.
     웬만한 시스템과 컴파일러에서는 Ack(4,3)만 넣어도 recursion depth 를
     초과할 수 있습니다. 계산시간은 예측불가..

    Ack(4,1) 정도를 추천.. 계산값은 65533  계산시간은 시스템에 따라 많이 틀리겠지만
  2 - 3 분 정도입니다.
top

Trackback Address :: http://xevious7.com/trackback/226

  1. Tracked from My Nate BLOG 2007/04/17 16:06 DELETE

    Subject: 얼리어댑터 블로깅

    마이네이트 늘보라에서 선정한 얼리어댑터와 관련한 추천 블로그입니다.(http://my.nate.com) 1. 빠른 맥정보, 매킨토시 이야기 rss-http://weenybee.tistory.com/rss url-http://weenybee.tistory.com/2. ..
  1. 동우리 2007/07/19 16:03 MODIFY/DELETE REPLY

    덕분에 AIX 와 Linux 에서 속도 차이 나는 이유를 찾았습니다. ^_^

  2. ㅇㅇ 2015/11/30 17:54 MODIFY/DELETE REPLY

    함수 정의에서 n+1 조건이 (m=0 일때) 아닌가요?

  3. xevious7 2015/11/30 22:36 MODIFY/DELETE REPLY

    네 m=0 일때 n+1 입니다. 함수에 구현된 것 처럼 위 본문은 오타가 쭉 있었네요. 감사합니다.

Write a comment