Est-ce possible d'optimiser davantage cet algorithme?

**darkxan** · 05/07/2008, 18h03

Intéressant. Cela me surprends mais pas plus que ça car Java utilise la compilation JIT. Java a donc une étape supplémentaire qui est la compilation de la boucle. Par contre, pourquoi il arrive à faire plus rapide ? Mystère, surtout que le code C++ est compilé avec l'option O3.

Mais là, on voit la puissance de Java, comme la fait Exoss, on peut faire une implémentation multi-threadé de l'algorithme qui améliore les performances (en tout cas sur sa machine). Et cette optimisation est moins évidente à mettre en place en C++ alors qu'en Java c'est immédiat.

**Exoss** · 05/07/2008, 20h17

Belle amélioration, mais je craint qu'il y ai une grosse différence de résultats.

En principe le calcul entre 10 et 2000000 devrait donner les nombres suivant :
11
101
1001
1078
1287
1364
10001
11096
100001
118183
1000001
1336634

Mais nous ne recevons que ceux-ci :
11
101
1001
10001
100001
1000001
1817492

D'autant plus que le nombre 1817492 n'est pas Lacroix

. Tout ce qui est en haut de la constante d'or (1,618... * 10^n) ne peut-être un nombre Lacroix

.

**®om** · 05/07/2008, 20h22

Tu as bien pris le fichier du post #37?

Car moi j'obtiens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
11
101
1001
1078
1287
1364
10001
11096
100001
118183
1000001
1336634
Algo1 : 861896432
11
101
1001
1078
1287
1364
10001
11096
100001
118183
1000001
1336634
Algo2 : 226250096
10
11
101
1001
1078
1287
1364
10001
11096
100001
118183
1000001
1336634
Algo3 : 96801478
10
11
101
1001
1078
1287
1364
10001
11096
100001
118183
1000001
1336634
Algo4 : 31337123

Seul le 3 est totalement correct.
Le 4 fonctionne plus rapidement, mais tu ne dois pas dépasser 2^32 pour le nombre à mettre au carré (et donc 2^64 pour le nombre mis au carré).

Sur les 2 premiers, il manque «10» (bah oui, 10² = 100, 10 - 0 = 10).

L'idéal serait donc de switcher d'algorithme dès que tu dépasses 2^32, ça permettrait d'être très rapide pour le début

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
new Algo3().execute(10, Integer.MAX_VALUE);
new Algo4().execute((long)Integer.MAX_VALUE + 1, Long.MAX_VALUE);

**Exoss** · 05/07/2008, 20h34

En fait, j'ai pris mon temps pour écrire mon message! Il aurait dû être placé directement après ton premier message. Je teste tout de suite votre nouvel algorithme!

**®om** · 05/07/2008, 20h45

Allez, voici un algo avec les 2 algos (avec des int et des longs), qui choisit celui à utiliser, et qui utilise tous les processeurs en parallèle (et donc les résultats ne sont pas forcément affichés dans l'ordre, mais c'est pas grave).
EDIT: je supprime le code, car buggé

EDIT2: en fait ça sert à rien, car les 2^32 premiers sont faits assez vite de toute façon, on peut toujours utiliser l'algo 3 !

Ça donne donc :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
public class FastLacroix {
 
	interface LacroixAlgorithm {
		void execute(long start, long end);
	}
 
	static class Algo3 implements LacroixAlgorithm {
		@Override
		public void execute(long start, long end) {
			final long[] powers10 = powers10Long();
			final int nbrDigitsMax = (int) Math.log10(end) + 1;
			end = end++;
 
			// Calcul de la première valeur
			long number = start;
			final long nbrSquared = number * number;
			int nbrDigits = (int) Math.log10(number) + 1;
			long divisor = powers10[nbrDigits - 1];
 
			long b1 = nbrSquared / divisor;
			long b0 = nbrSquared % divisor;
			long result = b1 - b0;
			if (result == number) {
				System.out.println(number);
			}
 
			number++;
			for (int i = nbrDigits; i <= nbrDigitsMax; i++, number++) {
				final long nbrMaxE = powers10[i];
				divisor = powers10[i - 1];
 
				final long endBoucle = Math.min(nbrMaxE, end);
				while (number < endBoucle) {
					final long newCalc = 2 * number - 1;
 
					b0 += newCalc % divisor;
					b1 += newCalc / divisor;
 
					if (b0 > divisor) {
						b0 = b0 - divisor;
						b1++;
					}
 
					result = b1 - b0;
 
					if (result == number) {
						System.out.println(number);
					}
 
					number++;
				}
 
				b1 = number;
				b0 = 0;
				result = number;
			}
 
		}
 
		private static long[] powers10Long() {
			long[] powers10 = new long[19];
			long l = 1;
			for (int i = 0; i < 19; i++) {
				powers10[i] = l;
				l *= 10;
			}
			return powers10;
		}
	}
 
	private static final int PROCESSOR_COUNT = Runtime.getRuntime().availableProcessors();
	private static ExecutorService EXECUTOR = Executors.newFixedThreadPool(PROCESSOR_COUNT);
	private static final long TASK_SIZE = 1l << 28;
	private static long current = 10;
 
	/**
         * @param args
         */
	public static void main(String[] args) {
		for(int i = 0; i < PROCESSOR_COUNT; i++) {
			EXECUTOR.execute(next());
		}
	}
 
	private static synchronized Runnable next() {
		final long current = FastLacroix.current;
		FastLacroix.current += TASK_SIZE;
		Runnable runnable = new Runnable() {
			@Override public void run() {
				LacroixAlgorithm algo = new Algo3();
				//System.out.println("nouvelle tâche");
				algo.execute(current, current + TASK_SIZE - 1);
				EXECUTOR.execute(next());
			}
		};
		return runnable;
	}
 
}

EDIT : ne fonctionne pas au-delà de 2^32, car la valeur initiale doit toujours être 2^32, et à chaque nouvelle tâche il y a une valeur initiale.
La valeur initiale doit donc être calculée par des BigInteger (juste 1 fois).

**Exoss** · 05/07/2008, 21h02

Je crois que c'est préférable de n'utiliser que l'algorithme 3, car je ne m'amuse pas à recalculer depuis le début

. Cependant, l'algorithme doit être en mesure de les calculer, même s'il est plus lent.

J'ai cette erreur en utilisant ton programme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
Exception in thread "pool-1-thread-2" java.lang.ArrayIndexOutOfBoundsException: 10
        at test.FastLacroix$Algo4.execute(FastLacroix.java:98)
        at test.FastLacroix$1.run(FastLacroix.java:166)
        at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:885)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:907)
        at java.lang.Thread.run(Thread.java:619)
Exception in thread "pool-1-thread-1" java.lang.ArrayIndexOutOfBoundsException: 10
        at test.FastLacroix$Algo4.execute(FastLacroix.java:98)
        at test.FastLacroix$1.run(FastLacroix.java:166)
        at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:885)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:907)
        at java.lang.Thread.run(Thread.java:619)

**®om** · 05/07/2008, 21h06

Tiens, une idée pour améliorer les perfs d'un facteur 10 : tous les nombres qui fonctionnent commencent par 1

**®om** · 05/07/2008, 22h21

Et l'idée mise en œuvre, avec 1 tâche par processeur. Chaque tâche correspond à un traitement pour tous les nombres d'un même nombre de chiffres (donc elles ne sont pas égales en temps, évidemment):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.math.BigInteger;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
public class FastLacroix {
 
	interface LacroixAlgorithm {
		void execute(int nbDigits);
	}
 
	static class Algo3 implements LacroixAlgorithm {
 
		@Override
		public void execute(int nbDigits) {
			final long[] powers10 = powers10Long();
 
			long number = powers10[nbDigits - 1]; // tous les nombres commencent par 1
			long taskEnd = 2 * number; // pour faire uniquement les nombres avec un certain nombre de digits qui
			// commencent par 1
			long divisor = number; // powers10[nbDigits - 1]
 
			BigInteger nbrSquared = new BigInteger(String.valueOf(number));
			nbrSquared = nbrSquared.multiply(nbrSquared);
			BigInteger divisorBigInteger = new BigInteger(String.valueOf(divisor));
			long b1 = nbrSquared.divide(divisorBigInteger).longValue();
			long b0 = nbrSquared.mod(divisorBigInteger).longValue();
 
			long result = b1 - b0;
			if (result == number) {
				System.out.println(number);
			}
 
			number++;
			while (number < taskEnd) {
				final long newCalc = 2 * number - 1;
 
				b1 += newCalc / divisor;
				b0 += newCalc % divisor;
 
				if (b0 > divisor) {
					b0 = b0 - divisor;
					b1++;
				}
 
				result = b1 - b0;
 
				if (result == number) {
					System.out.println(number);
				}
 
				number++;
			}
 
		}
 
		private static long[] powers10Long() {
			long[] powers10 = new long[19];
			long l = 1;
			for (int i = 0; i < 19; i++) {
				powers10[i] = l;
				l *= 10;
			}
			return powers10;
		}
	}
 
	private static final int PROCESSOR_COUNT = Runtime.getRuntime().availableProcessors();
	private static ExecutorService EXECUTOR = Executors.newFixedThreadPool(PROCESSOR_COUNT);
	private static int current = 1;
 
	public static void main(String[] args) {
		for (int i = 0; i < PROCESSOR_COUNT; i++) {
			EXECUTOR.execute(next());
		}
	}
 
	private static synchronized Runnable next() {
		final int current = FastLacroix.current;
		FastLacroix.current += 1;
		Runnable runnable = new Runnable() {
			@Override
			public void run() {
				try {
					LacroixAlgorithm algo = new Algo3();
					algo.execute(current);
					System.out.println("-- fin des nombres à " + current + " chiffres");
					EXECUTOR.execute(next());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		};
		return runnable;
	}
 
}

**darkxan** · 05/07/2008, 22h40

Une question qui n'est en rapport direct mais quelle est la valeur retourné par Runtime.getRuntime().availableProcessors(); avec un dual core ? Théoriquement, cela devrait retourner 1 car un double coeur n'est au sens strict qu'un seul processeur.

Par contre, je serais curieux de voir si les performances ne serait pas meilleur encore avec plus de threads qu'il y a de coeurs. Car on fait par des exemples des io avec les system.out donc le thread est bloqué, en plus, les processeurs ont plusieurs unités de calcul ils pourraient donc traiter peut être plus efficacement un nombre plus important de threads.

Tiens, une idée pour améliorer les perfs d'un facteur 10 : tous les nombres qui fonctionnent commencent par 1

Énorme ! Je n'avais même pas fait gaffe. Par contre, je n'ai aucune idée pour expliquer mathématiquement la chose.

A la fin, il faudra faire une comparaison avec tout premier programme d'Exoss pour voir la différence.

**®om** · 05/07/2008, 22h48

Ah ouais faudrait tester de mettre plus de threads…

Lancer le programme comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

java FastLacroix | tee log

Arrêter avec Ctrl + C, et ensuite pour avoir les résultats dans l'ordre sans les lignes qui commencent par -- :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cat log | grep -v ^-- | sort -n

Ou le nombre de résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cat log | grep -v ^-- | wc -l

**Exoss** · 05/07/2008, 22h50

Je peut te confirmer qu'avec mon ordinateur cela donne la valeur 2.

J'ai aussi remarqué qu'en augmentant le nombre de thread j'ai eu une augmentation importante des performances. Je ne l'ai pas calculé précisément, c'est plutôt empirique.

Je ne connait pas la classe executor. Est-ce vraiment mieux d'utiliser cette classe au lieu de créer plusieurs thread?

Edit :
J'ai éliminé les nombres tel que 11, 101, 1001 de ma liste. Rajouter les si cela vous semble mieux!

P.S. Tes lignes de commandes c'est uniquement pour les consoles linux si je ne me trompe pas?

**®om** · 06/07/2008, 12h08

Envoyé par darkxan

Envoyé par ®om

Tiens, une idée pour améliorer les perfs d'un facteur 10 : tous les nombres qui fonctionnent commencent par 1

Énorme ! Je n'avais même pas fait gaffe. Par contre, je n'ai aucune idée pour expliquer mathématiquement la chose.

Pour un nombre de n chiffres, on peut distinguer 2 cas :
(1)→ soit x < 10^(n+½), auquel cas x² est composé d'un nombre impair de chiffres (E(log₁₀(x²))+1 = 2n-1)
(2)→ soit x ≥ 10^(n+½), auquel cas x² est composé d'un nombre pair de chiffres (E(log₁₀(x²))+1 = 2n)
(avec 10^(n+½) ≈ 3,1623×10^n)

Dans le cas (1), on veut trouver {x/ x = E(x²/10^(n-1)) - E(x² mod 10^(n-1))}.

Si x∈[2×10^n;10^(n+½)], ie «x commence par 2 ou (3 et son carré a un nombre impair de chiffres)»,
alors le premier chiffre de x² sera d'au moins (x/10^n)², ie «supérieur ou égal au carré du premier chiffre de x».
si x commence par 2 → x² commence par k avec 4 ≤ k ≤ 8
si x commence par 3 (∧ E(log₁₀(x²))+1 = 2n-1, ie «x² a un nombre impair de chiffres») → x² commence par 9

Or, si l'on soustrait un nombre k' de (n-1) chiffres à un nombre k de n chiffres (on fait k-k'), le chiffre numéro (n-1) (en numérotant de droite à gauche à partir de 0) ne pourra pas être plus petit que ((le premier chiffre de k) - 1).
Exemple : 427 - 53 = 374 : on ne peut pas obtenir un nombre dont le premier chiffre est plus petit que 3 en soustrayant un nombre de 2 chiffres à 427. Au pire des cas, on aurait 427 - 99 = 328, on ne peut pas atteindre un nombre inférieur.

Donc si x commence par 2, x² commence par un nombre k entre 4 et 8, il est impossible en soustrayant les (n-1) derniers chiffres aux n premiers d'obtenir un nombre qui commence par 2.
Raisonnement identique si x commence par 3.

Dans le cas (2), on veut trouver {x/ x = E(x²/10^n) - E(x² mod 10^n)}.

On veut alors soustraire un nombre k' de n chiffres à un autre nombre k de n chifres (avec k les n premiers chiffres de x², k' les n derniers).
Pour que «ça marche», il faut que k≥k'. Lorsque c'est le cas, il faut également que k≥x, car on veut obtenir k-k'=x.
Or, cela n'est pas possible, car si au lieu de x², on prenait x×10^(log₁₀(x)+1), on aurait k=x. Or, évidemment, x<10^(log₁₀(x)+1), et donc x²<x×10^(log₁₀(x)+1), donc k<x.
Par exemple, au lieu de prendre 432², on prenait 432×1000, k vaudrait 432, k' vaudrait 0, et k-k'=432. Évidemment 432<1000, et donc 432×432 donne un nombre inférieur à 432000 (ici 186624, avec 186<432).

CQFD

Je suis persuadé qu'on peut encore restreindre l'ensemble à explorer concernant la suite des chiffres (pas uniquement le premier qui vaut 1).

Envoyé par Exoss

J'ai aussi remarqué qu'en augmentant le nombre de thread j'ai eu une augmentation importante des performances. Je ne l'ai pas calculé précisément, c'est plutôt empirique.

Attention à ne pas te laisser prendre par le fait que le 2e thread commence déjà par des nombres avec plus de chiffres, et donc que tous les nombres précédents ne sont pas encore traités (c'est pour ça qu'ils n'arrivent pas dans l'ordre).

Envoyé par Exoss

Je ne connait pas la classe executor. Est-ce vraiment mieux d'utiliser cette classe au lieu de créer plusieurs thread?

Ici, cela permet d'avoir un pool de threads, et de réutiliser ces threads sans en créer un nouveau à chaque fois. C'est mieux pour ce qu'on a besoin de faire.

Envoyé par Exoss

J'ai éliminé les nombres tel que 11, 101, 1001 de ma liste. Rajouter les si cela vous semble mieux!

Pourquoi cela?

Envoyé par Exoss

P.S. Tes lignes de commandes c'est uniquement pour les consoles linux si je ne me trompe pas?

Oui, c'est ça. C'est bien pratique ^^

Hier, après avoir laissé tourner un petit peu, voici 64 résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
1
10
11
100
101
1000
1001
1078
1287
1364
10000
10001
11096
100000
100001
118183
1000000
1000001
1336634
10000000
10000001
12727274
100000000
100000001
123529412
1000000000
1000000001
1019138757
1025974026
1097744361
1120879122
1140017878
1165991904
1237762239
1288553552
1307692308
1333666334
1405436669
1428571430
1447710186
1454545455
1473684212
1526315790
1545454547
1552289816
1571428572
1594563333
10000000000
10000000001
10440553516
11539644505
11980198021
100000000000
100000000001
101503588109
118690447106
120194035214
126086956523
127590544631
144777403628
146280991736
----------------
1000000000000
1000000000001
1036496350366

Là où sont les tirets, il peut manquer des nombres (car le thread des nombres à 12 chiffres avait pas fini son travail, tout comme celui des nombres à 13 chiffres n'a pas fini, mais ça c'est normal c'est la fin de la liste.

**®om** · 06/07/2008, 12h25

Envoyé par ®om

Je suis persuadé qu'on peut encore restreindre l'ensemble à explorer concernant la suite des chiffres (pas uniquement le premier qui vaut 1).

Ah bah oui, il suffit d'arrêter la tâche courante (pour un nombre de chiffres donné) dès que k-10^(n-1) > x. Car sinon k-k' donnera toujours un nombre > x.
En plus, on peut calculer la borne une fois pour toute au début de la tâche (car quadratique en fonction de x, il faut résoudre une équation du type ax²+bx+c), je vais essayer de l'implémenter.

**®om** · 06/07/2008, 13h58

Donc dans la version proposée jusqu'ici, on parcourait de 10 à 19, de 100 à 199, de 1000 à 1999, etc…

En fait, on peut faire encore un peu mieux, il suffit d'arrêter la tâche courante (pour un nombre de chiffres donné) dès que k > x + 10^(n-1). Car sinon k-k' donnera toujours un nombre > x.
Par exemple, si n=3 (donc x a 3 digits), et que x² s'écrit ABCDE, si ABC > x + 100, inutile de continuer, car DE est forcément < 100 (car 2 chiffres uniquement), et donc ABC-DE sera toujours > x.
Donc voilà pour l'idée, mais c'est bien gentil, on va pas se taper à chaque itération le calcul de x + 10^(n-1) simplement pour s'arrêter un peu plus tôt. Il faut calculer la borne une fois pour toute (pour un n -le nombre de chiffres de x- donné).

La borne que k ne doit pas dépasser pour un x donné est donc b = x + 10^(n-1). On cherche alors pour quel x cette borne est dépassée, auquel cas on n'a même plus besoin de chercher plus loin.

On va appeler d la distance de k à la borne : d = b - k
Évidemment cette fonction est décroissante en fonction de x.
On remarque (enfin en cherchant un peu et avec de l'intuition) que d peut s'exprimer comme un polynôme de second degré de x (variable) et de n (constant):
d = -x² + 10^(n-1) × x + 10^2(n-1)

On cherche d = 0 (car on veut connaître à partir de quel x on a k>b).
On résoud le polynôme, et là, magie, on tombe sur:
(1+sqrt(5))/2 × 10^(n-1)

Autrement dit, le nombre d'or multiplié par 10^(n-1).
Comme le nombre d'or vaut à peu près 1,618, on peut uniquement explorer les valeurs de 10 à 16, de 100 à 161, de 1000 à 1618…

Donc voilà encore un gain d'environ 38% de perfs

Et voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.math.BigInteger;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
public class FastLacroix {
 
	private static final double NOMBRE_D_OR = (1 + Math.sqrt(5)) / 2;
 
	interface LacroixAlgorithm {
		void execute();
	}
 
	static class Algo3 implements LacroixAlgorithm {
 
		private int nbDigits;
 
		Algo3(int nbDigits) {
			this.nbDigits = nbDigits;
		}
 
		@Override
		public void execute() {
			final long[] powers10 = powers10Long();
 
			long number = powers10[nbDigits - 1]; // tous les nombres commencent par 1
			long taskEnd = (long) (powers10[nbDigits - 1] * NOMBRE_D_OR); //2 * number;
			long divisor = number; // powers10[nbDigits - 1]
 
			BigInteger nbrSquared = new BigInteger(String.valueOf(number));
			nbrSquared = nbrSquared.multiply(nbrSquared);
			BigInteger divisorBigInteger = new BigInteger(String.valueOf(divisor));
			long b1 = nbrSquared.divide(divisorBigInteger).longValue();
			long b0 = nbrSquared.mod(divisorBigInteger).longValue();
 
			long result = b1 - b0;
			if (result == number) {
				System.out.println(number);
			}
 
			number++;
			while (number < taskEnd) {
				final long newCalc = 2 * number - 1;
 
				b1 += newCalc / divisor;
				b0 += newCalc % divisor;
 
				if (b0 > divisor) {
					b0 = b0 - divisor;
					b1++;
				}
 
				result = b1 - b0;
 
				if (result == number) {
					System.out.println(number);
				}
 
				number++;
			}
 
		}
 
		private static long[] powers10Long() {
			long[] powers10 = new long[19];
			long l = 1;
			for (int i = 0; i < 19; i++) {
				powers10[i] = l;
				l *= 10;
			}
			return powers10;
		}
	}
 
	private static final int PROCESSOR_COUNT = Runtime.getRuntime().availableProcessors();
	private static ExecutorService EXECUTOR = Executors.newFixedThreadPool(PROCESSOR_COUNT);
	private static int current = 1;
 
	public static void main(String... args) {
		for (int i = 0; i < PROCESSOR_COUNT; i++) {
			EXECUTOR.execute(next());
		}
	}
 
	private static synchronized Runnable next() {
		final int current = FastLacroix.current;
		FastLacroix.current += 1;
		Runnable runnable = new Runnable() {
			@Override
			public void run() {
				try {
					LacroixAlgorithm algo = new Algo3(current);
					algo.execute();
					System.out.println("-- fin des nombres à " + current + " chiffres");
					EXECUTOR.execute(next());
				} catch (Exception e) {
					e.printStackTrace();
				}
			}
		};
		return runnable;
	}
 
}

On est déjà bien à un facteur 400 en perfs par rapport à mon premier post là, sans compter la première optimisation de darkxan qui a déjà fait beaucoup

Voici 69 résultats :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
1
10
11
100
101
1000
1001
1078
1287
1364
10000
10001
11096
100000
100001
118183
1000000
1000001
1336634
10000000
10000001
12727274
100000000
100000001
123529412
1000000000
1000000001
1019138757
1025974026
1097744361
1120879122
1140017878
1165991904
1237762239
1288553552
1307692308
1333666334
1405436669
1428571430
1447710186
1454545455
1473684212
1526315790
1545454547
1552289816
1571428572
1594563333
10000000000
10000000001
10440553516
11539644505
11980198021
100000000000
100000000001
101503588109
118690447106
120194035214
126086956523
127590544631
144777403628
146280991736
153719008266
155222596374
1000000000000
1000000000001
1036496350366
-------- // peut-être (sans doute) d'autres manquants ici
10000000000000
10000000000001

**®om** · 06/07/2008, 16h20

Envoyé par Exoss

Chose intéressante, il n'y a pas de nombre Lacroix en haut du nombre d'or (constante 1,618...).

Arf, tu savais déjà ce que je viens de trouver

…

**darkxan** · 06/07/2008, 16h42

Très intéressant, j'avais regardé avec un nombre à trois chiffres avec la notation a2*10^2+a1*10+a0 pour voir comment ça se passait mais je n'étais pas allé aussi loin que toi.

Par contre, c'est vrai qu'Exoss tu aurais pu utiliser le fait qu'il n'y a pas de nombre de Lacroix au dessus du nombre d'or si tu le savais déjà.

La seule chose qui reste à faire avec ton algorithme je pense, c'est de tester d'augmenter le nombre de threads et regarder les performances. Puis, il ne reste plus qu'a lancer ton calcul sur tes machines et je pense que l'on pourra avoir tous les nombres jusqu'au plus grand long.

Par contre, je pense qu'il faudrait revoir la méthode de distribution des plages pour que ça soit plus équitable et éviter que le dernier thread fasse le plus gros boulot tout seul.

**Exoss** · 06/07/2008, 16h51

Citation:

Envoyé par Exoss Voir le message
J'ai aussi remarqué qu'en augmentant le nombre de thread j'ai eu une augmentation importante des performances. Je ne l'ai pas calculé précisément, c'est plutôt empirique.

Attention à ne pas te laisser prendre par le fait que le 2e thread commence déjà par des nombres avec plus de chiffres, et donc que tous les nombres précédents ne sont pas encore traités (c'est pour ça qu'ils n'arrivent pas dans l'ordre).

En fait, j'ai ma propre implémentation avec des threads depuis longtemps! Si tu aurais lu les messages depuis le début tu aurais su que je me suis fait une plateforme de calculs distribués avec une application serveur. En gros :
- application serveur qui découpe les tâches de calculs en paquets (200 millions ex) et distribue ceux-ci aux clients connectés.
- l'application serveur enregistre aussi mes nombres Lacroix au fur et à mesure qu'ils sont découvert, et garde en mémoire l'avancement des calculs.
-chaque clients possèdent plus d'une unité de calculs et je suis capable de calculer la vitesse de calculs par le nombre de paquets calculés en 1 min(un timer me sert de marqueur dans ma console).

Je trouve que ta version avec la classe executor est plus intéressante que ma simulation de pool de thread au niveau de la gestion de ceux-ci. Cependant, je crois que c'est plus intéressant de découper les calculs par paquets de 200 millions que par unités de 3,4,5 chiffres etc... Le travail avance beaucoup plus vite à deux thread qu'un seul. Aussi, cela nous donne la possibilité de découper en paquets pour distribuer la tâche sur plusieurs ordinateurs.

Pour ce qui est de la règle d'or, c'est déjà implanté depuis longtemps dans mon application serveur

.

**®om** · 06/07/2008, 16h59

Envoyé par Exoss

Je trouve que ta version avec la classe executor est plus intéressante que ma simulation de pool de thread au niveau de la gestion de ceux-ci. Cependant, je crois que c'est plus intéressant de découper les calculs par paquets de 200 millions que par unités de 3,4,5 chiffres etc... Le travail avance beaucoup plus vite à deux thread qu'un seul. Aussi, cela nous donne la possibilité de découper en paquets pour distribuer la tâche sur plusieurs ordinateurs.

Ouais, je trouve aussi, mais la découpe par nombre de chiffres permet de ne faire qu'une seule fois le calcul sur le BigDecimal, et ensuite c'est simplement des opérations sur b0 et b1.

Mais faudrait découper un peu plus, sinon les tâches sont interminables

**Exoss** · 06/07/2008, 17h20

Dès que tu arrive autour des nombres à 11-13 chiffres ça commence à valoir la peine de découper. Avant ça, les calculs se font plutôt rapidement.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Ouais, je trouve aussi, mais la découpe par nombre de chiffres permet de ne faire qu'une seule fois le calcul sur le BigDecimal, et ensuite c'est simplement des opérations sur b0 et b1.
Mais faudrait découper un peu plus, sinon les tâches sont interminables

Tu peut toujours effectuer le calcul qu'une seule fois sur le BigInteger! Par exemple, le nombre 144777403628 se tient dans la zone 144600000000 et 144800000000. Je ne fais pas le calcul 200 millions de fois puisque l'on a toujours le même nombre de chiffres. C'est sur que pour les nombres à 12 chiffres je le fait quand même à peut-prêt 300 fois pour un découpages en paquets de 200 millions... mais c'est déjà pas si pire non? On pourrait facilement augmenter à 2 milliards tellement les calculs se font rapidement maintenant

.

**®om** · 17/07/2008, 17h42

Alors, c'est quoi le plug grand que tu as trouvé?

Est-ce possible d'optimiser davantage cet algorithme?

Langage Java

Discussions similaires

Partager

Partager