I pacchetti di Java rendono disponibili ai programmatori funzioni molto potenti, non disponibili in altri linguaggi di programmazione. In una delle pagine precedenti si è usata, ad esempio, la classe GregorianCalendar i cui metodi permettono di ottenere numerose informazioni calendariali.
Per rappresentare valori numerici ed operare su di essi Java prevede i tipi predefiniti int, long, float, double comuni a molti altri linguaggi, che, per un dato di un certo tipo, allocano in memoria un numero prestabilito di bytes. Ciò implica che ognuno di questi tipi numerici ha un range limitato da un massimo e un minimo valore rappresentabile, cosa che in alcune applicazioni può rappresentare un problema. Se, ad esempio, il prodotto tra due dati di tipo long supera il massimo rappresentabile dal tipo il risultato è errato e se il programmatore non previene il rischio con una clausola try, può succedere che l'errore non venga rilevato causando il malfunzionamento inspiegabile dell'applicazione.
Per ovviare ai limiti dei tipi numerici standard in Java sono disponibili le classi BigInteger e BigDecimal.
Nell'esempio seguente si propone un'applicazione che stabilisca, usando i metodi della classe BigInteger, se un numero naturale, anche molto grande, è primo e, se non lo è, che fornisca la sua scomposizione in fattori primi.
Con valori di tipo long si potrebbero tentare gli illustrati nella pagina Numeri Primi ma per numeri molto grandi questi metodi inevitabilmente fallirebbero. La classe BigInteger permette di affrontare abbastanza agevolmente il problema.
Essa infatti, oltre a permettere di codificare numeri interi virtualmente senza limiti di range e di effettuare le più comuni operazioni aritmetiche su di essi, implementa funzioni come
Dato un BigInteger bi, se l'istruzione bi.isProbablePrime(20) risponde true, si può essere abbastanza sicuri che bi è primo.
In caso contrario è necessaria una procedura di scomposizione che, nell'esempio, usa un algoritmo dovuto a John M. Pollard. Questo algoritmo, dato un numero, se non è primo, lo scompone nel prodotto di due fattori. Se uno di questi fattori è primo viene aggiunto ad una lista creata come oggetto di classe java.util.ArrayList<E> dove <E> rappresenta la classe di oggetti da considerare insieme. Nell'esempio si definisce la classe Scomposizione come derivata da ArrayList<BigInteger>. Se un fattore non è primo, a sua volta viene ricorsivamente sottoposto all'algoritmo. La procedura continua fino a che tutti i fattori individuati sono primi. Nel caso in cui l'algoritmo fallisse si ricorre al crivello di Eratostene.
Una volta individuati tutti i fattori, dalla lista viene ricavato un array che viene ordinato in senso crescente in modo che tutti i fattori uguali nell'array risultano contigui. Da ogni gruppo di fattori uguali si ricava una potenza. Fattori singoli e potenze vengono infine trascritti nella stringa di output.
La sequenza di preparazione dell'applicazione è la seguente.
Questa è la grafica del progetto.
La definizione della classe Primi va completata con la redazione dei suoi metodi specifici non ereditati dalla classe JFrame che servono allo sviluppo dei calcoli matematici necessari.
Esempio.
/*
Applicazione Primi
Scomposizione in fattori primi di un numero naturale
*/
import java.awt.*;
import javax.swing.*;
import javax.swing.border.*;
import java.awt.event.*;
import java.math.BigInteger;
import java.util.GregorianCalendar;
import java.util.ArrayList;
import java.util.Arrays;
//==========================================================================
public class Primi
extends JFrame
implements ActionListener
{
Container contenitore;
JPanel pannello_intestazione, pannello_input, pannello_output;
JLabel label_intestazione;
JTextArea output;
CampoInput c_num, c_tempo;
JButton button_reset, button_calcolo;
BigInteger irrisolto;
long durata, durata_max, t_iniz, t_attuale;
boolean fine_tempo;
static BigInteger ZERO = new BigInteger("0");
static BigInteger UNO = new BigInteger("1");
static BigInteger DUE = new BigInteger("2");
Scomposizione SCOMPOSIZIONE;
CoppiaBI CBI;
//--------------------------------------------------------------------------
public Primi()
{
setTitle("Primi");
int larghezza = 700;
int altezza = 240;
setPreferredSize(new Dimension(larghezza,altezza));
setResizable(false);
contenitore = getContentPane();
contenitore.setLayout(new BoxLayout(contenitore,BoxLayout.Y_AXIS));
pannello_intestazione = new JPanel();
pannello_intestazione.setMaximumSize(new Dimension(larghezza,40));
pannello_intestazione.setBackground(new Color(70,180,80));
pannello_intestazione.setBorder(BorderFactory.createRaisedBevelBorder());
label_intestazione = new JLabel("Scomposizione");
pannello_intestazione.add(label_intestazione);
add(pannello_intestazione);
pannello_input = new JPanel();
pannello_input.setMinimumSize(new Dimension(larghezza,40));
pannello_input.setBackground(new Color(90,160,90));
pannello_input.setBorder(BorderFactory.createRaisedBevelBorder());
pannello_input.setLayout(new BoxLayout(pannello_input,BoxLayout.X_AXIS));
c_num = new CampoInput("numero",20,"",Color.cyan);
pannello_input.add(c_num);
c_tempo = new CampoInput("tempo max. (m)",3,"1",Color.cyan);
pannello_input.add(c_tempo);
button_calcolo = new JButton("CALCOLO");
button_calcolo.setBackground(Color.red);
button_calcolo.setActionCommand("calcolo");
button_calcolo.addActionListener(this);
pannello_input.add(button_calcolo);
add(pannello_input);
button_reset = new JButton(" RESET ");
button_reset.setBackground(Color.yellow);
button_reset.addActionListener(this);
button_reset.setActionCommand("reset");
pannello_input.add(button_reset);
pannello_output = new JPanel();
pannello_output.setPreferredSize(new Dimension(larghezza,80));
pannello_output.setBackground(new Color(30,220,140));
pannello_output.setBorder(BorderFactory.createRaisedBevelBorder());
output = new JTextArea(5,60);
pannello_output.add(output);
add(pannello_output);
}
//--------------------------------------------------------------------------
public void actionPerformed(ActionEvent e)
{
output.setText("");
String comando= e.getActionCommand();
if (comando=="reset")
{
c_num.setText("");
c_tempo.setText("1");
output.setText("");
return;
};
String input = c_num.getText();
if (input.length()==0)
{
output.setText("Errore: input vuoto");
return;
}
BigInteger big = new BigInteger("0");
String scompo = "";
boolean errore = false;
try
{
big = new BigInteger(input);
}
catch(Exception exc)
{
errore = true;
}
if (errore || (big.signum() < 1) || big.equals(UNO))
output.setText(input+": input non ammesso.");
else
{
scompo = scomposizione(big);
output.setText(scompo);
}
}
//---------------------------------------------------------------
String scomposizione(BigInteger bi) // stringa della scomposizione
{
durata_max = 60000;
String t = c_tempo.getText();
try
{
durata_max = Long.parseLong(t);
durata_max *= 60000;
}
catch(Exception exc)
{}
fine_tempo = false;
t_iniz = new GregorianCalendar().getTimeInMillis();
SCOMPOSIZIONE = new Scomposizione();
String scompo = bi.toString();
scomposizioneBI(bi);
int l = SCOMPOSIZIONE.size();
if ((l==1) && (!fine_tempo))
scompo += ": primo.";
else
scompo += " = "+SCOMPOSIZIONE.toString();
if (fine_tempo)
scompo += "\nTEMPO DI CALCOLO ESAURITO. ELABORAZIONE INTERROTTA.\nFATTORE IRRISOLTO: "+irrisolto.toString();
return scompo;
}
//---------------------------------------------------------------
void scomposizioneBI(BigInteger bi)
{
if (bi.isProbablePrime(20))
{
SCOMPOSIZIONE.add(bi);
return;
}
// se il numero è pari, dividerlo per 2 fino a che non si ottiene un resto dispari
while (bi.remainder(DUE).equals(ZERO)) // finché dividendo è pari
{
SCOMPOSIZIONE.add(DUE);
bi = bi.divide(DUE);
}
if (bi.equals(UNO))
return;
if (bi.isProbablePrime(20))
{
SCOMPOSIZIONE.add(bi);
return;
}
CoppiaBI pR = pollardRho(bi);
if (fine_tempo)
{
irrisolto = new BigInteger(bi.toString());
SCOMPOSIZIONE.add(irrisolto);
return;
}
if (!(pR.x.equals(UNO) || pR.y.equals(UNO)) )
{
if (pR.x.isProbablePrime(20))
SCOMPOSIZIONE.add(pR.x);
else
scomposizioneBI(pR.x);
if (pR.y.isProbablePrime(20))
SCOMPOSIZIONE.add(pR.y);
else
scomposizioneBI(pR.y);
return;
}
if (pR.y.equals(UNO))
crivello(pR.x);
else
crivello(pR.y);
}
//---------------------------------------------------------------------------------------------------
CoppiaBI pollardRho(BigInteger bi)
{
BigInteger a = new BigInteger("2");
BigInteger b = new BigInteger("2");
BigInteger diff, fattore;
do
{
a = funzionePollardRho(a,bi);
b = funzionePollardRho(b,bi);
b = funzionePollardRho(b,bi);
diff = a.subtract(b);
diff = diff.abs();
diff = diff.remainder(bi);
fattore = bi.gcd(diff);
if (fattore.compareTo(UNO)==1)
break ;
t_attuale = new GregorianCalendar().getTimeInMillis();
durata = t_attuale -t_iniz;
fine_tempo = durata>durata_max;
if (fine_tempo)
return null;
}while(!a.equals(b));
BigInteger q = bi.divide(fattore);
return new CoppiaBI(fattore,q);
}
//---------------------------------------------------------------------------------------------------
BigInteger funzionePollardRho(BigInteger x,BigInteger n)
{
x = x.multiply(x);
x = x.add(DUE);
x = x.remainder(n);
return x;
}
//---------------------------------------------------------------------------------------------------
void crivello(BigInteger bi) // crivello di Eratostene
{
BigInteger square;
BigInteger base = new BigInteger("3");
do
{
if (bi.equals(UNO))
return;
if (bi.isProbablePrime(20))
{
SCOMPOSIZIONE.add(bi);
return;
}
if (bi.remainder(base).equals(ZERO))
{
SCOMPOSIZIONE.add(base);
bi = bi.divide(base);
if (bi.equals(base))
{
SCOMPOSIZIONE.add(bi);
return;
}
if (bi.isProbablePrime(20))
{
SCOMPOSIZIONE.add(bi);
return;
}
}
else
{
base = base.nextProbablePrime();
square = base.multiply(base);
if (square.compareTo(bi)==1)
{
SCOMPOSIZIONE.add(bi);
return;
}
}
}while (true);
}
/**************************************************************************************/
class CampoInput
extends JPanel
{
TitledBorder titolo;
JTextField campo;
//---------------------------------------------------------------
//Costruttore
//---------------------------------------------------------------
CampoInput(String t, int w, String valore, Color colore)
{
setPreferredSize(new Dimension(w+16,40));
setMinimumSize(new Dimension(w+16,40));
setBackground(colore);
setBorder(BorderFactory.createRaisedBevelBorder());
titolo = BorderFactory.createTitledBorder(BorderFactory.createLineBorder(Color.black),t);
titolo.setTitleFont(new Font("SansSerif",Font.PLAIN,10));
setBorder(titolo);
setLayout(new FlowLayout(FlowLayout.CENTER,0,0));
campo = new JTextField(valore,w);
campo.setFont(new Font("SansSerif",Font.PLAIN,14));
campo.setMinimumSize(new Dimension(w,10));
add(campo);
}
//---------------------------------------------------------------
String getText()
{
return campo.getText();
}
//---------------------------------------------------------------
double getValue()
{
return Double.parseDouble(campo.getText());
}
//---------------------------------------------------------------
void setText(String t)
{
campo.setText(t);
}
//---------------------------------------------------------------
void setValue(double v)
{
campo.setText(String.valueOf(v));
}
//---------------------------------------------------------------
void reset()
{
campo.setText("");
}
}
/*********************** class Scomposizione *******************************************/
class Scomposizione
extends ArrayList< BigInteger>
{
public String toString()
{
int i, j;
int l = size();
BigInteger[] array = new BigInteger[l];
array = toArray(array);
Arrays.sort(array);
String sc = array[0].toString();
int conta = 1;
for(i=1; i < l; i++)
{
if (array[i].equals(array[i-1]))
conta++;
else
{
if (conta>1)
sc += "^"+conta;
sc += " x ";
sc += array[i].toString();
conta = 1;
}
}
if (conta>1)
sc += "^"+conta;
return sc;
}
}
/*********************** class CoppiaBI *******************************************/
class CoppiaBI
{
BigInteger x;
BigInteger y;
CoppiaBI(BigInteger X, BigInteger Y)
{
x = new BigInteger(X.toString());
y = new BigInteger(Y.toString());
}
//----------------------------------------------------------------------
public String toString() //CoppiaBI.toString()
{
return "{"+x.toString()+" , "+y.toString()+"}";
}
}
//--------------------------------------------------------------------------
public static void main(String args[])
{
Primi p = new Primi();
p.pack();
p.setVisible(true);
}
}
//==========================================================================
Il sorgente può essere scaricato da Primi.zip e scompattato in una cartella del proprio sistema.