BigInt

Implementazione di un intero unsigned a precisione illimitata.

Traccia

Si desidera sviluppare una gerarchia di classi Java per l’aritmetica di numeri interi (senza segno per semplicità) a precisione illimitata, ossia numeri con un arbitrario numero di cifre. Tali classi devono consentire, ad es., di calcolare una quantità come 2^128, che supera le capacità di calcolo degli interi long (a 64 bit). A questo scopo, le operazioni aritmetiche si possono eseguire secondo l’algoritmo carta-e-penna appreso nelle scuole inferiori, procedendo cioè cifra per cifra (dalla posizione meno significativa a quella più significativa), generando il riporto (o prestito) e utilizzandolo negli stadi successivi etc.
...
Predisporre un package poo.math. Quindi definire una interfaccia BigInt che astrae un intero senza segno a precisione illimitata supposto immutabile.
...
Mostrare un main di prova annidato in BigInt, che calcoli e mostri la quantità: 2^128.

ADT

L'Abstract Data Type BigInt si compone di Interfaccia che offre le funzionalità di più alto livello implementate come metodi default, una classe astratta Abstract BigInt che implementa l'interfaccia facendo l'override dei metodi di Object (toString, equals e hashCode) e un'implementazione tramite LinkedList chiamata BigInt, che implementa i rimanenti metodi dell'interfaccia.

Scelte progettuali

• operazioni aritmetiche: add, sub, mul, div, rem e poi sono tutte operazioni abbastanza ad alto livello da poter essere implementate tramite operazioni sempre più semplici fino ad arrivare alle operazioni increm decr che si basano molto sulla struttura dati sottostante. Nella pratica l'implementazione di incr è stata più un esercizio puramente didattico visto che, per motivi di performance, add è stata implementata tramite un override anche nella classe concreta;
  
• factory: il metodo di creazione di istanze per l'interfaccia è stato fondamentale per l'implementazione ad alto livello delle operazioni discusse sopra, nella classe concreta fa uso del costruttore tramite intero;
  
• metodi length e value: originariamente implementati entrambi come metodi di default stati surclassati da implementazione in BigInt che hanno migliorato le performance e/o ridotto l'ambiguità;
  
• in Abstract BigInt, i metodi fanno esteso uso della rappresentazione in forma di Stringa, siccome mi è sembrata la soluzione più bilanciata in termini di semplicità di implementazione e performance;
• data struttura: la struttura dati con cui è stata implementata la classe concreta (LinkedList) ha sicuramente definito la rappresentazione dell'intero "sotto la scocca". Per quanto riguarda il metodo value, ad esempio, originariamente la rappresentazione dell'intero partiva dalla cifra meno significativa nella struttura dati, quindi per evitare confusione ho preferito lasciarlo astratto nell'interfaccia anche dopo aver modificato l'implementazione. Ora l'intero è salvato come una lista di Integer con la più significativa come primo elemento. I costruttori rispecchiano questa scelta progettuale.
• costruttori: i tre costruttori ricevono rispettivamente un intero, una stringa e una LinkedList (di cui solo i primi due richiesti espressamente nella traccia). Quello tramite intero chiama il costruttore tramite stringa, che controlla tramite una regular expression la presenza di caratteri non numerici all'interno dell'input (questo previene l'inserimento di lettere e simboli non numerici, ma anche di numeri negativi nel primo costruttore). Il terzo costruttore (privato) tramite LinkedList, creato più che altro per comodità, permette la creazione di nuovi BigInt da restituire partendo dalle LinkedList dei due termini di ogni operazione aritmetiche (liste ottenute tramite il metodo privato bigInt ToOL). Questi ultimi metodi sono impostati privati perché le loro funzionalità sono necessarie solo all'interno delle operazioni sui BigInt, se fossero utilizzabili dall'utente renderebbero vano il tentativo di costruire il BigInt senza simboli non numerici (sarebbe possibile rendere pubblico il costruttore con LinkedList se preliminarmente avvenisse un join sugli elementi della lista per poi passarla come stringa al costruttore dedicato ma questo ridurrebbe ulteriormente le performance). In ogni caso entrambi (metodo e costruttore) sono fuori specifica quindi è meglio che non siano disponibili in ogni caso.

Performance e testing

Anche implementando solamente il metodo add a "basso livello" (addizione in colonna) le performance migliorano in maniera esponenziale durante la call del metodo pow (l'ho trovato ironico ma ce lo si poteva aspettare), infatti si passa da un'attesa di giorni a pochi secondi di computazione. Sarebbe stato possibile implementare anche moltiplicazione e divisione tramite algoritmi con carta e penna ma trovo che anche in questo stato le performance siano accettabili.
Tramite la classe Test è possibile verificare il risultato di 2^128 (come da traccia) inserendo da tastiera i due interi che rappresentano la base e l'esponente, per poi avere il confronto con lo stesso risultato della classe java.math.BigInteger: il test in questione mostra un messaggio di inizio del test, calcola e confronta i risultati di entrambe le classi, infine mostra un messaggio di conferma del risultato corretto o l'output dei metodi di entrambi gli oggetti in caso di risultato non conforme, infine mostra anche il tempo trascorso per eseguire il test (in secondi).
NB: nel tempo trascorso sono compresi sia le new che il calcolo della potenza di entrambi gli oggetti.