L'andamento dell'automa bidimensionale è meglio esplicato da un diagramma:

<table><tr><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr></table>

<table><tr><td>1</td><td>5</td><td>3</td></tr><tr><td>4</td><td>2</td><td>6</td></tr></table>

Si può osservare dalla figura che la forma dell'intorno dell'automa bidimensionale è diagonale (di qui il nome della mappa). □

## 8.4 Reversibilità degli automi bidimensionali

Abbiamo visto nella sezione 7.2 che esiste un algoritmo per determinare la reversibilità di una regola locale su automi unidimensionali di lunghezza infinita. I creatori dell'algoritmo avvertono tuttavia che "il loro risultato è limitato a stringhe ad una dimensione. Sebbene le tecniche impiegate si possano in principio estendere a più dimensioni, sembra che in pratica sia molto difficile implementarle. È estremamente probabile che una generalizzazione pluridimensionale richieda un approccio completamente diverso<fnref n="22" />. Jarkko Kari ha poi dimostrato (cfr. [Kar91]) che la reversibilità di automi di dimensione 2 con intorno di Moore non è decidibile, ovvero che non esiste un algoritmo<fnref n="23" /> in grado di decidere se una data regola locale sia o non sia iniettiva. La dimostrazione di Kari si basa sul "problema della quadrettatura del piano<fnref n="24" />. È dato un numero finito di quadrati di lato unitario con i bordi colorati. Disponiamo di infinite copie di questi quadrati ma non possiamo

<footnote n="22">²²Cfr. [AP72], pag. 449.</footnote>

<footnote n="23">²³Per definizione un algoritmo è una procedura di un numero finito di passi.</footnote>

<footnote n="24">²⁴Tradotto da *tiling problem*.</footnote>
ruotarli. Una quadrettatura è valida se per ogni coppia di quadrati contigui il bordo comune ha lo stesso colore. Si deve decidere se con i quadrati dati è possibile quadrettare tutto il piano. R. Berger ha provato nel 1966 ([Ber66]) che il problema non è decidibile, e Kari ha dimostrato che il problema della decidibilità della reversibilità di un automa bidimensionale con intorno di Moore è equivalente al problema della quadrettatura del piano. La dimostrazione si basa sul fatto che con l'insieme finito di quadrati unitari è possibile costruire un particolare automa cellulare bidimensionale che è reversibile se e solo se il piano può essere quadrettato.
# 9 Conclusione

Fra le varie tematiche affrontate in questa tesi, tre principalmente sono quelle che abbisognano di ulteriore ricerca e sviluppo.

1. Le considerazioni riguardanti la struttura del gruppo $G^n(R)$ (vedi capitolo 5 a pagina 67). In particolare si sono trovate (ahimé troppo tardi per essere incluse in questa sede) delle convenienti rappresentazioni feldesi dei gruppi $G_i$ di cui $G^n(R)$ è il prodotto diretto; inoltre sembra che ci possano essere diversi legami con la teoria dei codici correttori d'errore.

2. La “questione aperta di cui si parla a pagina 96. Purtroppo la dimostrazione di Jarkko Kari è costruita *ad hoc* per la regola “180. Sarebbe opportuno dimostrare l’ipotesi di invertibilità su lunghezze dispari in modo indipendente dalla struttura “interna della trasformazione, così da applicarla anche alle altre trasformazioni menzionate sopra.

3. L'ultimo capitolo, e in particolare i concetti di mappe transdimensionali, vanno approfonditi molto maggiormente.

È inoltre evidente dal lavoro svolto che trattare la non linearità con metodi combinatorici è sempre difficile e non sempre fruttuoso. Speriamo di avere comunque mostrato attraverso le parti di calcolo numerico che un tentativo in questo senso non deve necessariamente restare legato al limbo della teoria inapplicabile.
A Appendice: Il Programma CAInvPrm

/*
Name: CAInvPrm
Author: Leo Liberti
Purpose: to find the inverse of a local CA rule (if it exists)
with the permutation method (see dissertation)
Source: MS Visual C++ 4.0
History:
21/06/97 1.0 works.
26/06/97 1.1 Added APIL support and an option
for testing all transformations
with a FOR clause.
26/06/97 1.2 rewritten cmd line parser and added
option for simpler output
28/06/97 1.3 added -nodec flag and fixed some
parser bugs. Also changed the
way -all flag cycles through the
transf (now much quicker, w/o APIL)
30/06/97 1.4 added -infile: option and changed
the way -simple outputs, so can take
a redirection with -simple as an infile
17/08/97 1.5 added -complex flag
Notes: (unsigned)
[RI, r_0, r_1, n, *vectors, *localrules ... int
[RI, n, *globairules, [*localrules|, [*globairules| ... long int
vectors, or numbers, are in form (v_1, \ldots, v_n);
global rules are in form (v_0, \ldots, v_{|R|}^n - 1) (different from
dissertation standards); local rules as in thesis
EXIT CODES: 0 - all ok.
1 - not enough memory.
2 - r_0 + r_1 + 1 > n.
3 - -v flag set with -all flag
4 - other command line mistake
5 - can't open infile for input
6 - infile is 0 bytes long
7 - infile doesn't contain transformations
8 - could not read transformation from infile
9 - infile line too long
10 - etc
N.B. This program relies on APIL.H and APIL.CPP (see later in
this appendix).
*/
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include "apil.h"
#define APIL
#ifdef MESG
#ifdef
#define MESG "CAInvPrm 1.5 (Using perms. & APIL 1) - Leo Liberti 1997\n"
#ifdef TRUE
#define TRUE 1
#endif
#ifdef FALSE
#define FALSE 0
#endif
#ifdef PLUS
#define PLUS 1
#endif
#ifdef MINUS
#define MINUS -1
#endif
#ifdef BASE
#define BASE 10
#endif
#ifdef ARGS
#ifdef ARGs
#define ARGs 5
#ifdef FNLEN
#define FNLEN 80
#endif
#ifdef BUFLEN
#define BUFLEN 160
#endif
/* ---------- begin function list ---------- */
unsigned int mod(long a, unsigned int n)
{
    unsigned int a3;
    long a1, a2;
    a1 = a % (long) n;
    if (a1 < 0)
        a2 = n + a1;
    else
        a2 = a1;
    a3 = (unsigned int) a2;
    return a3;
}

/* Following functions already defined in apil.cpp; only read them in
if APIL is not defined */
#ifndef APIL
unsigned long power(unsigned long a, unsigned long n)
{
    unsigned long u, v, t;

    u = n;
    v = 1;
    t = a;

    while (u != 0)
    {
        if (u % 2 == 1)
        {
            v = v * t;
        }
        t = t * t;
        u = u / 2;
    }
}
```c
}
    return v;
}

int sgn(long a)
{
    if(a >= 0)
        return (int) PLUS;
    else
        return (int) MINUS;
}

char int2char(unsigned short int p)
{
    return p + '0';
}

void check_char(char *t, unsigned long c)
{
    if(strlen(t) > c)
        *(t + c) = '\0';
    if(!t)
    {
        // error 2 : no memory
        fprintf(stderr, "CAInvPrm: check_char: ERROR: Not enough memory.\n");
        exit(1);
    }
}

char *itoa(unsigned long p)
{
    unsigned long digits, i;
    char *ret;
    if(p == 0)
        digits = 1;
    else
        digits = (unsigned long) floor(log10((double) p)) + 1;
    // ret = new char[digits];
    ret = (char *) mallocemy digits);
    check_char(ret, digits);
    for(i = 0; i < digits; i++)
        *(ret + digits - i - 1) = int2char((p / \ powerBasE, (unsigned long) i)) % BASE);
    return ret;
}

#endif

/* end of functions defined in apil.cpp */

/* this is for vectors */
unsigned int *dec2vect(unsigned int R, unsigned long veclen, \ unsigned long s)
{
    unsigned long int i;
    unsigned int *v;
    v = (unsigned int *) malloca veclen * sizeof(int);
    if(!v)
    {
        fprintf(stderr, "CAInvPrm: dec2vect: ERROR: Not enough memory.\n");
        exit(1);
    }
    for(i = 1; i <= veclen; i++)
        *(v + i - 1) = (s / power(R, veclen - i)) % R;
    return v;
}

/* this is for rules */
unsigned int *dec2local(unsigned int R, unsigned long veclen, \ unsigned long s)
{
    unsigned long int i;
    unsigned int *v;
    v = (unsigned int *) malloca veclen * sizeof(int);
    if(!v)
    {
        fprintf(stderr, "CAInvPrm: dec2local: ERROR: Not enough memory.\n");
        exit(1);
    }
    for(i = 0; i < veclen; i++)
        *(v + veclen - i - 1) = (s / power(R, i)) % R;
    return v;
}

// ... with APIL support
unsigned int *dec2local(unsigned int R, unsigned long veclen, api s)
{
    api api_tmp;
    unsigned long int i, tmp;
    unsigned int *v, t;
    v = (unsigned int *) malloca veclen * sizeof(int);
    if(!v)
    {
        fprintf(stderr, "CAInvPrm: dec2local (APIL): ERROR: Not enough memory.\n");
        exit(1);
    }
    tmp = 1;
    for(i = 0; i < veclen; i++)
    {
        api_tmp = (s / tmp) % R;
        t = atoi(API_tmp API2char());
        *(v + veclen - i - 1) = t;
        tmp = tmp * R;
    }
```
```c
        return v;
    }
    // Transform a local in a decimal rep
    unsigned long local2dec(unsigned int R, unsigned long veclen, \
                             unsigned int *localrule)
    {
        unsigned long i, dec, tmp;
        dec = 0;
        tmp = 1;
        for(i = 0; i < veclen; i++)
        {
            dec = dec + *(localrule + veclen - i - 1) * tmp;
            tmp = tmp * R;
        }
        return dec;
    }
    // ...with APIL support
    api local2dec_api(unsigned int R, unsigned long veclen, \
                       unsigned int *localrule)
    {
        unsigned long i;
        api dec, tmp;
        dec = 0;
        tmp = 1;
        for(i = 0; i < veclen; i++)
        {
            dec = dec + tmp *(*(localrule + veclen - i - 1));
            tmp = tmp * R;
        }
        return dec;
    }
    unsigned long apply_rule(unsigned int R, unsigned int n, \
                             unsigned int r0, unsigned int r1, \
                             unsigned int *localrule, \
                             unsigned long vector)
    {
        unsigned int i, j, l, d, m;
        unsigned int *v;
        unsigned long t, td, c, c1; //p;
        long tmp;
        i = 0;
        t = power(R, n);
        d = r0 + r1 + 1;
        td = power(R, d);
        v = dec2vect(R, n, vector);
        c = 0;
        for(i = 0; i < n; i++)
        {
            l = n - i - 1;
            c1 = 0;
            for(j = 0; j < d; j++)
            {
                tmp = (long) l - (long) r0 + (long) j;
                m = mod(tmp, n);
                /* Per la definizione di mod()
                 vedi piu' sotto */
                c1 = c1 +(*(v + m)) * power(R, d - 1 - j);
            }
            // p = (rule / power(R, c1)) % R;
            c = c +(*(localrule + td - c1 - 1)) * power(R, i);
        }
        return c;
    }
    unsigned int *BT2AT(unsigned int R, unsigned int n, \
                         unsigned int r0, unsigned int r1, \
                         unsigned int *psi)
    {
        unsigned int d, i, j, l, t1, t2, t3;
        unsigned int *phi;
        d = r0 + r1 + 1;
        t1 = power(R, n);
        t2 = power(R, d);
        t3 = power(R, n - d);
        phi = (unsigned int *) malloc(t1 * sizeof(int));
        for(i = 0; i < t2; i++)
        {
            l = i * t3;
            for(j = 0; j < t3; j++)
                *(phi + l + j) = *(psi + i);
        }
        return phi;
    }
    unsigned int *AT2BT(unsigned int R, unsigned int n, \
                         unsigned int r0, unsigned int r1, \
                         unsigned int *phi)
    {
        unsigned int d, i, t1, t2, t3;
        unsigned int *psi;
        d = r0 + r1 + 1;
        t1 = power(R, n);
        t2 = power(R, d);
        t3 = power(R, n - d);
        psi = (unsigned int *) malloc(t2 * sizeof(int));
        for(i = 0; i < t2; i++)
        {
            *(psi + i) = *(phi + i * t3);
```
```c
}
    return psi;
}

unsigned long *local2global(unsigned int R, unsigned int n, \
                             unsigned int r0, unsigned int r1, \
                             unsigned int *localrule)
{
    unsigned long i, t, *globalrule;
    t = power(R, n);
    globalrule = (unsigned long *) malloc(t * sizeof(long int));
    if(!globalrule)
    {
        fprintf(stderr, "CAInvPrm: local2global: ERROR: Not enough memory.\n");
        exit(1);
    }
    for(i = 0; i < t; i++)
        *(globalrule + i) = apply_rule(R, n, r0, r1, localrule, i);
    return globalrule;
}

/* this function also attempts to find a shortened version of
 * the local rule corresponding to *globalrule and sets r1 to
 * the correct value (so if r1 = n - r0 - 1 it means there is
 * no shortened version) */
unsigned int *global2local(unsigned int R, unsigned int n, \
                             unsigned int r0, unsigned int *r1, \
                             unsigned long *globalrule)
{
    unsigned short flag;
    unsigned int *localrule, *shortlocal, l, k;
    unsigned long t, i, j, d, y, z1, z2;
    double x;

    t = power(R, n);
    localrule = (unsigned int *) malloc(t * sizeof(unsigned int));
    /* find the long version of the local rule */
    for(i = 0; i < t; i++)
        *(localrule + t - i - 1) = (*globalrule + i) / power(R, n - r0 - 1) % R;
    /* see if it can be shortened */
    flag = TRUE;
    /* find a possible "n - d" */
    l = *localrule;
    i = 0;
    while(*(localrule + i + 1) == l)
        i++;
    if(i > 1)
    {
        x = log((double) i) / log((double) R);
        y = (unsigned long) floor(x + 0.5);
        /* test if n-d=y is in \mathbb{Z} */
        z1 = power(R, y);
        if(z1 == i)
        {
            /* test if n-d=y is all right for the other positions */
            d = n - y;
            /* check that d >= 2 */
            if(d < 3 && n > 2)
            {
                d = 3;
                y = n - d;
                z1 = power(R, y);
            }
            else if(d == 1 && n == 2)
            {
                d = 2;
                y = 1;
                z1 = R;
            }
            z2 = power(R, d);
            *r1 = d - r0 - 1;
            for(j = 0; j < z2; j++)
            {
                k = *(localrule + j * z1);
                for(i = 1; i < z1; i++)
                {
                    if(*(localrule + j * z1 + i) != k)
                    {
                        flag = FALSE;
                        break;
                    }
                }
                if.flag == FALSE)
                    break;
            }
            if.flag == TRUE)
                shortlocal = AT2BT(R, n, r0, *r1, localrule);
            else
            {
                *r1 = n - r0 - 1;
                shortlocal = localrule;
            }
        }
        else
        {
            *r1 = n - r0 - 1;
            shortlocal = localrule;
        }
    }
    else
    {
        *r1 = n - r0 - 1;
        shortlocal = localrule;
    }
    return shortlocal;
}
```
```c
}
void local_out(unsigned long loc_len, unsigned int *localrule, FILE *fp)
{
    unsigned long i;
    fprintf("(", fp);
    for(i = 0; i < loc_len - 1; i++)
        fprintf fp, "%u", *(localrule + i));
    fprintf fp, "%u", *(localrule + loc_len - 1));
}

/* verify that prm is a permutation, and if it is, find the inverse.
 * if it isn't, return an array with zero entries */
unsigned long *prm inverse(unsigned long prm_len, unsigned long *prm)
{
    unsigned short int *checklist;
    unsigned long int i, *inv;
    int flag;
    checklist = (unsigned short *) malloc(prm_len * sizeof(short int));
    if(!checklist)
        fprintf(stderr, "CAInvPrm: prm Montgomery error: Not enough memory.
");
    exit(1);
}

inv = (unsigned long *) malloc(prm_len * sizeof(long int));
if(!inv)
    fprintf(stderr, "CAInvPrm: prm inverse: ERROR: Not enough memory.
");
exit(1);
}

flag = TRUE;
for(i = 0; i < prm_len; i++)
{
    (*(checklist + i)) = 0;
    (*(*inv + i)) = 0;
}

for(i = 0; i < prm_len; i++)
{
    if(++(*(*checklist + *(*(prm + i)))) > 1)
    {
        flag = FALSE;
        break;
    }
}

free(checklist);
/*
// the simplest response is the quickest!
if flag == TRUE
    *inv = 1;
*/
if flag == TRUE
    for(i = 0; i < prm_len; i++)
        *(*inv + *(*prm + i)) = i;
return inv;
}

/* careful: if outputting in cycle format (cycleflag == TRUE)
 * and prm is not a permutation, there is an infinite loop */
void prm_out(unsigned int R, unsigned long prm_len, unsigned long *prm,
    FILE *fp, short int cycleflag, unsigned int complexflag)
{
    unsigned long i, j, jsav, k, l;
    unsigned short *checklist;
    unsigned int length;
    char str[80], *baseNum;
    if(complexflag == TRUE)
    {
        length = (unsigned int) floor(log((double) prm_len) / log((double) R) + 0.5);
        baseNum = (char *) malloc(length * sizeof(char));
        check_char(baseNum, length);
    }
    if(cycleflag == TRUE)
    {
        checklist = (unsigned short int *) malloc(prm_len * sizeof(short int));
        for(i = 0; i < prm_len; i++)
            *(*checklist + i) = 0;
        i = 0;
        while(*(*prm + i) == i)
        {
            (*(*checklist + i))++;
            i++;
            if(i == prm_len)
                break;
        }
        if(i == prm_len)
            fprintf("(1)", fp);
    } else
    {
        /* start finding cycles */
        j = 1;
        for(;;)
        {
            /* follow through a cycle */
            for(k = 0; k++);
            {
                if(k > 0)
                {
                    if(complexflag == FALSE)
                        fprintf(itoa(j), fp);
                } else
```
```c
{
    for(l = 1; l <= length; l++)
        *(baseNum + l - 1) = int2char((j / power(R, length - l)) % R);
    fputs(baseNum, fp);
}

{(checklist + j))++;
jsav = j;
j = *(prm + jsav);
if(j == i)
{
    if(k > 0)
    {
        if(complexflag == FALSE)
            fputs("", fp);
        else
            fputs("\n", fp);
    }
    break;
}
else
{
    if(k == 0)
    {
        strcpy(str, "(");
        if(complexflag == FALSE)
            fputs(strcat(str, itoa.jsav)), fp);
        else
        {
            for(l = 1; l <= length; l++)
                *(baseNum + l - 1) = int2char((jsav / power(R, length - l)) % R);
            fputs("\n", fp);
            fputs(strcat(str, baseNum), fp);
        }
    }
    fputs("", fp);
}
}

/* search for an unused number */
j = 0;
while(*(checklist + j) > 0)
{
    j++;
    if(j > prvq_len - 1)
        break;
}

/* check if there are any */
if(j == prvq_len)
    break;

/* there are some; start again with new cycle */
i = j;
}
}
free(checklist);
}
else
{
    fputs("(", fp);
    for(i = 0; i < prvq_len - 1; i++)
    {
        fputs(itoa(*(prm + i)), fp);
        fputs("", fp);
    }
    fputs(itoa(*(prm + prvq_len - 1)), fp);
    fputs("", fp);
}
}

void help()
{
    fprintf(stderr, MESG);
    printf(" This program finds the inverse (if possible) of cellular\n");
    printf(" automata transformations expressed in decimal or local\n");
    printf(" representation (see relevant paper for details). Output is\n");
    printf(" appended both to stdout and to the file CAInvPrm.log. Usage:\n");
    printf("\n [drive:\\dir\\]CAInvPrm [options] R n r0 r1 [sigma]\n\n");
    printf(" where R is the size of the ring of interest, n is the length of\n");
    printf(" cellular automata, r0 is the left radius, r1 is the right radius\n");
    printf(" sigma is the decimal representation of the transformation to invert\n");
    printf(" Options: -local program asks for local representation; argument sigma\n");
    printf(" is then NOT required. This option cannot be used with -all\n");
    printf(" -all program tests all transformations of (\\cal B)_{r_0,r_1}^n(R)\n");
    printf(" this option cannot be used with either -local or -infile\n");
    printf(" -simple output is as follows:\ntransformation being tested\n if it\n");
    printf(" is invertible, nothing if it isn't\n");
    printf(" -complex decimal representations is suppressed from cyclic\n");
    printf(" representations of permutations\n");
    printf(" -nodec program doesn't output any decimal representation;\n");
    printf(" useful with -all, to avoid losing time with conversions\n");
    printf(" -nostdout doesn't output to stdout, only to log file. This option\n");
    printf(" saves time by not calling screen routines\n");
    printf(" -outfile:<file> sets a name for the log file. Default is\n");
    printf(" CAInvPrm.log\n");
    printf(" -infile:<file> sets a name for an input file. Each line of the\n");
    printf(" file must contain a decimal or local rep. of a transf\n");
    printf(" This option cannot be used with either -all or -local\n\n");
}
```

```c
int main(int argc, char *argv[])
{
    api_api_sig, api_inv; // api_counter, api_limit, api_R;
```
```c
// check informatflag
if(infileflag == TRUE)
{
    // initialize sigm
    if((g = fopen(infile, "r")) == NULL)
    {
        fprintf(stderr, "CAInvPrm: main: ERROR: Can't open %s for input.\n", informat);
        exit(5);
    }
    else
    {
        if(fprintf(g, "%c", &c) == EOF) // deal with remes and etc
        {
            fprintf(stderr, "CAInvPrm: main: ERROR: %s is 0 bytes long.\n", informat);
            exit(6);
        }
        while(c != ' (' && (c < '0' || c > '9'))
        {
            while(c != '\n')
            {
                if(fprintf(g, "%c", &c) == EOF)
                {
                    fprintf(stderr, "CAInvPrm: main: ERROR: %s does not contain transformations.\n", informat);
                    exit(7);
                }
                if(fprintf(g, "%c", &c) == EOF)
                {
                    fprintf(stderr, "CAInvPrm: main: ERROR: %s does not contain transformations.\n", informat);
                    exit(7);
                }
            }
            if(c == '(') // local reps
            {
                for(i = 0; i < td - 1; i++)
                {
                    if(fprintf(g, "%u", &int_buffer) == EOF)
                    {
                        fprintf(stderr, "CAInvPrm: main: ERROR: Could not read transformation from %s.\n", informat);
                        exit(8);
                    }
                    else
                        *(sigm + i) = int_buffer;
                }
                if(fprintf(g, "%u", &int_buffer) == EOF)
                {
                    fprintf(stderr, "CAInvPrm: main: ERROR: Could not read transformation from %s.\n", informat);
                    exit(8);
                }
                else
                    *(sigm + td - 1) = int_buffer;
                if(nodecflag == FALSE)
                {
                    api_sig = local2dec_api(R, td, sigm);
                    sig = NULL;
                    if(API_SIG <= longlimit)
                    {
                        sig = atol(API_SIG API2CHAR());
                        api_sig = 0;
                    }
                }
            }
            else // decimal reps
            {
                i = 0;
                while(c != '\n' && c != EOF)
                {
                    buffer[i] = c;
                    i++;
                    if(i >= BUFLEN)
                    {
                        fprintf(stderr, "CAInvPrm: main: ERROR: %s - line too long.\n", informat);
                        exit(9);
                    }
                    fprintf(g, "%c", &c);
                }
                buffer[i] = '\0';
                api_sig = buffer;
                sig = NULL;
                if(API_SIG <= longlimit)
                {
                    sig = atol(buffer);
                    api_sig = 0;
                }
                if(sig == NULL)
                    sig = dec2local(R, td, api_sig);
                else
                    sig = dec2local(R, td, sig);
            }
        }
    }
}

// initialize loop
// try opening the log file
f = fopen(alternatefile, "a+");
fprintf.stdout, MESG);
fprintf(stderr, "\nCalculating inverses of transformations in B_(%u,%u)~%u(Z_%u):\n", r0, r1, n, R);
if(f != NULL)
{
    fprintf(f, MESG);
    fprintf(f, "\nCalculating inverses of transformations in B_(%u,%u)~%u(Z_%u):\n", r0, r1, n, R);
}

 ritmp = (unsigned int *) malloc(sizeof(unsigned int));
 invflag = FALSE;
 stopflag = FALSE;
```
```c
while(stopflag == FALSE)
{
    // do all the work!
    sigma = local2global(R, n, r0, r1, sigm);
    tau = prm_inverse(tn, sigma);
    // check simpleflag
    if(simpleflag == TRUE)
    {
        // simplest things are the quickest!
        if(nodecflag == FALSE)
        {
            if(sig == NULL)
                just4output = api_sig_api2char();
            else
                just4output = itoa(sig);
            if(*tau != *(tau + 1))
            {
                if(nostdoutflag == FALSE)
                    fprintf(stderr, "%s\n", just4output);
                if(f != NULL)
                    fprintf(f, "%s\n", just4output);
                invflag = TRUE;
            }
        }
        else
        {
            if(*tau != *(tau + 1))
            {
                if(nostdoutflag == FALSE)
                {
                    local_out(td, sigm, stdout);
                    fprintf(stderr, "%n");
                }
                if(f != NULL)
                {
                    local_out(td, sigm, f);
                    fprintf(f, "%n");
                }
                invflag = TRUE;
            }
        }
        else
        {
            // complex stdout output
            if(*tau != *(tau + 1))
            {
                *r1tmp = r1;
                ta = global2local(R, n, r0, r1tmp, tau);
                tdtmp = power(R, r0 + *r1tmp + 1);
                invflag = TRUE;
            }
            if(nostdoutflag == FALSE)
            {
                // output to stdout
                fputs("*************************** \n", stdout);
                // fputs(MESG, stdout);
                // fprintf(stderr, "\nCalculating inverse of transformation in B_(%u,%u)~%u(Z_%u):\n\n", r0, r1, n, R);
                if(nodecflag == FALSE)
                {
                    if(sig != NULL)
                        fprintf(stderr, " Decimal representation: %lu\n", sig);
                    else
                        fprintf(stderr, " Decimal representation: %s\n", api_sig_api2char());
                }
                fputs(" Local representation: ", stdout);
                local_out(td, sigm, stdout);
                fputs("\n Global representation: ", stdout);
                prm_out(R, tn, sigma, stdout, FALSE, complexflag);
                if(*tau != *(tau + 1))
                {
                    fputs("\n Global representation (cycles): ", stdout);
                    prm_out(R, tn, sigma, stdout, TRUE, complexflag);
                    fputs("\n\nFound Inverse: \n\n", stdout);
                    api_inv = local2dec_api(R, tdtmp, ta);
                    if(nodecflag == FALSE)
                        fprintf(stderr, " Decimal representation: %s", api_inv_api2char());
                    fprintf(stderr, "\n Local representation with r_0=%u, r_1=%u: ", r0, *r1tmp);
                    local_out(tdtmp, ta, stdout);
                    fputs("\n Global representation: ", stdout);
                    prm_out(R, tn, tau, stdout, FALSE, complexflag);
                    fputs("\n Global representation (cycles): ", stdout);
                    prm_out(R, tn, tau, stdout, TRUE, complexflag);
                }
                else
                {
                    fputs("\n\nTransformation is not invertible", stdout);
                    fputs("\n*************************** \n", stdout);
                }
                if(f != NULL)
                {
                    fputs("*************************** \n", f);
                    // fprintf(f, MESG);
                    // fprintf(f, "\nCalculating inverse of transformation in B_(%u,%u)~%u(Z_%u):\n\n", r0, r1, n, R);
                    if(nodecflag == FALSE)
                    {
                        if(sig != NULL)
                            fprintf(f, " Decimal representation: %lu\n", sig);
                        else
                            fprintf(f, " Decimal representation: %s\n", api_sig_api2char());
                    }
                    fputs(" Local representation: ", f);
                    local_out(td, sigm, f);
```
```c
fputs("\n Global representation: ", f);
prm_out(R, tn, sigma, f, FALSE, complexflag);
if(*tau != *(tau + 1))
{
    fputs("\n Global representation (cycles): ", f);
    prm_out(R, tn, sigma, f, TRUE, complexflag);
    fputs("\n\nFound Inverse: \n\n", f);
    // api_inv = local2dec_api(R, tdtmp, ta);
    if(nodecflag == FALSE)
        fprintf(f, " Decimal representation: %s", api_inv_api2char());
        fprintf(f, "\n Local representation with r_0=%u, r_i=%u: ", r0, *ritmp);
    local_out tdtmp, ta, f);
    fputs("\n Global representation: ", f);
    prm_out(R, tn, tau, f, FALSE, complexflag);
    fputs("\n Global representation (cycles): ", f);
    prm_out(R, tn, tau, f, TRUE, complexflag);
}
else
    fputs("\n\nTransformation is not invertible", f);
    fputs("\n****************************\n", f);
}
}
// now if -all is set, increase sigm, otherwise check -infile
if(allflag == TRUE)
{
    counter = 1;
    while(*(sigm + td - counter) == R - 1)
    {
        if(counter == td)
        {
            stopflag = TRUE;
            break;
        }
        *(sigm + td - counter) = 0;
        counter++;
    }
    if(stopflag == FALSE)
    {
        (*(sigm + td - counter))++;
        if(nodecflag == FALSE)
            api_sig = local2dec_api(R, td, sigm);
    }
    else if(infileflag == TRUE) // check infileflag, else exit
    {
        if(fscnf(g, "%c", &c) == EOF) // normal end of file, exit
        {
            stopflag = TRUE;
        }
        if(stopflag == FALSE)
        {
            while(c != '(' && (c < '0' || c > '9'))
            {
                while(c != '\n')
                {
                    if(fscnf(g, "%c", &c) == EOF)
                    {
                        stopflag = TRUE;
                        break; // another normal termination
                    }
                }
                if(fscnf(g, "%c", &c) == EOF)
                {
                    stopflag = TRUE;
                    break; // yet another normal termination
                }
            }
            if(stopflag == FALSE)
            {
                if(c == '(') // local reps
                {
                    for(i = 0; i < td - 1; i++)
                    {
                        if(fscnf(g, "%u", &int_buffer) == EOF)
                        {
                            fprintf(stderr, "CAInvPrm: main: ERROR: Could not read transformation from %s.\n", \
                                                infile);
                            exit(8);
                        }
                        else
                            *(sigm + i) = int_buffer;
                    }
                    if(fscnf(g, "%u", &int_buffer) == EOF)
                    {
                        fprintf(stderr, "CAInvPrm: main: ERROR: Could not read transformation from %s.\n", infile);
                        exit(8);
                    }
                    else
                        *(sigm + td - 1) = int_buffer;
                    if(nodecflag == FALSE)
                    {
                        api_sig = local2dec_api(R, td, sigm);
                        sig = NULL;
                        if/api_sig <= longlimit)
                        {
                            sig = atol/api_sig_api2char());
                            api_sig = 0;
                        }
                    }
                }
            }
            else // decimal reps
            {
                i = 0;
                while(c != '\n' && c != EOF)
                {
```
```c
        buffer[i] = c;
        i++;
        fSCANf(g, "%c", &c);
    }
    buffer[i] = '\0';
    api_sig = buffer;
    sig = NULL;
    if api_sig <= longlimit)
    {
        sig = atol(buffer);
        api_sig = 0;
    }
    if (sig == NULL)
        sig = dec2local(R, td, api_sig);
    else
        sig = dec2local(R, td, sig);
}
}
}
}
stopflag = TRUE;
free(sigma);          // free space before starting anew
free(tau);
if (invflag == TRUE && simpleflag == FALSE)
    free(ta);
}
free(r1tmp);
free(sigm);
if (f != NULL)
    fclose(f);
if (g != NULL)
    fclose(g);
return 0;
}
```

```c
/*
Name: APIL,H
Author: Leo Liberti
Purpose: To implement functions for an Arbitrary Precision
          Integer Library (header file and class definition).
Source: MS Visual C++ 4.0 (header file)
*/
#ifdef WIN32
#include <malloc.h>
typedef unsigned long number_length;
#endif
#ifdef WIN32
#include <alloc.h>
typedef unsigned long number_length;
#endif
#include <string.h>
#include <stdlib.h>
#include <math.h>
typedef short int boolean;
#ifndef BASE
#define BASE (unsigned short) 10
#endif
#ifdef TRUE
#define TRUE (unsigned short) 1
#endif
#ifdef FALSE
#define FALSE (unsigned short) 0
#endif
#ifdef PLUS
#define PLUS (boolean) 1
#endif
#ifdef MINUS
#define MINUS (boolean) -1
#endif

class api
{
public:
    /* DATA */
    char *number;
    short int sign;

    /* CONSTRUCTORS AND DESTRUCTORS */
    api(void);
    api(char *n, short int s);
    api(const api &a);
    // api();

    /* UTILITY FUNCTIONS */
    void exchange api *a, api *b);
    char *api2char(void);
    unsigned short int get Coefficient power (unsigned long);

    /* MATHEMATICAL FUNCTIONS */
    api abs();
    api cut (number_length);
    friend void divide (api, api, api *, api *);
    friend void one digit divide (api, short int, api *, api *);
    friend api power (api, api);
    friend api power (api, unsigned long);
    friend api power (api, long);
    friend api power (api, unsigned int);
    friend api power (api, int);
    friend api power (api, unsigned short);
```
```c
friend api power api, short);
friend api power api, char *);
/* MATHEMATICAL OPERATORS */
/* ******** Assignment Operators */
api operator =(api);
api operator =(short int);
api operator =(int);
api operator =(long int);
api operator =(unsigned short int);
api operator =(unsigned int);
api operator =(unsigned long int);
api operator =(char *n);
/* ******** Order Operators */
boolean operator <(api);
boolean operator <(unsigned long);
boolean operator <(long);
boolean operator <(unsigned int);
boolean operator <(int);
boolean operator <(unsigned short);
boolean operator <(short);
boolean operator <(char *);
boolean operator ==(api);
boolean operator ==(unsigned long);
boolean operator ==(long);
boolean operator ==(unsigned int);
boolean operator ==(int);
boolean operator ==(unsigned short);
boolean operator ==(short);
boolean operator ==(char *a);
boolean operator !=(api);
boolean operator !=(unsigned long);
boolean operator !=(long);
boolean operator !=(unsigned int);
boolean operator !=(int);
boolean operator !=(unsigned short int);
boolean operator !=(short int);
boolean operator !=(char *a);
boolean operator >(api);
boolean operator >(unsigned long);
boolean operator >(long);
boolean operator >(unsigned int);
boolean operator >(int);
boolean operator >(unsigned short);
boolean operator >(short);
boolean operator >(char *a);
boolean operator <=(api);
boolean operator <=(unsigned long);
boolean operator <=(long);
boolean operator <=(unsigned int);
boolean operator <=(int);
boolean operator <=(unsigned short);
boolean operator <=(short);
boolean operator <=(char *a);
boolean operator >=(api);
boolean operator >=(unsigned long);
boolean operator >=(long);
boolean operator >=(unsigned int);
boolean operator >=(int);
boolean operator >=(unsigned short);
boolean operator >=(short);
boolean operator >=(char *a);
/* ******** Arithmetic Operators */
api operator +();
api operator -();
api operator +(api);
api operator +(unsigned long);
api operator +(long);
api operator +(unsigned int);
api operator +(int);
api operator +(unsigned short);
api operator +(short);
api operator +(char *);
api operator -(api);
api operator -(unsigned long);
api operator -(long);
api operator -(unsigned int);
api operator -(int);
api operator -(unsigned short);
api operator -(short);
api operator -(char *);
api operator *(api);
api operator *(unsigned long);
api operator *(long);
api operator *(unsigned int);
api operator *(int);
api operator *(unsigned short);
api operator *(short);
api operator *(char *);
api operator /(api);
api operator /(unsigned long);
api operator /(long);
api operator /(unsigned int);
api operator /(int);
```
```c
api operator /(unsigned short);
api operator /(short);
api operator /(char *);
api operator %(api);
api operator %(unsigned long);
api operator %(long);
api operator %(unsigned int);
api operator %(int);
api operator %(unsigned short);
api operator %(short);
api operator %(char *);
};
/* api friends */
void divide(API api, char *api, char *);
void onelesdivmod(API api, short int api, char *api);
api power(API api, char *);
api power(API api, unsigned long);
api power(API api, long);
api power(API api, unsigned int);
api power(API api, int);
api power(API api, unsigned short);
api power(API api, short);
api power(API api, char *);
/* other functions */
unsigned short int char2int(char *api, number_length);
char int2char(unsigned short int);
char *itoa(long);
char *itoa(unsigned long);
unsigned short int mod(short int, short int);
int sgn(long);
void check_char(char *api, number_length);
char *garbage_collection(char *api, number_length);
char *garbage_collection(char *);
number_length power(number_length, number_length);
```

```c
/*
Name:         APIL
Author:        Leo Liberti
Purpose:      To implement functions for an Arbitrary Precision
              Integer Library.
Source:       MS Visual C++ 4.0
History:       17/05/97 0.0      work started. Number format is a string
                             of character digits.
                             after lots of hassle, implemented rela-
                             tional operators, +, -, *,
                             first working version: added /, %, power.

24/05/97 0.6
04/06/97 1.0
*/
#include <stdio.h>
#include <string.h>
#include "apil.h"

/* UTILITIES FUNCTIONS */
/* returns the integer stored in the pos'th character of the string.
 convention is that the first char. of string is indexed with 0 */
unsigned short int char2int(char *t, number_length pos)
{
    int ret;
    char r;

    r = *(t + pos);
    if(r < '0' || r > '9')
        ret = -1;
    else
        ret = r - '0';

    return ret;
}

/* returns a char out of a positive short int */
char int2char(unsigned short int p)
{
    return p + '0';
}

/* converts multidigit integer to string */
char *itoa(unsigned long p)
{
    unsigned long digits, i;
    char *ret;

    if(p == 0)
        digits = 1;
    else
        digits = (unsigned long) floor(log10((double) p)) + 1;

    // ret = new char[digits];
    ret = (char *) malloc(digits);
    check_char(ret, digits);

    for(i = 0; i < digits; i++)
        *(ret + digits - i - 1) = int2char((p / \
power(Base, (number_length) i)) % Base);

    return ret;
}

char *itoa(long p)
{
    unsigned long digits, i, ll, q;
```
```c
char *ret;
q = labs(p);
if(p == 0)
    digits = 1;
else
    digits = (unsigned long) floor(log10((double) q)) + 1;
if(p < 0)
    ++digits;
//ret = new char[digits];
ret = (char *) malloc類 digits);
check_char(ret, digits);
if(p < 0)
{
    *ret = -';'
    ll = 1;
}
else
    ll = 0;
for(i = ll; i < digits; i++)
    *(ret + i) = int2char((q / \ powerBasE, (number_length) i)) % BASE);
return ret;
}
/* returns a^n */
number_length power(number_length a, number_length n)
{
    number_length u, v, t;
    u = n;
    v = 1;
    t = a;
    while(u != 0)
    {
        if(u % 2 == 1)
        {
            v = v * t;
        }
        t = t * t;
        u = u / 2;
    }
    return v;
}
/* if a>0, returns a mod b; otherwise n + (a mod b) */
unsigned short int mod(short int a, short int b)
{
    unsigned short int ret;
    if(a == 0)
        ret = a;
    else if(a > 0)
        ret = a % b;
    else if(abs(a) == b)
        ret = 0;
    else
        ret = b + (a % b);
    return ret;
}
/* returns the sign of an int */
int sgn(long a)
{
    if(a >= 0)
        return (int) PLUS;
    else
        return (int) MINUS;
}
/* frees unused space from strings */
void check_char(char *t, number_length c)
{
    if(strlen(t) > c)
        *(t + c) = '\0';
    if(!t)
    {
        /* error 2 : no memory */
        printf("APIL: Error: Could not allocate memory.\n");
        exit(2);
    }
}
char *garbage_collection(char *t, number_length *c)
{
    char *r, *s;
    s = t;
    while(*s == '0')
        s++;
    *c = strlen(s);
    /* check if t is zero */
    if(*c == 0)
    {
        s--;
        *c = 1;
    }
    //r = new char[*c];
    r = (char *) malloc(*c);
    check_char(r, *c);
    strcpy(r, s);
    return r;
}
char *garbage_collection(char *t)
{
    char *r, *s;
    s = t;
    while(*s == '0')
```
++s;
/* check if t is zero */
if(strlen(s) == 0)
    s++;
//r = new char strlen(s);
r = (char *) malloc(strlen(s));
check_char(r, strlen(s));
 strcpy(r, s);
return r;
}
/* CLASS API FUNCTIONS */
api::api()
{
    this->number = (char *) malloc(0);
    check_char(this->number, 0);
    *(this->number) = '\0';
}
api::api(char *n, short int s)
{
    number_length ln;
    ln = strlen(n);
    this->number = (char *) malloc(ln);
    check_char(this->number, ln);
    strcpy(this->number, n);
    this->sign = s;
}
api::api(const api &a)
{
    number_length ln;
    ln = strlen(a.number);
    this->number = (char *) malloc(ln);
    check_char(this->number, ln);
    strcpy(this->number, a.number);
    this->sign = a.sign;
}
/* work has to be done here; destructor does not work properly, so
rem it out. The problem of course is that there is a memory leak
without it. Compiling with DEBUG options fixes this but makes the
executable larger */
//api::"api()"
//
    //if(this->number != NULL)
    //    //delete this->number;
    //
    free(this->number);
//}
/* UTILITY FUNCTIONS */
void api::exchange api *a, api *b)
{
    api *address;
    address = a;
    a = b;
    b = address;
}
char *api::api2char()
{
    char *s;
    if(this->sign == MINUS)
    {
        s = (char *) malloc(strlen(this->number) + 1);
        check_char(s, strlen(this->number) + 1);
        *s = 'a';
        strcpy(s + 1, this->number);
    }
    else
    {
        s = (char *) malloc(strlen(this->number));
        check_char(s, strlen(this->number));
        strcpy(s, this->number);
    }
    return s;
}
unsigned short int api::getCoefficient_power(unsigned long p)
{
    unsigned long sl;
    unsigned short ret;
    sl = strlen(this->number) - 1;
    ret = *(this->number + sl - p) - '0';
    return ret;
}
/* MATHEMATICAL FUNCTIONS */
api api::abs()
{
    api ret(this->number, PLUS);
    return ret;
}
api api::cut(number_length digits)
{
    api ret;
    number_length ln, i;
    ret.sign = this->sign;
    ln = strlen(this->number);
    ret.number = (char *) realloc(ret.number, digits);
    if(ln < digits)
    {
```c
check_char(ret.number, digits);
for(i = 0; i < digits - ln; i++)
    *(ret.number + i) = '0';
 strcpy(ret.number + digits - ln, this->number);
}
else if(ln > digits)
    strcpy(ret.number, this->number + ln - digits);
else
    strcpy(ret.number, this->number);
return ret;
}

/* friend */
void one时代的divide(API a, short int b, API *q, API *r)
{
    api zero, one, bapi;
    number_length c, la;
    unsigned short int start, tmp, n, t;
    char *ini; /* rem out when using new */
    /* make zero and identity */
    //char *ini = new char[1];
    ini = (char *) malloc(1);
    check_char(ini, 1);
    *ini = '0';
    zero = ini;
    *ini = '1';
    one = ini;
    //delete ini;
    /* preliminary checks */
    bapi = b;
    la = strlen(a.number);
    tmp = a.getCoefficient_power(la - 1);
    if(la == 1 && tmp == abs(b))
    {
        *q = one;
        q->sign = a.sign * sgn(b);
        *r = zero;
        return;
    }
    else if(la == 1 && tmp < abs(b))
    {
        *q = zero;
        *r = a;
        return;
    }
    else if(la == 1 && tmp < abs(b))
    {
        *q = tmp / b;
        *r = tmp % b;
        return;
    }
    else if(la > 1 && tmp < abs(b))
    {
        q->number = (char *) realloc(q->number, la - 1);
        check_char(q->number, la - 1);
        for(c = 0; c < la - 1; c++)
            *(q->number + c) = '0';
        start = 2;
        n = tmp * BASE + a.get Coefficient power (la - 2);
    }
    else
    {
        q->number = (char *) realloc(q->number, la);
        check_char(q->number, la);
        for(c = 0; c < la; c++)
            *(q->number + c) = '0';
        start = 1;
        n = tmp;
    }
    /* perform calculation */
    for(c = start; c <= la; c++)
    {
        *(q->number + c - start) = int2char(n / b);
        t = n % b;
        if(c != la)
            n = t * BASE + a.get Coefficient power (la - c - 1);
    }
    q->sign = a.sign * sgn(b);
    r->number = (char *) realloc(r->number, 2);
    check_char(r->number, 2);
    *r = a - bapi * (*q);
    return;
}

/* the following function implements the division algorithm as
described in Knuth, The Art of Computer Programming, part II:
Seminumerical Algorithms. */
/* friend */
void divide(API a, api b, api *q, api *r)
{
    api tmp, tmp2, tmp3, tmp4, d1, dummy, zero, one;
    unsigned short d, v1, v2, qhat, qtmp;
    number_length m, n, p, i, j, c, start, q_digits;
    boolean digit_flag, carry_flag;
    short int bsign;
    char *ini; /* rem out when using new */
    /* make zero and identity */
    //char *ini = new char[1];
    ini = (char *) malloc(1);
    check_char(ini, 1);
    *ini = '0';
    zero = ini;
```
```
*ini = '1';
one = ini;
//delete ini;
/* preliminary checks */
if(a.abs() == b.abs())
{
    *q = one;
    q->sign = a.sign * b.sign;
    *r = zero;
    return;
}
else if(a abs() < b abs())
{
    *q = zero;
    *r = a;
    return;
}

/* start */
n = strlen(b.number);
m = strlen(a.number) - n;
//char *ini = new char[m + 1];
ini = (char *) realloc(ini, m + 1);
check_char(ini, m + 1);
for(i = 0; i < m + 1; i++)
    *(ini + i) = '0';
q->sign = PLUS;
q->number = (char *) realloc(q->number, m + 1);
check_char(q->number, m + 1);
 strcpy(q->number, ini);
//delete ini;
//char *ini = new char[n];
ini = (char *) realloc(ini, n);
check_char(ini, n);
for(i = 0; i < n; i++)
    *(ini + i) = '0';
r->sign = PLUS;
r->number = (char *) realloc(r->number, n);
check_char(r->number, n);
 strcpy(r->number, ini);
// delete ini;
/* start calculation [Knuth, Art of C.P., II, p. 257] */
v1 = b.getCoefficient_power(n - 1);
v2 = b.getCoefficient_power(n - 2);
if(v1 == 0)
{
    /* error 1 : divide by 0 */
    printf("APIL: ERROR: Divide by zero.\n");
    exit(1);
}
if(n == 1)
{
    oneambdiv(a, v1, q, r);
    q->sign = a.sign * b.sign;
    r->sign = PLUS;
    q->number = garbage sop(q->number);
    r->number = garbage sop(r->number);
}
else
{
    qambdiv = 0;
    /* step1: normalize */
    d = BASE / (v1 + 1);
    d1 = d;
    tmp = a * d1;
    p = strlen(tmp.number);
    if(p == m + n)
        digit_flag = TRUE;
    else
        digit_flag = FALSE;
    /* save b.sign before changing it */
    bsign = b.sign;
    b = b abs() * d1;
    v1 = b.getCoefficient_power(n - 1);
    v2 = b.getCoefficient_power(n - 2);
    /* if(strlen(b.number) > n)
        b.number++ */
    /* step2: initialize j */
    if(digit_flag == TRUE)
    {
        /* do the first loop (j = 0) keeping in mind that
         tmp.getCoefficient_power(p - j - 1) doesn't exist
         and has to be set to 0 */
        /* step3.0: calculate qhat */
        qtmp = tmp.getCoefficient_power(p - 1);
        qhat = qtmp / v1;
        while(v2 * qhat > (qtmp - qhat * v1) * BASE + \
                        tmp.getCoefficient_power(p - 2))
            qhat--;
        /* step4.0: multiply and subtract */
        //char *ini = new char[n];
        ini = (char *) realloc(ini, n);
        check_char(ini, n);
        strcpy(ini, tmp.number, (size_t) n);
        tmp2 = ini;
        tmp3 = qhat;
        //delete ini;
        tmp2 = tmp2 - tmp3 * b;
        if(tmp2.sign == MINUS)
        {
```
```c
carry_flag = TRUE;
//char *ini = new char[n + 1];
ini = (char *) realloc(ini, n + 1);
check_char(ini, n + 1);
*ini = '1';
for(c = 1; c <= n; c++)
    *(ini + c) = '0';
tmp4 = ini;
//delete ini;
tmp2 = tmp4 + tmp2;
}
else
    carry_flag = FALSE;
tmp2 = tmp2 cut(n);
strncpy(tmp.number, tmp2.number, n);
/* step5.0: 'test remainder" [what? where?] */
*(q->number) = int2char(qhat);
q_digits++;
/* step6.0: add back */
if(carry_flag == TRUE)
{
    --(*(q->number));
tmp2 = tmp2 + b;
strncpy(tmp.number, tmp2.number + 1, n);
}
start = 1;
}
else
    start = 0;
if(m >= start)
{
    for(j = 0; j <= m - start; j++)
    {
        /* step3: calculate qhat */
        qtmp = tmp.getCoefficient_power(p - j - 1) * BASE + \
              tmp.getCoefficient_power(p - j - 2);
        if(tmp.getCoefficient_power(p - 1 - j) == v1)
            qhat = BASE - 1;
        else
            qhat = qtmp / v1;
        while(v2 * qhat > (qtmp - qhat * v1) * BASE + \
                          tmp.getCoefficient_power(p - j - 3))
            qhat--;
        /* step4: multiply and subtract */
        //char *ini = new char[n + 1];
        ini = (char *) realloc(ini, n + 1);
        check_char(ini, n + 1);
        strncpy(ini, tmp.number + j, n + 1);
        tmp2 = ini;
        tmp3 = qhat;
        tmp2 = tmp2 - tmp3 * b;
        if(tmp2.sign == MINUS)
        {
            carry_flag = TRUE;
            *ini = '1';
            for(c = 1; c <= n; c++)
                *(ini + c) = '0';
tmp4 = ini;
tmp2 = tmp4 + tmp2;
}
else
    carry_flag = FALSE;
tmp2 = tmp2 cut(n + 1);
strncpy(tmp.number + j, tmp2.number, n + 1);
//delete ini;
/* step5: test remainder */
*(q->number + j + start) = int2char(qhat);
q_digits++;
/* step6: add back */
if(carry_flag == TRUE)
{
    --(*(q->number + j));
tmp2 = tmp2 + b;
strncpy(tmp.number + j + 1, tmp2.number + 1, n);
}
/* step7: loop on j */
}
}
/* step8: unnormalize */
if(m >= start)
tmp2 = tmp.number + m - start;
else
    tmp2 = tmp;
//char *ini = new char[i];
ini = (char *) realloc(ini, i);
check_char(ini, i);
*ini = '0';
dummy = ini;
//delete ini;
one时代的 divide(tmp2, d, r, &dummy);
/* use bsign (b.sign saved) to calculate q->sign */
q->sign = a.sign * bsign;
r->sign = PLUS;
*(q->number + q_digits) = '\0';
if((q->number) == '0')
    (q->number)++;
r->number = garbage_collection(r->number);
}
return;
}
```
/* function power */
/* friend */
api power api a, api n)
{
    api u, v, t;

    u = n;
    v = 1;
    t = a;

    while(u != 0)
    {
        if(u.get Coefficient power(0) % 2 == 1)
        {
            v = v * t;
        }
        t = t * t;
        u = u / 2;
    }
    return v;
}

/* friend */
api power api a, unsigned long b)
{
    api t;
    t = b;
    return power(a, t);
}

/* friend */
api power api a, long b)
{
    api t;
    t = b;
    return power(a, t);
}

/* friend */
api power api a, unsigned int b)
{
    return power(a, (unsigned long) b);
}

/* friend */
api power api a, int b)
{
    return power(a, (long) b);
}

/* friend */
api power api a, unsigned short b)
{
    return power(a, (unsigned long) b);
}

/* friend */
api power api a, short b)
{
    return power(a, (long) b);
}

/* friend */
api power api a, char *b)
{
    api t;
    t = b;
    return power(a, t);
}

/* end function power */

/* MATHEMATICAL OPERATORS */

/* ******** Assignment Operators */
api api::operator =(api a)
{
    this->number = (char *) realloc(this->number, strlen(a.number));
    check_char(this->number, strlen(a.number));
    strcpy(this->number, a.number);
    this->sign = a.sign;
    return *this;
}

api api::operator =(char *n)
{
    number_length c;

    c = 0;

    if(*n == '–')
    {
        this->sign = MINUS;
        c++;
    }
    else
    {
        this->sign = PLUS;
        while(*(n + c) == '0')
            c++;
    }

    /* check if *(n+c) = '0' */
    if
    this->number = (char *) realoc(this->number, \ n + c));
    check_char(this->number, strlen(n + c));
    strcpy(this->number, n + c);
    return *this;
}

api api::operator =(long a)
{
    char *s;
    s = itoa(a);
    this->number = s;
```c
this->sign = sgn(a);
return *this;
}

api api::operator =(int a)
{
    *this = (long) a;
    return *this;
}

api api::operator =(short a)
{
    *this = (long) a;
    return *this;
}

api api::operator =(unsigned long a)
{
    char *s;
    s = itoa(a);
    *this = s;
    this->sign = PLUS;
    return *this;
}

api api::operator =(unsigned int a)
{
    *this = (unsigned long) a;
    return *this;
}

api api::operator =(unsigned short a)
{
    *this = (unsigned long) a;
    return *this;
}

/* ******* Order Operators */
/* operator < */
boolean api::operator <(api a)
{
    boolean ret;
    number_length lt, la, i;
    lt = strlen(this->number);
    la = strlen(a.number);
    if (this->sign > a.sign)
        ret = FALSE;
    else if (this->sign < a.sign)
        ret = TRUE;
    else if (lt > la)
        ret = FALSE;
    else if (lt < la)
        ret = TRUE;
    else
    {
        ret = FALSE;
        for (i = 0; i < lt; i++)
        {
            if (this->number[i] < a.number[i])
            {
                ret = TRUE;
                break;
            }
            else if (this->number[i] > a.number[i])
            {
                ret = FALSE;
                break;
            }
        }
    }
    return ret;
}

boolean api::operator <(unsigned long a)
{
    api t;
    t = a;
    if (*this < t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator <(long a)
{
    api t;
    t = a;
    if (*this < t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator <(unsigned int a)
{
    return (*this < (unsigned long) a);
}

boolean api::operator <(int a)
{
    return (*this < (long) a);
}

boolean api::operator <(unsigned short int a)
{
    return (*this < (unsigned long) a);
}

boolean api::operator <(short int a)
{
    return (*this < (long) a);
}
```
```c
boolean api::operator <(char *a)
{
    api t;
    t = a;
    if (*this < t)
        return TRUE;
    else
        return FALSE;
}
/* end operator < */
/* operator == */
boolean api::operator == (api a)
{
    boolean ret;
    number_length lt, la, i;
    lt = strlen(this->number);
    la = strlen(a.number);
    if (this->sign != a.sign)
        ret = FALSE;
    else if (lt != la)
        ret = FALSE;
    else
    {
        ret = TRUE;
        for (i = 0; i < lt; i++)
        {
            if (this->number[i] != a.number[i])
            {
                ret = FALSE;
                break;
            }
        }
    }
    return ret;
}

boolean api::operator == (unsigned long a)
{
    api t;
    t = a;
    if (*this == t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator == (long a)
{
    api t;
    t = a;
    if (*this == t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator == (unsigned int a)
{
    return (*this == (unsigned long) a);
}

boolean api::operator == (int a)
{
    return (*this == (long) a);
}

boolean api::operator == (unsigned short int a)
{
    return (*this == (unsigned long) a);
}

boolean api::operator == (short int a)
{
    return (*this == (long) a);
}

boolean api::operator == (char *a)
{
    api t;
    t = a;
    if (*this == t)
        return TRUE;
    else
        return FALSE;
}
/* end operator == */
/* operator != */
boolean api::operator != (api a)
{
    return !(*this == a);
}

boolean api::operator != (unsigned long a)
{
    return !(*this == a);
}

boolean api::operator != (long a)
{
    return !(*this == a);
}

boolean api::operator != (unsigned int a)
{
    return !(*this == a);
}

boolean api::operator != (int a)
{
    return !(*this == a);
}

boolean api::operator != (unsigned short int a)
{
    return !(*this == a);
}
```
```c
{
    return !(*this == a);
}

boolean api::operator !=(short int a)
{
    return !(*this == a);
}

boolean api::operator !=(char *a)
{
    return !(*this == a);
}

/* end operator != */
/* operator > */
boolean api::operator > (api a)
{
    boolean ret;
    if (a < *this)
        ret = TRUE;
    else
        ret = FALSE;
    return ret;
}

boolean api::operator > (unsigned long a)
{
    api t;
    t = a;
    if (*this > t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator > (long a)
{
    api t;
    t = a;
    if (*this > t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator > (unsigned int a)
{
    return (*this > (unsigned long) a);
}

boolean api::operator > (int a)
{
    return (*this > (long) a);
}

boolean api::operator > (unsigned short int a)
{
    return (*this > (unsigned long) a);
}

boolean api::operator > (short int a)
{
    return (*this > (long) a);
}

boolean api::operator > (char *a)
{
    api t;
    t = a;
    if (*this > t)
        return TRUE;
    else
        return FALSE;
}

/* end operator > */
/* operator <= */
boolean api::operator <= (api a)
{
    boolean ret;
    if (*this < a || *this == a)
        ret = TRUE;
    else
        ret = FALSE;
    return ret;
}

boolean api::operator <= (unsigned long a)
{
    api t;
    t = a;
    if (*this <= t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator <= (long a)
{
    api t;
    t = a;
    if (*this <= t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator <= (unsigned int a)
{
    return (*this <= (unsigned long) a);
}

boolean api::operator <= (int a)
{
```
```c
return (*this <= (long) a);
}

boolean api::operator <=(unsigned short int a)
{
    return (*this <= (unsigned long) a);
}

boolean api::operator <=(short int a)
{
    return (*this <= (long) a);
}

boolean api::operator <=(char *a)
{
    api t;
    t = a;
    if (*this <= t)
        return TRUE;
    else
        return FALSE;
}

/* end operator <= */

/* operator >= */
boolean api::operator >=(api a)
{
    boolean ret;
    if (*this > a || *this == a)
        ret = TRUE;
    else
        ret = FALSE;
    return ret;
}

boolean api::operator >=(unsigned long a)
{
    api t;
    t = a;
    if (*this >= t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator >=(long a)
{
    api t;
    t = a;
    if (*this >= t)
        return TRUE;
    else
        return FALSE;
}

boolean api::operator >=(unsigned int a)
{
    return (*this >= (unsigned long) a);
}

boolean api::operator >=(int a)
{
    return (*this >= (long) a);
}

boolean api::operator >=(unsigned short int a)
{
    return (*this >= (unsigned long) a);
}

boolean api::operator >=(short int a)
{
    return (*this >= (long) a);
}

boolean api::operator >=(char *a)
{
    api t;
    t = a;
    if (*this >= t)
        return TRUE;
    else
        return FALSE;
}

/* end operator >= */

/* ****** Arithmetic Operators */
api api::operator +()
{
    api ret(this->number, this->sign);
    return ret;
}

api api::operator -()
{
    api ret(this->number, MINUS * (this->sign));
    return ret;
}

/* operator + */
api api::operator +(api a)
{
    char *t; /* rem out when using new */
    number_length lt, la, lmx, lmn, i, *c;
    short int carry, tmp, amax;
    api ret;
    c = new number_length;
    /* in order to avoid the operations of the likes of
       1 -
       12 =
       -29 (algorithm goes wrong)
    */
    calculates -(12 - 1) instead
```
```c
if(this->sign == PLUS && a.sign == MINUS && (a.abs() > *this))
    return -(-a - *this);

/* in order to avoid the operations of the likes of
  -12 +
  -1 =
  -29 (algorithm goes wrong)
  calculates -(12 - 1) instead
  */
if(this->sign == MINUS && a.sign == PLUS && (this->abs() > a))
    return -(*this - a);

/* in order to avoid the operations of the likes of
  -12 +
  -1 =
  -27 (algorithm goes wrong)
  calculates -(12 - (-1)) instead
  */
if(this->sign + a.sign == 2 * MINUS)
    return -(*this - a);

/* now start calculation */
lt = strlen(this->number);
la = strlen(a.number);
if(lt <= la)
{
    lmn = lt;
    lmx = la;
    amax = TRUE;
}
else if(lt > la)
{
    lmx = lt;
    lmn = la;
    amax = FALSE;
}

//char *t = new char[lmx + 1];
t = (char *) malloc(lmx + 1);
check_char(t, lmx + 1);
carry = 0;

for (i = 1; i <= lmn; i++)
{
    tmp = this->sign * char2int(this->number, lt - i) + \
        a.sign * char2int(a.number, la - i) + carry;
    *(t + lmx - i + 1) = int2char(mod(tmp, BASE));
    if(this->sign + a.sign == 0)
    {
        if(tmp < 0)
            carry = MINUS;
        else
            carry = 0;
    }
    else
    {
        if(tmp >= BASE)
            carry = PLUS;
        else
            carry = 0;
    }
}

for (i = lmn + 1; i <= lmx; i++)
{
    if(amax == FALSE)
        tmp = char2int(this->number, lt - i);
    else
        tmp = char2int(a.number, la - i);
    tmp = tmp + carry;
    *(t + lmx - i + 1) = int2char(mod(tmp, BASE));
    if(this->sign + a.sign == 0)
    {
        if(tmp < 0)
            carry = MINUS;
        else
            carry = 0;
    }
    else
    {
        if(tmp > BASE)
            carry = PLUS;
        else
            carry = 0;
    }
    if(carry != 0)
        *t = int2char(carry);
    else
        *t = '0';
    t = garbage_collection(t, c);
    check_char(t, *c);
    delete c;

    /* the cases computed here always have PLUS sign */
    ret = t;
    //delete t;
    return ret;
}

api api::operator +(unsigned long a)
{
    api t;
    t = a;
    return *this + t;
}

api api::operator +(long a)
{
    api t;
    t = a;
    return *this + t;
}
```
```c
api api::operator + (unsigned int a)
{
    return *this + (unsigned long) a;
}

api api::operator + (int a)
{
    return *this + (long) a;
}

api api::operator + (unsigned short a)
{
    return *this + (unsigned long) a;
}

api api::operator + (short a)
{
    return *this + (long) a;
}

api api::operator + (char *a)
{
    api t;
    t = a;
    return *this + t;
}

/* end operator + */
/* operator - */
api api::operator - (api a)
{
    return *this + (-a);
}

api api::operator - (unsigned long a)
{
    api t;
    t = a;
    return *this - t;
}

api api::operator - (long a)
{
    api t;
    t = a;
    return *this - t;
}

api api::operator - (unsigned int a)
{
    return *this - (unsigned long) a;
}

api api::operator - (int a)
{
    return *this - (long) a;
}

api api::operator - (unsigned short a)
{
    return *this - (unsigned long) a;
}

api api::operator - (short a)
{
    return *this - (long) a;
}

api api::operator - (char *a)
{
    api t;
    t = a;
    return *this - t;
}

/* end operator - */
/* operator * */
api api::operator * (api a)
{
    char *ini; /* rem out when using new */
    number_length i, j, lret, lt, la, len_check, *c;
    unsigned short tmp, k;

    c = new number_length;
    lt = strlen(this->number);
    la = strlen(a.number);

    /* check that length of string doesn't exceed capacity */
    len_check = power(2, sizeof(number_length) * 8 - 1);
    if(la >= len_check && lt >= len_check)
    {
        api ret("APIL: Error: Multiplication Overflow", PLUS);
        return ret;
    }

    /* initialize ret */
    lret = lt + la;
    //char *ini = new char[lret];
    ini = (char *) malloc(lret);
    check_char(ini, lret);

    for(i = 0; i < lret; i++)
        *(ini + i) = '0';
    api ret(ini, PLUS);

    /* start calculation (code from NUMEO.C by cerruti@dm.unito.it) */
    for(j = 1; j <= la; ++j)
    {
        k = 0;
        for(i = 1; i <= lt; ++i)
        {
            tmp = char2int(this->number, lt - i) * \
                   char2int(a.number, la - j) + \
                   char2int(ini, lret - i - j + 1) + k;
```
```c
        *(ini + lret - i - j + 1) = int2char(tmp % BASE);
        k = tmp / BASE;
    }
    *(ini + lret - j - lt) = int2char(k);
}

ini = garbage_collection(ini, c);
check_char(ini, *c);
 strcpy(ret.number, ini);
ret.sign = this->sign * a.sign;
//delete ini;
return ret;
}

api api::operator *(unsigned long a)
{
    api t;
    t = a;
    return *this * t;
}

api api::operator *(long a)
{
    api t;
    t = a;
    return *this * t;
}

api api::operator *(unsigned int a)
{
    return *this * (unsigned long) a;
}

api api::operator *(int a)
{
    return *this * (long) a;
}

api api::operator *(unsigned short a)
{
    return *this * (unsigned long) a;
}

api api::operator *(short a)
{
    return *this * (long) a;
}

api api::operator *(char *a)
{
    api t;
    t = a;
    return *this * t;
}

/* end operator */
/* operator / */
api api::operator /(api a)
{
    api quotient, rest;
    divide(*this, a, &quotient, &rest);
    return quotient;
}

api api::operator /(unsigned long a)
{
    api t;
    t = a;
    return *this / t;
}

api api::operator /(long a)
{
    api t;
    t = a;
    return *this / t;
}

api api::operator /(unsigned int a)
{
    return *this / (unsigned long) a;
}

api api::operator /(int a)
{
    return *this / (long) a;
}

api api::operator /(unsigned short a)
{
    return *this / (unsigned long) a;
}

api api::operator /(short a)
{
    return *this / (long) a;
}

api api::operator /(char *a)
{
    api t;
    t = a;
    return *this / t;
}

/* end operator */
/* operator % */
api api::operator % (api a)
{
    api quotient, rest;
    divide(*this, a, &quotient, &rest);
    return rest;
}
```
```c
}
api api::operator %(unsigned long a)
{
    api t;
    t = a;
    return *this % t;
}

api api::operator %(long a)
{
    api t;
    t = a;
    return *this % t;
}

api api::operator %(unsigned int a)
{
    return *this % (unsigned long) a;
}

api api::operator %(int a)
{
    return *this % (long) a;
}

api api::operator %(unsigned short a)
{
    return *this % (unsigned long) a;
}

api api::operator %(short a)
{
    return *this % (long) a;
}

api api::operator %(char *a)
{
    api t;
    t = a;
    return *this % t;
}

/* end operator % */

/* CLASS API END */
```
B Appendice: Il Programma CAInvInf

/*
Name: CAInvInf.H
Author: Leo Liberti
Purpose: to test for injectivity of global reps
of CA transformations (see thesis) (header file
and class definition).
Algorithm by S. Amoroso and Y.N. Patt, 1972
*/
Source: MS Visual C++ 4.0

// global variables (defaults):
int R = 2;
int n = 3;

// structures
struct triple
{
    unsigned int r;
    unsigned long row;
    unsigned long col;
    int status;
};

// classes:
class couple
{
public:
    // data
    unsigned long a;
    unsigned long b;
    class couple *prec;
    class couple **sequent;
    int *sequent_status;
    int status;
    int merge_after;
    int been_there;

    // functions
    void assign(unsigned long a, unsigned long b);

    // constructors and destructors: don't need any
};

/*
Name: CAInvInf
Author: Leo Liberti
Purpose: To test for injectivity of global reps
of CA transformations (see thesis)
Algorithm by S. Amoroso and Y.N. Patt, 1972
Source: MS Visual C++ 4.0
History: 02/09/97 0.1 first try finished
02/09/97 1.0 it works
Notes: decimal numbers: unsigned long
local rule length: unsigned long
base: unsigned int
local rules are in form (v_1, \dots, v_n)
functions are coded in order of dependency
exit codes & error msgs
1 not enough memory
2 localrule is not injective in 1
3 localrule is not injective in 2.step 3
4 localrule is not injective in 2.step 4
6 localrule is not injective in 2.step 6
N.B. Actually this program is nearly in C; the only
C++ extension used is class couple, but it could
easily be redefined as a structure.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CAInvInf.h"
/* Values couple.status can take */
#define CROSSED_OUT 0
#define NORMAL -1
/* Values couple.merge_after can take */
#define CROSS 0
/* Values couple.sequent_status can take */
#define CROSSED 0
/* Values couple.been_there can take */
#define NO -1
/* Values triple.status can take */
#define FOUND 0
#define NOT_FOUND -1
/* other defines */
#define TRUE 1
#define FALSE 0
#define MSG "CAInvInf v. 1;0 - Leo Liberti 1997\n"
#define OUTFILE "CAInvInf.log"
// various utility functions **********
unsigned long power(unsigned long a, unsigned long n)
{
    unsigned long u, v, t;
```c
u = n;
v = 1;
t = a;
while(u != 0)
{
    if(u % 2 == 1)
    {
        v = v * t;
    }
    t = t * t;
    u = u / 2;
}
return v;
}
// like dec2vect but also inverts direction
unsigned int *dec2local(unsigned int R, unsigned long n, unsigned long d)
{
    unsigned int *v;
    unsigned long t, i;
    v = (unsigned int *) malloc(n * sizeof(unsigned int));
    if(v == NULL)
    {
        fprintf(stderr, "CAInvInf: dec2vect: ERROR: Not enough memory.\n");
        exit(1);
    }
    t = 1;
    for(i = 0; i < n; i++)
    {
        *(v + i) = (d / t) % R;
        t = t * R;
    }
    return v;
}
void local_out(unsigned long loc_len, unsigned int *localrule, FILE *fp)
{
    // inverts back the localrule as well
    fputs("(", fp);
    for(i = 0; i < loc_len - 1; i++)
        fprintf fp, "%u,", *(localrule + loc_len - i - 1));
    fprintf fp, "%u)", *localrule);
}
// end of various utility functions **************
// class couple related functions **************
void couple::assign(unsigned long a1, unsigned long b1)
{
    unsigned int i, t;
    a = a1;
    b = b1;
    t = power( ::R, 2);
    sequent = (class couple **) malloc(t * sizeof(class couple *));
    if(sequent == NULL)
    {
        fprintf(stderr, "CAInvInf: couple constructor: ERROR: Not \
                                  enough memory.\n");
        exit(1);
    }
    for(i = 0; i < t; i++)
        sequent[i] = NULL;
    sequent_status = (int *) malloc(t * sizeof(int));
    if(sequent_status == NULL)
    {
        fprintf(stderr, "CAInvInf: couple constructor: ERROR: Not \
                                  enough memory.\n");
        exit(1);
    }
    for(i = 0; i < t; i++)
        sequent_status[i] = CROSSED;
    // default to CROSSED_OUT
    status = CROSSED_OUT;
    merge_after = NORMAL;
    prec = NULL;
    been_there = NO;
}
// end of class related functions **************
// crucial program functions **************
/* satellite functions of injectivity_test */
/* find couple finds the address (and stores it in a triple)
in the array **table of the couple (a, b)
Notes: struct triple address.status meaning
       0    found
       1    not found */
struct triple find couple(unsigned long a, unsigned long b, \
                             unsigned int *localrule, class couple ***table)
{
    struct triple address;
    unsigned int R, n, r;
    unsigned long row, col, t, t1;
    // first check that a > b; otherwise invert couple
    if(a < b)
    {
        t = a;
        a = b;
        b = t;
    }
    address.status = NOT_FOUND;
    R = ::R;
    n = ::n;
```
```c
        t = power(R, n - 1) - 1;
t1 = (t + 1) * R;
r = localrule[a];
if(localrule[b] == r)
{
    address.r = r;
    for(row = 0; row < t; row++)
    {
        if(table[r][row][0].a == a)
        {
            address.row = row;
            break;
        }
    }
    for(col = 0; col <= address.row; col++)
    {
        if(table[r][addressrow][col].b == b)
        {
            address.col = col;
            address.status = FOUND;
            break;
        }
    }
}
return address;
}

/* Note: all reference to "relevant paper" refer to
[Amoroso & Patt, Decision Procedures for Surjectivity and
Injectivity of Parallel Maps for Tessellation Structures,
J. of Comp. Syst. Sci., 6, 448-464, 1972]

Return codes: exitcode meaning
0               localrule is injective
2               TEST 1 failed (localrule not balanced)
3
4               TEST 2 Step 3 failed
5               TEST 2 Step 4 failed
6               TEST 2 Step 6 failed
*/
int injectivity_test(unsigned int *localrule)
{
    struct triple addr;
    class couple ***table, *current, *copy;
    unsigned int R, n, i, j, k, r, sl;
    unsigned long t, t1, row, col, c1, c2;
    unsigned long *balanced, a, b, counter;
    int exitcode, flag1;
    long flag;
    FILE *f;

    f = fopen(OUTFILE, "a+");
    if(f == NULL)
    {
        fprintf(stderr, "CAInvInf: WARNING: Can't open log file, \
                        report will not be written.\n");
    }
    exitcode = 0;
    R = ::R;
    n = ::n;
    t = power(R, n - 1) - 1; // t is the no. of rows in table[r]
    t1 = (t + 1) * R;       // t1 is the length of localrule
    r = 0;
    sl = power(R, 2);      // length of *sequent
    /* TEST 1: localrule must be "balanced" (see relevant paper) */
    balanced = (unsigned long *) malloc(R * sizeof(unsigned long));
    if(balanced == NULL)
    {
        fprintf(stderr, "CAInvInf: array \"balanced\" allocation: ERROR: \
                        Not enough memory.\n");
        exit(1);
    }
    for(i = 0; i < R; i++)
        balanced[i] = 0;
    for(c1 = 0; c1 < t1; c1++)
        balanced[*(*localrule + c1)]++;
    for(i = 0; i < R; i++)
    {
        if(balanced[i] != t + 1)
        {
            exitcode = 2;
            if(f != NULL)
            {
                fprintf(f, "-----------\n");
                fprintf(f, MSG);
                fprintf(f, "Local rule:\n");
                local_out(t1, localrule, f);
                fprintf(f, "\n is not injective: its table is not balanced.\n");
                fprintf(f, "\n Found %lu instances of symbol %u while expecting %lu.\n", balanced[i], i, t + 1);
                fprintf(f, "-----------\n");
                fclose(f);
            }
            free(balanced);
            return exitcode;
        }
    }
    // don't free(balanced) because it will be used later in TEST 2
    // for this purpose, void it.
    for(i = 0; i < R; i++)
        balanced[i] = t;
    /* TEST 2: as described in relevant paper */
    /* Steps 1 and 2: partition "table" of localrule and construct
sequent tables (array table) */
    /* Initialization of array table
```
```c
note: table is a complex array:
    table[r][i][j] contains the table of couples mapping to r
    table[r][i][j] is the (i,j)-th box of table r. The order
    (i,j) proceeds as in 0,0,1,0,1,1,2,0,2,1,2,2; ...
    there are (R^(n-1) - 1)(R^(n-1))/2 such boxes.

// allocation
```

```c
    table = (class couple **) malloc(R * sizeof(class couple **));
    if(table == NULL)
    {
        fprintf(stderr, "CAInvInf: array \"table\" allocation: ERROR: Not \n");
        exit(1);
    }

    for(i = 0; i < R; i++)
    {
        table[i] = (class couple **) malloc(t * sizeof(class couple *));
        if(table[i] == NULL)
        {
            fprintf(stderr, "CAInvInf: array \"table\" allocation: ERROR: Not \n");
            exit(1);
        }
    }

    for(i = 0; i < R; i++)
    {
        for(row = 0; row < t; row++)
        {
            table[i][row] = (class couple *) malloc((row + 1) * sizeof(class couple));
            if(table[i][row] == NULL)
            {
                fprintf(stderr, "CAInvInf: array \"table\" allocation: ERROR: Not \n");
                exit(1);
            }
        }
    }

    // initialization
    /* here the algorithm must search through the vector localrule and
     "fish" couples which map to the same number.
     Important: increment row and col properly, so that entries
     result in a table indexed exactly like one described
     in relevant paper, figure 5. There should be
     no overshooting because localrule is balanced
     and there are no commuted couples. */

    for ci = t1 - 1; ci > 0; ci--)
    {
        r = localrule[ci];
        /* *balanced records (t - how many times)
         r has been "visited" already */
        balanced[r]--;
        // initialize row and col
        row = balanced[r];
        col = 0;
        for(c2 = 0; c2 < ci; c2++)
        {
            if(localrule[c2] == r)
            {
                table[r][row][col].assign ci, c2);
                col++;
            }
        }
    }

    free(balanced);

    /* Step 3:find sequent sets and put their addresses in
     table[r][row][col]->sequent counter] with syntax
     table[r][row][col]->sequent counter = &(table[sequent...])
     To do this, we implement a cycle that goes through all
     the *table array and finds (and puts in *sequent)
     the address of all sequent sets. */

    // counter for table[.]
    for(r = 0; r < R; r++)
    {
        // counter for table[x][*]
        for(row = 0; row < t; row++)
        {
            // counter for table[x][y][*]
            for(col = 0; col <= row; col++)
            {
                counter = 0;
                // counter for u_2, \ldots, u_n, *
                for(j = 0; j < R; j++)
                {
                    a = ((table[r][row][col].a) * R + j) % t1;
                    // counter for v_2, \ldots, v_n, *
                    for(k = 0; k < R; k++)
                    {
                        b = ((table[r][row][col].b) * R + k) % t1;
                        /* now a and b contain the "pre-sequent set" (i.e.
                         it is a sequent set provided localrule[a]==
                         ==localrule[b] and a!=b. */
                        if(a != b)
                        {
                            /* We try to find the address of (a,b) in
                             ***table with find couple. If it is not found,
                             it means localrule[a]!==localrule[b] */
                            addr = find couple(a, b, localrule, table);
                            if(addr.status == FOUND)
                            {
                                /* Verify (a, b) != (table...->a, table...->b).
```
```c
break;
}
if(current == NULL)
{
    // impossible: table has no non CROSSED_OUT entry with NORMAL
    // sequents
    exit(3);
}
else
{
    // initialize
    copy = current;
    current = copy->sequent[i];
    current->prec = copy;
    current->been_there++;
}
{
    // (2)
    flag = TRUE;
    while flag == TRUE)
    {
        // if (a)
        if(current->status == CROSSED_OUT)
        {
            if(current->prec == NULL)
            {
                current->been_there = NO;
                // no prec: increase r, row, col and back to 2)
                if(col < row)
                {
                    col++;
                }
                else
                {
                    if(row < t - 1)
                    {
                        row++;
                        col = 0;
                    }
                    else
                    {
                        if(r < R - 1)
                        {
                            r++;
                            row = 0;
                            col = 0;
                        }
                        else
                        {
                            // exit point;
                            flag = FALSE;
                        }
                    }
                }
                current = &table[r][row][col];
                current->prec = NULL;
                current->been_there = NO;
            }
            else
            {
                current->been_there = NO;
                copy = current;
                current = copy->prec;
                current->been_there = NO;
                // find index of sequent to mark out
                for(i = 0; i < sl; i++)
                {
                    if(current->sequent[i] == copy)
                    {
                        current->sequent_status[i] = CROSSED;
                        current->sequent[i] = NULL;
                        break;
                    }
                }
            }
        }
        else if((current == &table[r][row][col]) &&
                 ((current->prec != NULL) || current->been_there > NO))
        {
            // case (b same as starting point): not injective
            if(f != NULL)
            {
                fprintf(f, "-----------\n");
                fprintf(f, MSG);
                fprintf(f, "Local rule:\n");
                local_out(t1, localrule, f);
                fprintf(f, "\n is not injective: there is a periodic path starting and\n");
                fprintf(f, "ending with couple (\%lu, \%lu).\n", current->a, current->b);
                fprintf(f, "-----------\n");
                fclose(f);
            }
            // deallocate memory
            for(r = 0; r < R; r++)
                for(row = 0; row < t; row++)
                    free(table[r][row]);
            for(r = 0; r < R; r++)
                free(table[r]);
            free(table);
            // exit
            exitcode = 4;
            return exitcode;
        }
        else
        {
            // check whether box has valid sequents or not
            flag1 = FALSE;
            for(i = 0; i < sl; i++)
            {
                if(current->sequent_status[i] == NORMAL)
                {
```
```c
flag1 = TRUE;
break;
}
}
if (flag1 == TRUE)
{
    // it has some; case (c)
    current->been_there++;
    copy = current;
    current = copy->sequent[i];
    current->prec = copy;
}
else
{
    // it has none; case (d)
    if (current->merge_after != CROSS)
    {
        // case (i)
        current->status = CROSSED_OUT;
        current->been_there = NO;
    }
    else
    {
        // case (ii)
        if (current->prec == NULL)
        {
            current->been_there = NO;
            // no prec: increase r, row, col and back to 2)
            if (col < row)
            {
                col++;
            }
            else
            {
                if (row < t - 1)
                {
                    row++;
                    col = 0;
                }
                else
                {
                    if (r < R - 1)
                    {
                        r++;
                        row = 0;
                        col = 0;
                    }
                    else
                    {
                        // exit point;
                        flag = FALSE;
                    }
                }
            }
            current = &table[r][row][col];
            current->prec = NULL;
            current->been_there = NO;
        }
        else
        {
            current->been_there = NO;
            copy = current;
            current = copy->prec;
            current->been_there = NO;
            // find index of sequent to mark out
            for (i = 0; i < sl; i++)
            {
                if (current->sequent[i] == copy)
                {
                    current->sequent_status[i] = CROSSED;
                    break;
                }
            }
        }
    }
}
}
}
}

/* Step 5: Assigning valid merge_afters. Now we know that each
path must end in a box containing just a CROSS, and hence
each box will be assigned a merge_after number. The possibility
of a box not being assigned one comes into play only because
there may be periodic paths, but we excluded this in Step 4,
so this step may be skipped altogether.
*/
/* Step 6: verifying that the merging cannot diverge again. We
must check all non CROSSED_OUT boxes */
for (r = 0; r < R; r++)
{
    for (row = 0; row < t; row++)
    {
        for (col = 0; col <= row; col++)
        {
            if (table[r][row][col].status != CROSSED_OUT)
            {
                a = table[r][row][col].a / R;
                b = table[r][row][col].b / R;
                if (a == b)
                {
                    // localrule not injective
                    if (f != NULL)
                    {
                        fprintf(f, "-----------\n");
                        fprintf(f, MSG);
                        fprintf(f, "Local rule:\n");
                        local_out(t1, localrule, f);
                        fprintf(f, "\n is not injective: it diverges after having merged.\n");
                        fprintf(f, "Faulting couple: (%lu, %lu).\n", table[r][row][col].a, table[r][row][col].b);
```
Bibliografia

[AAV97] AAVV., *Properties of CA*, 1997, http://alife.santafe.edu/pub/topics/cas/postscript/properties.ps.gz.

[AP72] Serafino Amoroso e Yale N. Patt, *Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures*, Journal of Computer and System Sciences 6 (1972), 448-464.

[Ber66] R. Berger, *The undecidability of the domino problem*, Memoires of the American Mathematical Society 66 (1966).

[Ghi93] Giangiacomo Ghiglia, *Automi cellulari*, 1993.

[Hed69] G. A. Hedlund, *Endomorphisms and automorphisms of the shift dynamical system*, Mathematical Systems Theory 3 (1969), no. 4, 320-375.

[Kar91] Jarkko J. Kari, *Reversibility and surjectivity problems of cellular automata*, Journal of Computer and System Sciences 48 (1991), 149-182.

[Kar96] Jarkko J. Kari, *Representation of reversible cellular automata with block permutations*, Mathematical Systems Theory 29 (1996), 47-61.

[Kar97] Jarkko J. Kari, *Comunicazione privata*, 1997.

[Knu83] Donald E. Knuth, *The art of computer programming, part ii: Semi-numerical algorithms*, Addison-Wesley, Reading, Massachusetts, 1983.
[KR88] Brian W. Kerninghan e Dennis M. Ritchie, *The c programming language*, second ed., Prentice Hall, Englewood Cliffs, New Jersey, 1988.

[MD96] Christopher Moore e Arthur A. Drisko, *Algebraic properties of the block transformation on cellular automata*, Santa Fe Institute Working Papers (1996), http://www.santafe.edu/sfi/publications.

[Mel93] Luisa Mellano, *Complessità computazionale e proprietà algebriche degli automi cellulari*, 1993.

[Moo97] Christopher Moore, *Quasi-linear cellular automata*, Santa Fe Institute Working Papers (1997), http://www.santafe.edu/sfi/publications.

[Ric72] D. Richardson, *Tessellations with local transformations*, Journal of Computer and System Sciences **6** (1972), 373-388.

[Sat94] Tadakazu Sato, *Group structured linear cellular automata over $Z_m$*, Journal of Computer and System Sciences **49** (1994), 18-23.

[Sch96] Herbert Schildt, *Guida al linguaggio c++*, Mc Graw-Hill Libri Italia, Milano, 1996.

[WMO84] Stephen Wolfram, Olivier Martin, e Andrew M. Odlyzko, *Algebraic properties of cellular automata*, Communications in Mathematical Physics **93** (1984), 219-258.

[Wol83] Stephen Wolfram, *Statistical mechanics of cellular automata*, Reviews of Modern Physics **55** (1983), 601-644.

[WP85] Stephen Wolfram e Norman H. Packard, *Two-dimensional cellular automata*, Journal of Statistical Physics **38** (1985), 901-946.
Indice analitico

algebra, 16

algoritmo, 36, 87, 106, 109, 112

Amoroso, Serafino, 106, 109, 111

anello, 10, 20, 84, 103

automa cellulare

definizione di, 7, 10, 26

automi cellulari

infiniti, 103

base

conversione in, 37

sviluppo in, 114

cicli disgiunti, 85

condizioni al contorno, 10, 16, 99

configurazione, 103

“Giardino dell’Eden”, vedi GOE

finita, 104

insieme delle, 107

GOE, 106

parziale, 107

dipolinomio, 15

equivalenza di vettori, 70

estensione, 11, 22, 92

garden of Eden, vedi configurazione

GOE

generatore, 56, 74

gruppo, 69, 82, 117

ciclico, 14, 59, 74, 92

simmetrico, 13, 74

intorno, 10, 40, 90, 105

convenzionale, 10, 22, 37, 64

isomorfismo, 77

orbitale, 70

Kari, Jarkko J., 99

legge di evoluzione, 10, 20

localizzazione, 12, 34

matrice, 14, 29, 32

circolante, 14, 16

monoide, 21, 25, 27, 30, 40

Moore, Edward F., 106, 107

Myhill, John, 106, 107

numero di Wolfram, 22, 112

orbita, 33, 41, 45, 59

lunghezza, 59

periodo, 59

Patt, Yale N., 106, 109, 111

permutazione, 13, 18, 33, 47, 74, 82

polinomio, 15

prodotto

cartesiano, 74
semi-diretto, 75
punto di accumulazione, 108

raggio

d'azione, 10, 29, 37

destro, 10, 37, 87

negativo, 91

sinistro, 10, 37

rappresentazione

decimale, 38

globale, 82

locale, 37, 41, 70, 86, 90

orbitale, 61, 64, 73

rappresentazione locale, 64

regola "180", 99

regola "75", 101

regola "90", 22, 62, 72

regola locale, 11, 22, 92, 109

bilanciata, 109

restrizione, 107

Richardson, D., 106, 108

schema orbitale, 62, 64

seguente, 114

shift, 12, 21, 26, 29, 37, 92, 117

sottogruppo, 81, 82, 92, 93

normale, 82, 117

tabella dei seguenti, 113

tavola

dei caratteri, 82

dei cicli, 56

di moltiplicazione, 56, 69

trasformazione cellulare

lineare, 15

trasformazione cellulare, 12

iniettiva, 107

invertibile, 12, 69, 87, 103

banale, 95

lineare, 16

non lineare, 17

prodotto di, 24, 33, 45, 64

vettore, 18, 20