Ackermann의 기능은 gcc에서 segfaults

Question

평범 할 것입니다.이 질문과 관련하여 Ackermann very inefficient with Haskell/GHC (필자는 아마도 비합리적으로 나를 짜증나게합니다) 왜 Wilhelm Ackermann의 유명한 기능을 계산할 프로그램이

인지 궁금합니다.

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

int main() { 
    printf("%d\n", ack(4,1)); 
    return 0; 
} 

는 잘 작동하지만 (다른 곳에서 도움) 명백한 최적화를 주어진 인수 (4,2) 주어 졌을 때 - 물론 알고리즘 잔인 - Segmentation fault: 11로 끝나는 :

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

int main() { 
    printf("%d\n", ack(4,2)); 
    return 0; 
} 

만약 내가 com 최적화 프로그램 'if (m == 1) return n+2;'을 실행하면 프로그램은 다른 언어에서와 마찬가지로 계속 실행되지만 동일한 효과는 없습니다. 적어도 5 분의 동작 후에는 그렇지 않습니다. (내가 OS X에서 함께 제공 gcc를 사용하고 있음을 유의하지만, 같은 예와 gcc-4.7.2ideone.com에 일어나고있는 것 같다.)

나는 프로그램을 동의 - [8m41s 후 보정, 않는 것 같습니다] 컴파일 할 자격도 없지만 일반적으로 공포와 언어 흠집이나 컴파일러 오류로 내가 낯 익은 다른 언어로 볼 수있는 세분화 오류가 gcc에 대한 적절한 응답인지 궁금합니다.

Answer 1

두 프로그램 모두 스택이 부족하여 성능이 향상됩니다. 필요한 스택은 매개 변수 'n'에 비례하고 'n'은 빠르게 커집니다. 그래서 아무런 버그도없고 단지 제한된 기계입니다.

재미 있고 속도가 더 빠른 일부 코드를 내 보관 파일에 추가하겠습니다. 또한 'm'이 증가 할 때마다 'n'이 얼마나 빨리 커지는 지 보여줍니다.

typedef unsigned long long N; 
N acker (N m, N n) 
{ 
     while (1) 
     switch (m) 
     { 
     case 0: return n+1U; 
     case 1: return n+2U; 
     case 2: return 2U*(n+1U)+1U; 
     case 3: return (1LLU<<(n+3U))-3U; 
     default: 
       if (n == 0U) 
         n = 1U; 
       else 
         n = acker(m, n-1U); 
       m--; 
       break; 
     } 
     return n+1U; 
}