Division Euclidienne en Binaire

Version imprimable

Voir 40 message(s) de cette discussion en une page

01/05/2019, 12h11
Black Confucius

Citation:

Envoyé par unparia

Bonjour Black Confucius

J'ai donc compris que tu t'étais "lancé" dans la recherche du plus grand nombre premier supérieur au record actuel (que détient, si ma mémoire ne me trompe pas, un ressortissant indien... mais n'en suis pas certain)

J'appelle à tout hasard ton attention sur le fait que la détermination rigoureuse du modulo (si nul dans les divisions successives par des premiers déjà connus -->> nb non premier) n'est pas indispensable.

Je ne vais pas développer ce mécanisme, mais t'en soumettre la pensée à tout hasard -->>

Qu'est le "déroulement" d'une division de type scolaire (donc par traitement d'un dividende et d'un diviseur exprimé sous forme de chaînes de caractères), sinon la détermination, par tranches décalées du nombre de soustractions du diviseur tant que la tranche traitée lui est supérieure ? Et quand devenue inférieure, on "décale" de 1 ce qui reste de la tranche en lui ajoutant le caractère suivant du dividende.
On sait que le modulo est différent de 0 si, in fine (lorsque plus de décalage possible), le diviseur est supérieur au résultat de la dernière soustraction alors que ce résultat est différent de 0.
Nous n'avons pas besoin d'en calculer la valeur puisqu'il suffit de déterminer si elle est >= 0

Bon courage (tu t'es lancé dans un sacré défi, si tu cherches à battre le record actuel;))

Merci Unparia

Oui sacré défi en tous cas ! Le seul problème demeure le temps de calcul exorbitant --> donc l'objectif est de trouver une astuce qui permette d'avoir un résultat de calcul en un temps acceptable, sachant que tout ceci est à l'intérieur d'une boucle presque éternelle elle aussi!
Je vous tiendrai au courant de mes avancées (si jamais cela donne quelque chose) si cela vous intéresse.

Par ailleurs, je pense que si tous les humains étaient des développeurs, la guerre n'existerait nulle part.
Je ne jamais vu, nulle part ailleurs, une communauté aussi déterminée à s'investir et s'entraider dans la recherche de solutions aux problèmes des autres.

Bonne fête du travail !
01/05/2019, 12h29
unparia

Citation:

Je ne jamais vu, nulle part ailleurs, une communauté aussi déterminée à s'investir et s'entraider dans la recherche de solutions aux problèmes des autres.

Si Si ! ... regarde autour de toi ... Les communautés de pêcheurs, par exemple... Et pas uniquement eux ... ;)

Ceci dit : Selon ce qui m'est rapporté, le record actuel (du nombre premier le plus élevé connu) a nécessité l'utilisation des ressources de plusieurs machines et n'a pas utilisé VBA.
Bonne fête du travail à toi également.
02/05/2019, 01h38
Black Confucius

Citation:

Envoyé par unparia

Si Si ! ... regarde autour de toi ... Les communautés de pêcheurs, par exemple... Et pas uniquement eux ... ;)

Tu as raison: il y a les chasseurs aussi, les alpinistes, les spéléologues, les bédouins dans le désert, etc...

Citation:

Envoyé par unparia

Ceci dit : Selon ce qui m'est rapporté, le record actuel a nécessité l'utilisation des ressources de plusieurs machines et n'a pas utilisé VBA.

C'est moins une question d'outil que de méthode je crois savoir. Le meilleur pilote n'est pas forcément celui qui a la voiture la plus puissante :lol:
02/05/2019, 06h51
unparia

Citation:

Le meilleur pilote n'est pas forcément celui qui a la voiture la plus puissante

Certes, mais même le meilleur pilote au monde ne saurait faire au volant d'une 2 CV ce qu'il saurait faire avec une formule 1
A lire ? --->>
https://fr.wikipedia.org/wiki/Calcul_distribu%C3%A9
C'est d'ailleurs sur ce "tissu" que s'appuie actuellement le programme GIMPS (Great Internet Mersenne Prime Search)

PS : à moins, bien entendu, d'être suffisamment fortuné (énormément fortuné******) pour s'offrir ce genre de luxe --->>
https://fr.wikipedia.org/wiki/Superordinateur
Quand la puissance, la complexité et le nombre des calculs sont l'élément majeur, la partie "software" ne saurait faire face, seule, aux faiblesses et limites de la partie "hardware".

******) Titan coûte actuellement un peu moins de 100 millions de dollars.
Sans parler des coûts annexes très importants (consommation énorme d'électricité pour le calculateur lui-même, les systèmse de refroidissement, du maintien de l'hygrométrie, etc...)
02/05/2019, 08h46
Black Confucius

Merci pour tes infos :roll: (dont je connaissais déjà la plupart ...)
C'est encourageant en tous cas de voir que des personnes partagent ma curiosité et mon élan sur cette problématique.
J'expérimente quelques idées on verra bien.
Verdict dans quelques semaines, quelques mois, ... ou quelques éternités selon la vitesse de ma tortue :ptdr: (laptop + vba)
I will do it, or die trying it !!!
02/05/2019, 08h56
unparia

Bien
Je crois que l'on a "fait le tour" (du moins en ce qui me concerne) de la question.

Juste un point encore (si ta machine a beaucoup de "place")

Tu peux déjà éviter de tester tous les nombres qui seraient un multiple de chacun des nombres premiers déjà connus (dont tu dois bien évidemment dresser une liste). Ces nombres (à ne pas tester) doivent alors eux-mêmes être recensés dans une liste également (il va te falloir de la place ...).
02/05/2019, 09h12
Black Confucius

Citation:

Envoyé par unparia

Bien
Je crois que l'on a "fait le tour" (du moins en ce qui me concerne) de la question.

Juste un point encore (si ta machine a beaucoup de "place")

Tu peux déjà éviter de tester tous les nombres qui seraient un multiple de chacun des nombres premiers déjà connus (dont tu dois bien évidemment dresser une liste). Ces nombres (à ne pas tester) doivent alors eux-mêmes être recensés dans une liste également (il va te falloir de la place ...).

Merci.
Bien sûr qu'il ne faut pas tout tester --> et donc mettre une stratégie de recensement, soit dans une liste, soit par évaluation de certaines conditions dans la boucle de test de primalité...

Je crois que je vais mettre en "résolu", pour ne pas laisser des discussions pendantes ...

Bonne continuation et merci encore !
02/05/2019, 09h17
unparia

Citation:

soit par évaluation de certaines conditions dans la boucle de test de primalité...

oui, mais --->> calculs --->> lenteur de plus ;)

Amitiés et bon(ne) courage/patience

EDIT : lorsque l'on a établi la liste, à partir du plus grand nombre premier connu, de tous les multiples supérieurs à ce nombre, de chacun des nombres premiers déjà connus, on l'a établie d'un seul coup par multiplications. Tout nombre au dessus du dernier plus grand nombre premier connu qui ne se trouverait pas dans cette liste répond forcément au critère de primarité. Et on n'a fait que des multiplications (aucune division ni modulo) au lieu d'un test de primarité pour chaque nouveau nombre testé.
On peut trouver un intérêt (gain de place) à procéder par "fourchettes" (de tous les multiples entre N et N + x ) où idéalement (mais pas forcément) x serait égal au carré du plus grand nombre premier déjà connu. Il faut quand même de la place ...;)
A noter, de surcroît, aucun multiple de tout nombre ne répondant pas au critère de primarité ne saurait être premier non plus ... et donc ? ..on peut réduire considérablement le nombre des nombres à tester ....(mais encore plus de place nécessaire alors)

Citation:

Envoyé par unparia

Alors voilà, mis en code, le mécanisme dont il s'agit

Code:

1
2
3
4
5
6
7
8
9
Dim nb As String, Diviseur As Long
  nb = String(60000, "8") ' -->> est une longue chaîne de "8" (60000 "8")
  Diviseur = 1547302
  deb = Timer
  While Len(nb) > 9
    nb = CStr(Val(Left(nb, 9) Mod Diviseur)) & Mid(nb, 10)
  Wend
  nb = CStr(Val(nb Mod Diviseur))
  MsgBox Timer - deb & "seconds --->>" & vbCrLf & nb

Tu n'as pas besoin de prendre la peine de me répondre.
Ou tu peux t'en inspirer et tant mieux, ou tel n'est pas le cas et tant pis.
cela ne regarde que toi.
Amitiés.

Bonjour Unparia.
J'ai fait des tests pour comparer ta méthode et la mienne pour calculer le modulo d'un grand nombre (plusieurs milliers de caractères) lorsque le diviseur est très petit (8 caractères au plus).
J'en conclu (voir ci-dessous) que ta méthode est plus rapide pour les diviseurs de moins de 7 caractères.
Je vais donc la conserver et l'intégrer dans mes fonctions pour l'utiliser quand c'est rentable.
Merci pour ce code.

Code:

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
Avec un nombre de 100 000 caractères :

Nb caractères diviseur: 1:
Durée avec ModGN :              0,68
Durée avec la formule unparia : 0,14
-----------------------------------------------
Nb caractères diviseur: 2:
Durée avec ModGN :              0,70
Durée avec la formule unparia : 0,14
-----------------------------------------------
Nb caractères diviseur: 3:
Durée avec ModGN :              0,70
Durée avec la formule unparia : 0,17
-----------------------------------------------
Nb caractères diviseur: 4:
Durée avec ModGN :              0,70
Durée avec la formule unparia : 0,22
-----------------------------------------------
Nb caractères diviseur: 5:
Durée avec ModGN :              0,72
Durée avec la formule unparia : 0,25
-----------------------------------------------
Nb caractères diviseur: 6:
Durée avec ModGN :              0,71
Durée avec la formule unparia : 0,36
-----------------------------------------------
Nb caractères diviseur: 7:
Durée avec ModGN :              0,77
Durée avec la formule unparia : 0,50
-----------------------------------------------
Nb caractères diviseur: 8:
Durée avec ModGN :              0,73
Durée avec la formule unparia : 0,92
-----------------------------------------------

Avec un nombre de 200 000 caractères :

Nb caractères diviseur: 1:
Durée avec ModGN :              2,63
Durée avec la formule unparia : 0,59
-----------------------------------------------
Nb caractères diviseur: 2:
Durée avec ModGN :              2,70
Durée avec la formule unparia : 0,59
-----------------------------------------------
Nb caractères diviseur: 3:
Durée avec ModGN :              2,73
Durée avec la formule unparia : 0,78
-----------------------------------------------
Nb caractères diviseur: 4:
Durée avec ModGN :              2,67
Durée avec la formule unparia : 0,89
-----------------------------------------------
Nb caractères diviseur: 5:
Durée avec ModGN :              2,81
Durée avec la formule unparia : 1,15
-----------------------------------------------
Nb caractères diviseur: 6:
Durée avec ModGN :              2,73
Durée avec la formule unparia : 1,39
-----------------------------------------------
Nb caractères diviseur: 7:
Durée avec ModGN :              2,76
Durée avec la formule unparia : 2,32
-----------------------------------------------
Nb caractères diviseur: 8:
Durée avec ModGN :              2,78
Durée avec la formule unparia : 3,93
-----------------------------------------------

Avec un nombre de 300 000 caractères :

Nb caractères diviseur: 1:
Durée avec ModGN :              12,32
Durée avec la formule unparia : 5,18
-----------------------------------------------
Nb caractères diviseur: 2:
Durée avec ModGN :              12,34
Durée avec la formule unparia : 5,77
-----------------------------------------------
Nb caractères diviseur: 3:
Durée avec ModGN :              12,40
Durée avec la formule unparia : 6,77
-----------------------------------------------
Nb caractères diviseur: 4:
Durée avec ModGN :              12,40
Durée avec la formule unparia : 8,36
-----------------------------------------------
Nb caractères diviseur: 5:
Durée avec ModGN :              12,65
Durée avec la formule unparia : 10,00
-----------------------------------------------
Nb caractères diviseur: 6:
Durée avec ModGN :              12,57
Durée avec la formule unparia : 14,09
-----------------------------------------------
Nb caractères diviseur: 7:
Durée avec ModGN :              12,81
Durée avec la formule unparia : 19,03
-----------------------------------------------
Nb caractères diviseur: 8:
Durée avec ModGN :              12,54
Durée avec la formule unparia : 35,43
-----------------------------------------------


Avec un nombre de 500 000 caractères :

Nb caractères diviseur: 1:
Durée avec ModGN :              71,45
Durée avec la formule unparia : 22,82
-----------------------------------------------
Nb caractères diviseur: 2:
Durée avec ModGN :              71,28
Durée avec la formule unparia : 24,69
-----------------------------------------------
Nb caractères diviseur: 3:
Durée avec ModGN :              69,91
Durée avec la formule unparia : 29,00
-----------------------------------------------
Nb caractères diviseur: 4:
Durée avec ModGN :              71,77
Durée avec la formule unparia : 33,98
-----------------------------------------------
Nb caractères diviseur: 5:
Durée avec ModGN :              71,68
Durée avec la formule unparia : 42,76
-----------------------------------------------
Nb caractères diviseur: 6:
Durée avec ModGN :              71,23
Durée avec la formule unparia : 56,80
-----------------------------------------------
Nb caractères diviseur: 7:
Durée avec ModGN :              72,34
Durée avec la formule unparia : 84,21
-----------------------------------------------
Nb caractères diviseur: 8:
Durée avec ModGN :              73,43
Durée avec la formule unparia : 145,31
-----------------------------------------------

Voir 40 message(s) de cette discussion en une page