| edu/upv_ehu/gbg/docencia/perfectos/CalculadorDiversoDeNumerosPerfectos.java |
1 package edu.upv_ehu.gbg.docencia.perfectos;
2
3 import java.math.BigInteger;
4 import java.util.concurrent.ArrayBlockingQueue;
5 import java.util.concurrent.ThreadPoolExecutor;
6 import java.util.concurrent.TimeUnit;
7
8 /**
9 * Proporciona 5 alternativas para mostrar los números perfectos hasta un tope dado.
10 * De utilidad para ver cómo el planteamiento de algoritmos adecuados es importante,
11 * y para ver las posibilidades que da Java para realizar cómputos complejos.
12 *
13 * @author german
14 */
15 public class CalculadorDiversoDeNumerosPerfectos {
16 private CalculadorDiversoDeNumerosPerfectos(){}
17
18 //tiempo inicial para mostrar el acumulado hasta la obtención de cada perfecto.
19 //en los métodos BIG
20 private static long elapsedTimeControl;
21
22 //---------- METODO NAIF -------------------------------------------
23
24 /**
25 * Lleva a la salida estándar los perfectos hasta "max",
26 * probando para cada uno de ellos todos sus divisores.
27 *
28 * @param max número superior a considerar
29 */
30 public static void perfectosNaif(long max){
31 for (long candidato=1; candidato<=max; candidato++) {
32 long suma=0;
33 for (long divisor=1 ;divisor<candidato;divisor++) if (candidato%divisor==0) suma+=divisor;
34 if (candidato==suma) System.out.println(candidato);
35 }
36 }
37
38 //---------- METODO MEJOR -------------------------------------------
39
40 /**
41 * Lleva a la salida estándar los perfectos hasta "max",
42 * probando para cada uno los divisores hasta su raíz cuadrada y sumando los encontrados y sus complementarios.
43 *
44 * @param max número superior a considerar
45 */
46 public static void perfectosMejor(long max){
47 for (long candidato=1; candidato<max; candidato++) {
48 long suma=1;
49 for (int divisor=2;divisor<=Math.sqrt(candidato);divisor++) if (candidato%divisor==0) suma+=divisor+candidato/divisor;
50 if (candidato==suma) System.out.println(candidato);
51 }
52 }
53
54 //---------- METODO BUENO -------------------------------------------
55
56 /**
57 * Calcula perfectos mediante su expresión basada en primos de Mersenne (2<sup>ρ-1</sup>)*(2<sup>ρ</sup>-1).
58 *
59 * @param maxRo valor máximo de "p" en la fórmula a calcular
60 */
61 public static void perfectosBueno(int maxRo){
62 long ro=2, terminoA=2, terminoB=3;
63 Intentos:
64 for (; ro<=maxRo; terminoA<<=1, terminoB=(terminoB<<1) | 1L, ro++) {
65 for (int divisor=2; divisor<=Math.sqrt(terminoB);divisor++) if (terminoB%divisor==0) continue Intentos;
66 System.out.println(terminoA*terminoB);
67 }
68 }
69
70 //---------- METODO BIG ---------------------------------------------
71
72 /**
73 * Calcula perfectos mediante su expresión basada en primos de Mersenne (2<sup>ρ-1</sup>)*(2<sup>ρ</sup>-1),
74 * utilizando una representación numérica de precisión indefinida.
75 * OJO. El resultado no es seguro. La primalidad es probabilística.
76 * Para cada uno presenta: tiempo de ejecución acumulado (ms.), p (potencia de Mesrenne), número de cifras del perfecto, el perfecto
77 *
78 * @param maxRo máxima potencia (p en la fórmula)
79 * @param certainty factor de probabilidad del test de primalidad según err<=(1-1/2^factProb)
80 */
81 public static void perfectosBig(int maxRo,int certainty){
82 System.out.println("Certeza de primalidad: 1-1/2^"+certainty+" = "+(1-1.0/(1<<certainty)));
83 System.out.println(" t(seg.) ro long. perfecto");
84 String perfecto;
85 int ro=2;
86 BigInteger terminoA=new BigInteger("2"), terminoB=new BigInteger("3");
87 elapsedTimeControl=System.currentTimeMillis();
88 for (;ro<=maxRo;ro++, terminoA=terminoA.shiftLeft(1), terminoB=terminoB.shiftLeft(1).setBit(0))
89 if (terminoB.isProbablePrime(certainty))
90 System.out.printf("%10.3f seg. %6d %6d %s\n",(System.currentTimeMillis()-elapsedTimeControl)/1000.0,ro,(perfecto=terminoA.multiply(terminoB).toString()).length(),perfecto);
91
92 }
93
94 //---------- METODO BIGTHREADED --------------------------------------
95
96 /**
97 * Calcula perfectos mediante su expresión basada en primos de Mersenne (2<sup>ρ-1</sup>)*(2<sup>ρ</sup>-1),
98 * utilizando una representación numérica de precisión indefinida y usando todos los hilos del procesador.
99 * OJO. El resultado no es seguro. La primalidad es probabilística.
100 * La evaluación de cada candidato se delega en hilos "DeterminaPerfecto" que son ejecutados por un ThreadPool.
101 *
102 * @param maxRo máxima potencia (p)
103 * @param certainty certeza del test de primalidad según err<=(1-1/2^certainty)
104 */
105 public static void perfectosBigThreaded(int maxRo, int certainty,int numeroDeHilos) {
106 System.out.println("Ejecutando con "+numeroDeHilos+" hilos");
107 System.out.println("Certeza de primalidad: 1-1/2^"+certainty+" = "+(1-1.0/(1<<certainty)));
108 System.out.println(" t(seg.) ro long. perfecto");
109 ThreadPoolExecutor executor = new ThreadPoolExecutor(numeroDeHilos, numeroDeHilos, 1, TimeUnit.DAYS, new ArrayBlockingQueue<Runnable>(numeroDeHilos+4), new ThreadPoolExecutor.CallerRunsPolicy());
110 String perfecto;
111 int ro=2;
112 BigInteger terminoA=new BigInteger("2"), terminoB=new BigInteger("3");
113 elapsedTimeControl=System.currentTimeMillis();
114 for (;ro<=maxRo;ro++, terminoA=terminoA.shiftLeft(1), terminoB=terminoB.shiftLeft(1).setBit(0))
115 executor.execute(new DeterminaPerfecto(ro, terminoA, terminoB, certainty));
116 executor.shutdown();
117 try {executor.awaitTermination(1, TimeUnit.DAYS);
118 } catch (InterruptedException ex) {System.err.println("Oops! "+ex.getMessage());
119 }
120 }
121
122 /**
123 * Clase auxiliar que lleva la determinación de si un candidato es perfecto a un hilo, para poder lanzar varios candidatos en paralelo.
124 *
125 * Presenta el tiempo de ejecución acumulado (seg.), p (potencia de Mersenne), número de cifras del perfecto, el perfecto
126 */
127 private static class DeterminaPerfecto implements Runnable {
128 private final int ro,certainty;
129 private final BigInteger terminoA, terminoB;
130
131 public DeterminaPerfecto(int ro, BigInteger terminoA, BigInteger terminoB, int certainty) {
132 this.ro=ro;
133 this.terminoA = terminoA;
134 this.terminoB = terminoB;
135 this.certainty = certainty;
136 }
137
138 @Override
139 public void run() {
140 Thread.currentThread().setPriority(4);
141 String perfecto;
142 if (terminoB.isProbablePrime(certainty))
143 System.out.printf("%10.3f seg. %6d %6d %s\n",(System.currentTimeMillis()-elapsedTimeControl)/1000.0,ro,(perfecto=terminoA.multiply(terminoB).toString()).length(),perfecto);
144 }
145
146 }
147
148 }