Repository files navigation

Questo progetto nasce come risposta alla sfida lanciata dalla pagina facebook8bpri di scrivere un programma per una piattaforma 8 bit che trovi le prime 1000 triplette pitagoriche: aquesto link c'è la traccia completa della sfida.

La scelta è dettata principalmente da ragioni di interesse storico: questo compilatore (mai distribuito ufficialmente da Borland)è stato scritto da Martin Odersky (l'inventore diScala language) e non è mai stato usato da una massa critica di utenti. Pertanto è sia una scelta "sfidante" che un motivo per una ricerca filologica.

• source - Codice sorgente in Turbo Modula-2
  • pythagor.mod - Sorgente della soluzione alla "sfida".
• binary - File .COM eseguibili su sistemi CP/M-80
  • p-mcode.com Eseguibile compilato in "mcode"
  • p-native.com Eseguibile compilato in codice nativo
• dists - Raccolta di immagini di dischi CP/M per Commodore 64 (con scheda Z80) e Commodore 128 (incluso codice di boot di sistema)
  • pythagoras64.d64 - Disco per C64 (con scheda Z80), include sorgente e binari
  • pythagoras128.d64 - Disco per C128, include sorgente, binari e sistema minimale per il boot

La soluzione consiste nell'applicazione delteorema di Barning, che consente di ottenere tutte le terne pitagoriche avendo come input una di partenza, che tipicamente è la minimale(3, 4, 5). Ciò implica l'esplorazione di un albero infinito, pertanto diventa impossibile una sua esplorazione in termini di "Depth-Search", dato che questa tecnica presuppone un numero di nodifinito:

Viceversa, l'esplorazione è da effettuarein larghezza, tutti i nodi di un livello, prima di passare al successivo:

Ciò è stato implementato tramite una struttura acoda (queue):

PROCEDURE DoBreadthSearch();VAR value: VECTOR;    r: RESULTS;    i: CARDINAL;BEGIN    WHILE count < 1000 DO        INC(count);        Pull(value);        IF count >= 981 THEN           INC(lines);           Assign(output[lines], value);        END;        GetNext3(value, m, r);        FOR i := 1 TO 3 DO            Push(r[i])        END    ENDEND DoBreadthSearch;

Da notare il limite (1000) imposto nel cicloWHILE: senza questo limite non ci sarebbe (teoricamente) termine all'algoritmo, dato che l'albero da esplorare èinfinito.

NOTA: Per ottenere unaDepth Search (ricerca in profondità), ammesso che l'albero da esplorare siafinito, è sufficiente utilizzare una struttura dati apila (push-pop) anziché acoda (push-pull).

Per la rilevazione del tempo utilizzato è stato necessario (non avendo Turbo Modula-2 funzioni native in tal senso) ricorrere agli interrupt di CP/M, in particolare all'interrupt105 della componenteBDOS:

PROCEDURE GetTime(): LONGINT;CONST GetDT = 105; (* BDOS Function *)VAR dat: ARRAY[0..1] OF CARDINAL;    hour, minute, second: INTEGER;BEGIN    BDOS(GetDT,ADR(dat));    second := BcdToDec(IORESULT);    minute := BcdToDec(dat[1] DIV 256);    hour   := BcdToDec(INTEGER(BITSET(dat[1])*BITSET(65535)));    RETURN LONG(second) + (LONG(minute)*60L) + (LONG(hour)*3600L)END GetTime;

Tramite la chiamataBDOS viene richiamata la routine di sistema (disponibile solo nel CP/M 3.0, o "plus", e non nelle release precedenti come la 2.2) che restituisce:

• IORESULT, che contiene i secondi in formatoBCD
• la variabiledat, che contiene nei 16 bit meno significativi, ore e minuti, concatenati e in formato BCD (quindi "packed BCD")

Tramite una funzione che fa uso di operatoribitwise i valori BCD vengono convertiti in decimale:

PROCEDURE BcdToDec(n: INTEGER): INTEGER;BEGIN    RETURN (INTEGER(BITSET(n) * BITSET(240)) DIV 16) * 10          + INTEGER(BITSET(n) * BITSET(15))END BcdToDec;

Le prestazioni sono state misurate eseguendo il programma, sia in versione "m-code" che in codice nativo, su un emulatore di C128 in modalità CP/M

Riferimenti:

• Manuale di Turbo Modula-2
• CP/M + Turbo Modula-2: un'accoppiata interessante
• If only Borland had stuck with Turbo Modula-2 for CP/M