Discussion :

[Exoss]

Bonjour! Je ne suis pas débutant en Java, mais je ne connais pas très bien les structures de données et l'algorithmie.

Je me demandais s'il est possible de faire quelques optimisations sur le bout de code qui suivra plus tard. Je dois d'abord vous expliquer ce que fait mon algorithme.

Il s'agit d'une classe qui me permet de tester une particularité mathématique. Le test est simple. Prenez n'importe quel nombre positif et mettez-le au carré. Ex. : 1078 au carré = 1162084. Prenez les quatre premiers chiffres et soustrayez-les par les trois derniers. Ex. : 1162 - 084. Cela vous donne le nombre de départ, 1078. Il existe plusieurs autres nombres qui ont cette particularité.

Mon code maintenant. La fonction isNombreLacroix() me permet de trouver mes nombres (appelés Lacroix, du nom de son découvreur). J'y ai inclus un exemple d'utilisation de la fonction dans le Main. Comme vous pouvez le voir j'utilise intensivement les string. Y aurait-il une manière d'optimiser le code pour le rendre plus rapide?

Dans mon application générale je suis maintenant rendu à calculer dans les 13 chiffres, et cela prend pas mal de temps . Je me suis fait une plateforme de calculs distribués. Comme cela je peux utiliser mes quatre ordinateurs pour aller plus vite, mais c'est insuffisant. Je fais à peu près 27 millions de calculs par minutes avec mon parc informatique.

J'espère que ma question est claire .

Merci de votre aide!

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
package utilitaire;
 
import java.math.BigInteger;
 
/**
 * @author Philippe Bourdages
 */
public class NombreLacroix {
 
    private static BigInteger number;
    private static String numberSquared;
    private static Integer qtyChar;
    private static Integer qtyCharSquared;
    private static BigInteger nbrToSubtract;
    private static BigInteger nbrSubtracting;
    private static BigInteger result;
    private static Boolean valid;
 
    /**
     * Validation d'un nombre Lacroix.
     *
     * @return Boolean
     * @param arg BigInteger
     */
    public static synchronized boolean isNombreLacroix(final BigInteger arg) {
        number = arg;
        valid = false;
 
        numberSquared = number.pow(2).toString();
        qtyChar = number.toString().length();
        qtyCharSquared = numberSquared.length();
 
        nbrToSubtract = new BigInteger(numberSquared.substring(0, qtyChar));
        nbrSubtracting = new BigInteger(numberSquared.substring(qtyChar));
 
        /*Élimination des nombres lacroix qui résultent d'une
        soustractions par zéro et un. Ex: 1001 et 1000*/
        if (nbrSubtracting.compareTo(BigInteger.ONE) > 0) {
 
            result = nbrToSubtract.subtract(nbrSubtracting);
 
            /*Comparaison du nombre de départ et du nombre soustrait.
            S'ils sont égaux, alors c'est un nombe lacroix*/
            if (number.compareTo(result) == 0) {
                valid = true;
            }
 
        }
 
        return valid;
    }
 
    /*
     * Exemple d'utilisation de la classe...
     */
    public static void main(final String[] args) {
        long start = System.nanoTime();
 
        BigInteger i, iAdd, iMax;
        iAdd = new BigInteger("1");
        iMax = new BigInteger("2000000");
 
        for (i = new BigInteger("4"); i.compareTo(iMax) <= 0; i = i.add(iAdd)) {
 
            if (NombreLacroix.isNombreLacroix(i)) {
                System.out.println(i);
            }
        }
 
        long end = System.nanoTime();
        long elapsedNanoSeconds = end - start;
        System.out.println("time elapsed:" + elapsedNanoSeconds);
    }
}

[darkxan]

L'algorithme en lui même semble optimisé par contre après on descendre aux optimisations du point de vue langage.

Déjà, retire moi cet horrible synchronized, il te fait perdre pas mal de temps pour strictement rien. De plus, tu travailles avec des BigInteger or il serait préférable de travailler soit entièrement avec des long ou avec une combinaison entre des long et des int.

L'avantage aussi de travailler avec des types primitifs, c'est que tu ne perds pas de temps pour créer les objets et que les opérations sont bien plus rapides. Surtout que dans ton cas la précision des long et largement suffisant pour contenir le carré de ton nombre de départ.

Ou alors travailler avec Long et Integer. Peut être que les opérations sur les objets sont plus optimisés que ce que tu pourrais faire en Java sur les types primitifs.

Note : qtyCharSquared n'est jamais utilisé.

Peut être que quelque chose comme ça serait plus efficace. A voir si ce n'est pas encore avec number comme int avec des cast :

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
long numberSquared;
int nbChar;
long nbrToSubtract;
long nbrSubtracting;
long result;
 
long number = 4;
while(true) {
	numberSquared = number * number;
	nbChar = number.toString().length();
 
	nbrToSubtract = Long.parseLong(numberSquared.substring(0, nbChar));
	nbrSubtracting = Long.parseLong(numberSquared.substring(nbChar));
 
	result = nbrToSubtract - nbrSubtracting;
 
	if (number == result) {
		System.out.println(number);
	}
 
	number++;
}

[Exoss]

Quelques précisions :

• Je dois utiliser les BigInteger, car j'ai déjà dépassé la limite des Long. Le maximum des Long est 2^63, soit un nombre à 19 chiffres. Actuellement, je suis dans les nombres à 13 chiffres. Au carré, cela donne 25 chiffres. Je crois donc que l'utilisation des BigInteger est justifiée.
• J'ai mis la classe en synchronized, car je pensais créer plusieurs unités de calculs avec chacun un thread. Cependant, je ne suis pas sûr que cela m'apporte un gain quelconque. Oui, non?

Que puis-je faire pour améliorer les performances au niveau du langage?

Edit :
C'est vrai que qtyCharSquared ne sert à rien. J'ai supprimé deux structures if , avant de publier mon algorithme, qui utilisaient cette variable.

[darkxan]

Peut être que tes nombres font 25 chiffres au carré mais vu qu'ensuite tu travailles sur la moitié du nombre, rien ne t'empêche de travailler avec des long.

L'utilisation de synchronized ici est stupide. Si il y a avait plusieurs thread alors il serait bloqué à cause du synchronized, de plus rien n'empêcherait des threads de travailler sur la vérification de deux nombres distincts et donc probablement deux instances différentes de la classe. Si tu fais le travail sur des machines distinctes, il suffit de découper l'espace des données et dans un attribuer un à chaque machine. L'utilisation du mot clé synchronized est très couteux pour l'appel d'une méthode.

Pour les autres améliorations, regarde le code que j'ai proposé. J'ai enlevé l'appel de méthode, j'ai enlevé la comparaison dans le for pour le remplacer par un while, j'ai supprimé la variable inutile et remplacer tous par des long. Au vu de ton message précédent, il te suffit simplement de mettre le nombre au carré en BigInteger et laisser le reste en long.

[Exoss]

Je suis bien d'accord pour changer mon nombre de départ en long. De toute manière, quand j'aurai un nombre à 19 chiffres au carré, ça va prendre des lustres avant d'arriver à calculer les nombres à 20 chiffres.

J'ai des doutes pour ce qui est de l'appel d'une fonction avec le mot clé synchronized. Je n'ai pas vu d'amélioration notable. Selon les moyennes que j'ai calculées, il y avait une différence de 0.005 %. Pourtant, en théorie c'est bien évident que cela consomme plus...

Est-ce possible d'avoir de meilleures performances avec diverses unités de calculs en thread? Comment implanterais-tu ceci? J'ai une certaine idée, mais j'aimerais savoir la tienne.

Pour ce qui est du découpage des données, c'est déjà fait. C'est dans une autre classe cependant. Dans mon application serveur pour être plus précis...

P.S. Je ne suis pas sûr que le while est approprié si je veux découper mes données... C'est à dire se donner une zone de calcul ex. : calculer de 2 000 000 à 4 000 000 pour un ordinateur, et distribuer à un autre la zone de 4 000 000 à 6 000 000.

[darkxan]

Ce qui est important pour les long, c'est de travailler avec eux lorsque tu as découpé ton nombre en deux. En faite, tu ne travailles avec le BigInteger uniquement pour mettre le nombre au carré.

Le synchronized ne consomme pas énormément je crois que c'est 4 cycles pour un appel de méthode contre 700 pour un appel en synchronized. Sur nos machines ça ne donne pas un changement immense.

Pour les threads, la seule chose possible serait de lancer plusieurs fois le calcul avec des nombres distincts dans chaque Thread. Si ton pc est multi coeur alors peut être que ça améliorera les performances mais ce n'est pas dit. Tu peux faire le test en découpant la plage en deux avec deux Threads.

[Exoss]

Pas mal, cela me donne un gain d'environ 20 %.
J'ai enlevé le mot clé synchronized. Je ferai des tests plus tard.

Mes tests en nanosecondes :
Avant-
6373645254
6345403116
6308523569
6475563514
6424747558
-
En moyenne 6385576602.2

Après optimisation-
5353118343
5203194540
5123215381
5163872224
5337934570
-
En moyenne 5236267011,6

Je te dirais qu'il n'y a que ta boucle while que je ne comprends pas encore... Tout ce que je vois c'est qu'elle fait une boucle infinie : P.

Je teste le tout avec le reste de mon application!

Voici la nouvelle version :

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
package utilitaire;
 
import java.math.BigInteger;
 
/**
 * @author Philippe Bourdages
 */
public class NombreLacroix {
 
    private static long number;
    private static String numberSquared;
    private static int qtyChar;
    private static long nbrToSubtract;
    private static long nbrSubtracting;
    private static long result;
    private static boolean valid;
 
    /**
     * Validation d'un nombre Lacroix.
     *
     * @return boolean
     * @param arg long
     */
    public static boolean isNombreLacroix(final long arg) {
        number = arg;
        valid = false;
 
        numberSquared = new BigInteger(String.valueOf(number)).pow(2).toString();
        qtyChar = String.valueOf(number).length();
 
        nbrToSubtract = Long.parseLong(numberSquared.substring(0, qtyChar));
        nbrSubtracting = Long.parseLong(numberSquared.substring(qtyChar));
 
        /*Élimination des nombres lacroix qui résultent d'une
        soustractions par zéro et un. Ex: 1001 et 1000*/
        if (nbrSubtracting > 1) {
            result = nbrToSubtract - nbrSubtracting;
 
            /*Comparaison du nombre de départ et du nombre soustrait.
            S'ils sont égaux, alors c'est un nombe lacroix*/
            if (result == number) {
                valid = true;
            }
        }
 
        return valid;
    }
 
    /*
     * Exemple d'utilisation de la classe...
     */
    public static void main(final String[] args) {
        long start = System.nanoTime();
 
        long i, max;
        max = Long.parseLong("2000000");
 
        for (i = Long.parseLong("4"); i <= max; i++) {
            if (NombreLacroix.isNombreLacroix(i)) {
                System.out.println(i);
            }
        }
 
        long end = System.nanoTime();
        long elapsedNanoSeconds = end - start;
        System.out.println("time elapsed:" + elapsedNanoSeconds);
    }
}

[djo.mos]

Bonjour,
En enlevant les statics (plus quelques autres modifs mineures), j'arrive à améliorer le temps d'exécution de 12% ...

Nouvelle version:

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
public class NombreLacroix {
 
	private String numberSquared;
	private int qtyChar;
	private long nbrToSubtract;
	private long nbrSubtracting;
	private long result;
 
	/**
         * Validation d'un nombre Lacroix.
         * 
         * @return boolean
         * @param arg
         *            long
         */
	public boolean isNombreLacroix(final long arg) {
 
		numberSquared = BigInteger.valueOf(arg).pow(2).toString();
		qtyChar = String.valueOf(arg).length();
 
		nbrToSubtract = Long.parseLong(numberSquared.substring(0, qtyChar));
		nbrSubtracting = Long.parseLong(numberSquared.substring(qtyChar));
 
		/*
		 * Élimination des nombres lacroix qui résultent d'une soustractions par
		 * zéro et un. Ex: 1001 et 1000
		 */
		if (nbrSubtracting > 1) {
			result = nbrToSubtract - nbrSubtracting;
 
			/*
			 * Comparaison du nombre de départ et du nombre soustrait. S'ils
			 * sont égaux, alors c'est un nombe lacroix
			 */
			if (result == arg) {
				return true;
			}
		}
 
		return false;
	}
 
	private void calc() {
		long start = System.nanoTime();
 
		long i, max;
		max = 2000000l;
 
		for (i = 4l; i <= max; i++) {
			if (isNombreLacroix(i)) {
				System.out.println(i);
			}
		}
 
		long end = System.nanoTime();
		long elapsedNanoSeconds = end - start;
		System.out.println("time elapsed:" + elapsedNanoSeconds);
 
	}
 
	/*
	 * Exemple d'utilisation de la classe...
	 */
	public static void main(final String[] args) {
		new NombreLacroix().calc();
	}
}

Résultats:
* Algo Original:
2808185360
3048996098
2905201273
3462183910
3291724994
3059284529
-
3095929360 (moyenne)

* Version modifiée
3116381569
2881773951
2424079053
2573075706
2775559913
2531012838
-
2716980505 (moyenne)

Bon, nos machines sont différentes ça se voit (je suis sur un Q6600 : quad core à 2.4 GHz + OpenJDK/Linux).

[Exoss]

Je confirme une amélioration de 12 % supplémentaire versus la version de départ . Pour un total de 30 % avec les autres améliorations .

Je suis un peu surpris. J'avais ajouté les static justement pour gagner du temps, mais c'est le contraire qui se passe! Il semble y avoir un peu plus d'espace utilisé si je ne m'abuse?

Génial le coup du BigInteger.valueOf(arg).pow(2).toString();
Cela simplifie pas mal la ligne numberSquared = new BigInteger(String.valueOf(number)).pow(2).toString();

Je me demande cependant si c'était une bonne idée d'enlever la variable valid, car l'application PMD me dit que c'est une mauvaise pratique que d'avoir plus d'un seul return... "A method should only have one exit point, and that should be the last statement in the method."

//Au départ
6373645254
6345403116
6308523569
6475563514
6424747558
-
6385576602.2

//Après toutes les modifications
4540499701
4339018227
4517011519
4473696797
4501947873
-
4474434823,4

Je ne comprends pas trop tes résultats. Est-ce que tu as effectué le test pour 2 millions de nombres? et non 20 millions comme je vois dans ton code? Si c'est 20 millions, il y a effectivement une grosse différence entre nos deux processeurs : P.

Merci à vous deux pour toutes ces améliorations! Ça devrait faire avancer un peu plus vite ces calculs . Si jamais vous voyez autre chose, je suis preneur!

[vic]

Salut,

Une remarque sur le langage : synchronized signifie qu'un seul thread à la fois peut accéder à la méthode ... Donc exactement l'inverse de ce que tu cherches. Ensuite tu utilises des méthodes et variables statiques. C'est une mauvaise pratique et précisément un obstacle au multithreading. Il faut toujours utiliser des variables de classe pour que chaque instance de l'objet ait ses propres variables.

Pour créer plusieurs unités de calcul parallèles, c'est très simple, il suffit de créer un objet Thread pour chaque unité, de lui attribuer une plage de nombres à calculer et d'implémenter correctement la méthode run(). A priori ça aura surtout de l'intérêt sur une machine multiprocesseur, mais ça peut apporter un petit gain sur une machine monoprocesseur en remplissant les quelques moments où un thread dort pour accéder au disque ou aux I/O.

Pour ce qui est de l'optim, il est peut-être possible d'améliorer en utilisant 2 long pour stocker le nombre. Également certains calculs comme le calcul de la longueur du nombre sont fait à chaque itération alors qu'ils pourraient être faits uniquement à chaque puissance de 10.

On peut aussi remplaçer String.valueof(nombre).length() par (int)Math.log10(nombre) + 1.

Aurais-tu quelques valeurs de plus de 10 chiffres pour tester l'algorithme ?

P.S. : attention à PMD il reflète parfois plus un certain dogme que de réelles bonnes pratiques ...

[Exoss]

Salut Vic,

Merci pour les précisions à propos du mot clé synchronized! Cela apporte quelques éclaircissements sur la manière de procéder!

Je vais implémenter la possibilité d'avoir plusieurs unités de calculs dans l'application. Je n'ai pas grand-chose à faire pour y parvenir! Le plus gros est déjà fait. J'ai un ordinateur double coeur chez moi, alors c'est une bonne idée.

Pour ce qui est de l'optim, il est peut-être possible d'améliorer en utilisant 2 long pour stocker le nombre

Ah bon? En séparant le nombre en deux parties?

Également certains calculs comme le calcul de la longueur du nombre sont fait à chaque itération alors qu'ils pourraient être faits uniquement à chaque puissance de 10.

C'est une excellente idée. Elle est un peu difficile à implémenter dans mon système actuel, mais c'est possible.

On peut aussi remplaçer String.valueof(nombre).length() par (int)Math.log10(nombre) + 1.

Je suis curieux, alors j'essaie! Au pire, cela réduit le nombre d'objets String instancié.

Merci!

P.S. StyleChecker est encore plus dogmatique que PMD .

Edit :
La liste des 41 nombres trouvés jusqu'à présent :

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
1078
1287
1364
11096
118183
1336634
12727274
123529412
1019138757
1025974026
1097744361
1120879122
1140017878
1165991904
1237762239
1288553552
1307692308
1333666334
1405436669
1428571430
1447710186
1454545455
1473684212
1526315790
1545454547
1552289816
1571428572
1594563333
10440553516
11539644505
11980198021
101503588109
118690447106
120194035214
126086956523
127590544631
144777403628
146280991736
153719008266
155222596374
1036496350366

[Exoss]

J'ai implémenté l'optimisation :
(int)Math.log10(nombre) + 1 à toutes les puissances 10 = gain de 6.5 %
Merci Vic!!

J'en suis maintenant à -36,5 % qu'avant. En réalité, la nouvelle version est 57 % de plus rapide qu'avant : ).

Il ne me reste plus que l'augmentation de la quantité d'unités de calculs à tester, je crois.


Version à jour :

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
package utilitaire;
 
import java.math.BigInteger;
 
/**
 * @author Philippe Bourdages
 */
public class NombreLacroix {
    private String numberSquared;
    private long nbrToSubtract;
    private long nbrSubtracting;
    private long result;
 
    /**
     * Validation d'un nombre Lacroix.
     *
     * @return boolean
     * @param nombre long
     */
    public final boolean isNombreLacroix(final long nombre, final int qtyChar) {
        numberSquared = BigInteger.valueOf(nombre).pow(2).toString();
 
        nbrToSubtract = Long.parseLong(numberSquared.substring(0, qtyChar));
        nbrSubtracting = Long.parseLong(numberSquared.substring(qtyChar));
 
        /*Élimination des nombres lacroix qui résultent d'une
        soustractions par zéro et un. Ex: 1001 et 1000*/
        if (nbrSubtracting > 1) {
            result = nbrToSubtract - nbrSubtracting;
 
            /*
            * Comparaison du nombre de départ et du nombre soustrait.
            * S'ils sont égaux, alors c'est un nombe Lacroix
            */
            if (result == nombre) {
                return true;
            }
        }
 
        return false;
    }
 
    public final boolean isNombreLacroix(final long nombre) {
        int qtyCharRedirect = (int)Math.log10(nombre) + 1;
 
        return isNombreLacroix(nombre, qtyCharRedirect);
    }
 
 
    /*
     * Exemple d'utilisation de la classe...
     */
    public static void main(final String[] args) {
        NombreLacroix valideur = new NombreLacroix();
 
        long start = System.nanoTime();
 
        long i, max;
        max = 4000000;
        int qtyChar = (int)Math.log10(max) + 1;
 
        for (i = 2000000; i <= max; i++) {
            if (valideur.isNombreLacroix(i, qtyChar)) {
                System.out.println(i);
            }
        }
 
        long end = System.nanoTime();
        long elapsedNanoSeconds = end - start;
        System.out.println("time elapsed:" + elapsedNanoSeconds);
    }
}

[darkxan]

J'ai pensé à une idée qui pourrait améliorer le calcul, comme :

(X+1)^2 = X^2 + 2X + 1.

Tu pourrais donc calculer : nouveauCarre = ancienCarre + 2 * nombrePrecedent + 1;

L'avantage c'est que la multiplication par 2 est juste un ajout de zéro à droite en binaire et qu'ensuite il ne reste plus que deux additions dont une incrémentation. La question est de savoir si avec les BigInteger ça peut donner un meilleur résultat.

Voilà une proposition, ce n'est pas dit que ça améliore quelque chose à cause de l'obligation de passer par un BigInteger pour faire l'addition.

Code :

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

1
2
3
4
long ltmp = 2 * nombrePrecedent + 1;
BigInteger btmp = BigInteger.valueOf(ltmp);
BigInteger numberSquared = BigInteger.valueOf(ancienCarre);
numberSquared.add(btmp);

PS: Je ne comprends pas pourquoi tu travailles avec une méthode et des membres de classe. Autant tout faire dans le main et travailler avec des variables locales. Tu n'as pas d'appel de fonction et pas d'accès à des variables de classe. Certes le gain de temps est ultra minime mais pourquoi s'en privé ?

EDIT : Je pense avoir trouvé un meilleur algorithme que voici, il est bassé sur ma réflexion précédente :

Soit X(i-1) le nombre de l'itération précédente et R(i-1) le résultat. l étant le nombre de chiffres de X.

Soit X(i) = X(i-1) + 1
X(i)^2 = X(i-1)^2 + 2*X(i-1) + 1
T(i) = 2*X(i-1) + 1 = b0 + b1*10^(l-1)
R(i) = R(i-1) + b1 - b0

Ex:
X(i-1) = 11 096, X(i-1)^2 = 123121216, R(i) = 11 096
X(i) = 11 097 T(i) = 22193 R(i) = 8 905

Donc en conclusion, il n'est pas nécessaire de calculer le carré (sauf celui de départ qui nous servira de base) et donc on peut travailler uniquement avec des long !

[Exoss]

Je ne peut pas mettre ce code dans la fonction main, car il est utilisé à divers endroits dans le reste de mon application de calculs distribués. Cette classe est en réalité une fonction utilitaire. Je ne sais pas si j'ai bien fait de mettre cette fonction à part dans une classe plutôt que dans ma classe d'unité de calculs, mais elle est aussi utilisé par mon application serveur.

À propos des variables en membres de classe au lieu de simple variables locales. C'est un choix que j'avais fait lors de la réalisation de la classe, comme l'utilisation du mot clé static, afin de limiter la création d'objets. Je ne suis plus certain de l'effet obtenu par cette pratique. Je vais faire des tests à nouveau. Je vais aussi essayer ton algorithme, même si j'avoue le trouver un peu complexe et difficile à relire .

Malheureusement, je n'ai vraiment pas d'autres choix que d'utiliser le BigInteger. Si tu regarde le dernier nombre que j'ai trouvé, 1036496350366, tu comprendra qu'une fois au carré le long ne peut plus être utilisé. À moin que j'ai mal compris l'utilisation de ton algorithme .

Merci encore de ton aide! Elle est appréciée

P.S. Les essais avec les thread sont très concluant! J'ai doublé ma vitesse de calculs sur mon ordinateur double coeur, et même plus!!

[darkxan]

Effectivement, tu n'as pas compris.

Dans ma première solution, je te proposais de calculer le carré sans faire de multiplication et en utilisant des BigInteger. C'est le code que j'ai mis dans mon message précédent.

Une deuxième solution que j'ai explicitée après consiste à ne plus calculer le carré et à se servir du résultat de la soustraction précédente pour calculer le nouveau résultat. Il n'y a donc plus le carré à calculer et donc on travaille uniquement sur des long.
Les seuls calculs à faire dans la boucle sont :
- V = 2*X(i-1) + 1
- Découper V : (b1, b0)
- R(i) = R(i-1) + b1 - b0

Je te laisse relire mon message précédent pour comprendre le fonctionnement.

[Exoss]

Tes variables ne sont pas très bien expliquées. B1 et Bo correspondent à? Tu as quelques erreurs dans tes calculs.

Soit X(i-1) le nombre de l'itération précédente et R(i-1) le résultat.
l étant le nombre de chiffres de X.

Soit X(i) = X(i-1) + 1
X(i)^2 = X(i-1)^2 + 2*X(i-1) + 1
T(i) = 2*X(i-1) + 1 = b0 + b1*10^(l-1)
R(i) = R(i-1) + b1 - b0

Ex:
X(i-1) = 11 096, X(i-1)^2 = 123121216, R(i) = 11 096
X(i) = 11 097 T(i) = 22193 R(i) = 8 905

X(i) = 11096 + 1 (ok)
X(i)^2 = 123121216 + 2*11096 + 1 = 123143409 (il te faut le carré
du nombre précédant? pas le choix d'un BigInteger)
T(i) = 22192 + 1 = b0 + b1*10^(5-1) (Elles représentent quoi ces variables?)
R(i) = R(11096-1) + b1 - b0 (le résultat du nombre précédant? X(i-1) ?)

X(i-1) = 11 096, X(i-1)^2 = 123121216, R(i-1) = 11 096 (petite erreur ici?)
X(i) = 11 097 T(i) = 22193 R(i) = 8 905


Même chose pour :
- V = 2*X(i-1) + 1
- Découper V : (b1, b0)
- R(i) = R(i-1) + b1 - b0

Au moins, il n'y a pas de mise au carré dans cette version simplifiée, mais j'ai toujours besoin de savoir ce que représente R(i-1) et b1-b0.

Montre-moi une version avec les données dans les variables s'il te plaît.

[darkxan]

Le calcul du résultat R (qui est la soustraction) se calcul comme une suite. C'est à dire que l'on initialise le premier résultat puis on peut calculer tous les suivants à partir du résultat précédent.

Pour résumé :
1) Calculer R en utilisant ton ancienne méthode. (Sera effectué une seule fois).
2) Nouvelle boucle qui se sert du précédent pour calculer le R suivant.


La notation que j'utilise est simple : R(i) corresponds au résultat de l'on veut calculer et R(i-1) corresponds au résultat précédent que l'on a déjà calculé.

Voilà un nouvel exemple :
1) Initialisation pour X = 11097,
R = 8905 (calculé avec ta méthode)
On pose R(i-1) = 8905


2) Boucle :

Itération 1 : pour 11098
* T(i) = 2 * X(i-1) + 1 = 2 * 11097 + 1 = 22 195
* b1 = 2
* b0 = 2195
* R(i) = R(i-1) + b1 - b0 = 8905 + 2 - 2195 = 6 712
On pose R(i-1) = R(i)

Itération 2 : pour 11099
idem

[Exoss]

Je m'excuse de te dire cela, mais ton algorithme ne fonctionne pas . C'est dommage parce que le temps de calcul aurait été réduit de beaucoup.

Un petit exemple s'impose.

Initialisation :
X = 11095
x^2 = 11095^2 = 123099025
R(i) = R(i -1) = 12309 - 9025 = 3284

Boucle :
Ici le prochain nombre, 11096, devrait être valide si on applique la méthode d'en haut qui utilise la mise au carré.

T(i) = 2*(i-1) + 1 = 2 * (11096 - 1) + 1 = 22191
b1 = 2
b0 = 2191
R(i) = R(i-1) + b1 - b0 = 3284 + 2 - 2191 = 1095

alors que
11096^2 = 12312|1216
12312 - 1216 = 11096

si on continue :
T(i) = 2*(i-1) + 1 = 2 * (11097 - 1) + 1 = 22193
b1 = 2
b0 = 2193
R(i) = R(i-1) + b1 - b0 = 1095 + 2 - 2193 = -1096

alors que
11097^2 = 12314|3409
12314 - 3409 = 8905

En conclusion, c'est une particularité de la mise au carré et je ne crois pas que l'on puisse faire autrement... Chose intéressante, il n'y a pas de nombre Lacroix en haut du nombre d'or (constante 1,618...).

[darkxan]

Ah, effectivement il y a un problème de propagation de retenu... J'ai trouvé la solution, il ne faut pas travailler R(i-1) mais avec les morceaux du carré.

11 095 :
R(i-1) = b1(i-1) - b0(i-1) = 12309 - 9025 = 3284

11 096 :
T(i) = 2 * 11095 + 1 = 22191
b0(i) = 2191 + b0(i-1) = 11216
b1(i) = 2 + b1(i-1) = 12310

Si b0(i) > 10^5
alors
b0(i) = 1216
b1(i)++ = 12311

R(i) = b1(i) - b0(i) = 11096

[Exoss]

Désolé, cela ne fonctionne vraiment pas... Essaie de l'implanter et tu verras qu'il est impossible d'obtenir les mêmes nombres :

1078
1287
1364
11096
118183
1336634

Je me suis essayé. C'est un peu brouillon, j'en conviens...

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
package client;
 
/**
 *
 * @author Phil
 */
public class NombreLacroix2 {
 
    public static void main(String[] args) {
        //Zone a calculer
        long nbrActuel = 5;
        long nbrFin = 2000000;
 
        //Calculs avant la boucle
        int qtyChar;
        String numberSquared;
        long nbrToSubtract;
        long nbrSubtracting;
        long result;
 
        numberSquared = new Long(nbrActuel * nbrActuel).toString();
        qtyChar = (int) Math.log10(nbrActuel) + 1;
 
        nbrToSubtract = Long.parseLong(numberSquared.substring(0, qtyChar));
        nbrSubtracting = Long.parseLong(numberSquared.substring(qtyChar));
 
        result = nbrToSubtract - nbrSubtracting;
 
        //Calculs sans mise au carré
        for (long number = nbrActuel + 1; number <= nbrFin; number++) {
            String preResult = new Long(2 * (number - 1) + 1).toString();
 
            nbrSubtracting = Long.parseLong(preResult.substring(1)) + nbrSubtracting;
            nbrToSubtract = Integer.parseInt(preResult.substring(0, 1)) + nbrToSubtract;
 
            if (nbrSubtracting > 10000) {
                nbrSubtracting = Long.parseLong(String.valueOf(nbrSubtracting).substring(1));
                nbrToSubtract = nbrToSubtract + 1;
            }
 
            result = nbrToSubtract - nbrSubtracting;
 
            if (number == result) {
                System.out.println(result + ": NombreLacroix!!");
            }
 
            //System.out.println((number) + " var : " + nbrToSubtract + "-" + nbrSubtracting + "=" + result);
        }
    }
}