/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        C A L C U L   D E   L A   F O N C T I O N   D E   A C K E R M A N   E N   E N T I E R  :                                   */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '$xtc/Ackerman.01$c' :                                                                                           */
/*                                                                                                                                   */
/*                    Jean-Francois Colonna (LACTAMME, 19991020120000).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

#include  <stdio.h>

int       ackerman(m,n)
                                        /* La fonction d'Ackerman est une fonction calculable (au sens de Turing), sans etre         */
                                        /* primitive recursive. Les fonctions 'f' de type "primitive recursive" sont definies        */
                                        /* par des formules du type :                                                                */
                                        /*                                                                                           */
                                        /*                  f(m1,m2,...,mk,0)   = g(m1,m2,...,mk)                                    */
                                        /*                  f(m1,m2,...,mk,N+1) = h(m1,m2,...,mk,N,f(m1,m2,...,mk,N))                */
                                        /*                                                                                           */
                                        /* La fonction d'Ackerman croit beaucoup plus vite que toute exponentielle...                */
int       m;
int       n;
          {
          if        (m==0)
                    {
                    return(n+1);
                    }
          else
                    {
                    if        (n==0)
                              {
                              return(ackerman(m-1,1));
                              }
                    else
                              {
                              return(ackerman(m-1,ackerman(m,n-1)));
                              }
                    }
          }

void      main()
          {
          int       NumberOfInputs;
          int       m,n;
                                        /* Aguments de la fonction.                                                                  */

          printf("\n m=");
          NumberOfInputs=scanf("%d",&m);
          printf("\n n=");
          NumberOfInputs=scanf("%d",&n);

          printf("\n Ackerman(%d,%d) = %d\n",m,n,ackerman(m,n));
                                        /* Quelques resultats de 'time' pour 'ackerman(4,1)' (soit m=4 et n=1) :                     */
                                        /*                                                                                           */
                                        /*                  CMAP27    cc        454.720u  0.400s 7:40.15 98.9%   0+0k 0+0io 84pf+0w  */
                                        /*                  CMAP27    cc -O3    400.100u  0.530s 6:52.56 97.1%   0+0k 0+0io 84pf+0w  */
                                        /*                                                                                           */
                                        /*                  LACT27    cc -O3    465.5u    2.0s 8:08 95%          0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /*                  LACT29    cc        775.4u    0.4s 13:07 98%         0+0k 0+0io 0pf+0w   */
                                        /*                  LACT29    cc -O3    566.7u    0.3s 9:37 98%          0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /* Avantage a 'CMAP27' et a 'LACT27' sur 'LACT29' !                                          */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20041013143528 :                                                        */
                                        /*                                                                                           */
                                        /*                  LACT15    cc        109.020u  0.010s 1:51.19 98.0%   0+0k 0+0io 87pf+0w  */
                                        /*                  LACT15    cc -O3    107.410u  0.100s 1:49.41 98.2%   0+0k 0+0io 87pf+0w  */
                                        /*                                                                                           */
                                        /*                  LACT16    cc         51.450u  0.010s 0:53.07 96.9%   0+0k 0+0io 87pf+0w  */
                                        /*                  LACT16    cc -O3     38.700u  0.040s 0:41.02 94.4%   0+0k 0+0io 87pf+0w  */
                                        /*                                                                                           */
                                        /*                  sumix11   cc        user=0m35.510s sys=0m0.010s                          */
                                        /*                  sumix11   cc -O3    user=0m22.430s sys=0m0.020s                          */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20041208092321 :                                                        */
                                        /*                                                                                           */
                                        /*                  LACT17    cc         41.413u 0.008s 0:44.66 92.7%    0+0k 0+0io 0pf+0w   */
                                        /*                  LACT17    cc -O3      9.754u 0.001s 0:11.55 84.4%    0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20120104173549 :                                                        */
                                        /*                                                                                           */
                                        /*                  LACT18    $Cc        11.204u 0.000s 0:16.86 66.4%    0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20120104135847 :                                                        */
                                        /*                                                                                           */
                                        /*                  LACT19    $Cc         4.930u 0.000s 0:06.66 74.0%    0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20160811164523 :                                                        */
                                        /*                                                                                           */
                                        /*                  LACT19    $Cc         3.300u 0.010s 4:08.60 1.3%     0+0k 0+0io 0pf+0w   */
                                        /*                  LACT1A    $Cc         2.184u 0.004s 3:48.42 0.9%     0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20210913082256 (ATTENTION : '$Cc' contient '-O3' sur '$LACT1B') :       */
                                        /*                                                                                           */
                                        /*                  LACT19    $Cc         3.340u 0.000s 0:05.69 58.6%    0+0k 0+0io 0pf+0w   */
                                        /*                  LACT1B    $Cc        11.557u 0.000s 0:14.07 82.0%    0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
                                        /*                                                                                           */
                                        /* Nouveaux tests le 20211208115822 (ATTENTION : '$Cc' contient '-O1' sur '$LACT1B' et les   */
                                        /* tests sur '$LACT1B' ayant ete faits sur '/mnt/DisqueDur/home/colonna/tests/c.D', puis     */
                                        /* sur '/home/colonna/tests/c.D' -apres la bascule 'v $Fdirectories 20211208110726'-) :      */
                                        /*                                                                                           */
                                        /*                  LACT19    $Cc         3.300u 0.010s 0:05.34 61.9%    0+0k 0+0io 0pf+0w   */
                                        /*                  LACT1B    $Cc        11.577u 0.003s 0:13.26 87.2%    0+0k 0+0io 0pf+0w   */
                                        /*                                                                                           */
          }



Copyright © Jean-François Colonna, 2021-2023.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / École polytechnique, Institut Polytechnique de Paris, 2021-2023.