GabriXX01 ha scritto:
io ho scelto quello di creare il tipo BigInt mediante interfaccia(data dalla traccia), classe astratta e classe concreta e quindi di non utilizzare la classe speciale BigInteger, ma usando una LinkedList di Integer. Grazie a questa LinkedList posso creare numeri di qualsiasi lunghezza (quindi anche molto superiori ai classici long, int, ecc.), inserendo un numero per ogni cella.
Quando si vuole fare una classe di quel tipo, cioè che rappresenta un "valore", la prima, primissima, cosa da valutare e stabilire è se si intende realizzare una classe che definisce oggetti
mutabili o
immutabili. Quindi tu cosa hai scelto? La immutabilità in generale ha molti benefici.
Nel caso poi di un "big integer" cioè a precisione "arbitraria", la seconda cosa da valutare è come mantenere il valore, nel senso di: a) in
complemento a due; oppure b) in valore assoluto con segno mantenuto a parte.
Il
complemento a due chiaramente agevola e rende facilissime le somme/sottrazioni. Di meno, invece, le altre operazioni. Quindi tu cosa hai scelto?
Poi bisogna vedere come gestire il valore materialmente. Se gli oggetti sono immutabili, un LinkedList<Integer> è probabilmente un po' "troppo". Anche per il fatto che una lista "linkata" è poco utile/efficiente in questo contesto (meglio semmai un ArrayList).
Considera che nel "vero" BigInteger (quello del framework) c'è un banale array int[] (più pochi altri campi), quindi molto molto compatto.
GabriXX01 ha scritto:
Detto ciò, io ho già implementato i metodi di sottrazione e addizione, e per fare la moltiplicazione avevo anche pensato a un'iterazione dell'addizione, però la moltiplicazione dovrebbe essere di questa forma: public BigInt mul(BigInt m),
cioè che riceve un solo BigInt a sua volta come parametro, quindi essendo un qualsiasi BigInt non sempre posso portarlo sotto forma di long. La mia domanda è, esiste un modo per fare la moltiplicazione tra questi 2 numeri? In caso qualcuno sa suggerirmi un'idea? Ho pensato di implementare la moltiplicazione classica(quella fatta alle elementari, come inoltre ho fatto per sub e add) però non penso sia una cosa fattibile.
Per la moltiplicazione dipende da come hai rappresentato il valore. Se vuoi/puoi, mostra quanto hai fatto finora per somme/sottrazioni, giusto per capire cosa hai fatto.
Considera che il BigInteger del framework è molto ottimizzato, per la moltiplicazione utilizza varie tecniche ed algoritmi come il
Karatsuba multiplication algorithm e il
"optimal" 3-way Toom-Cook algorithm. Insomma, il BigInteger del framework è una implementazione altamente professionale. Nel tuo caso, essendo un esercizio, immagino non si debba arrivare a quel livello.