us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 2016
-
7 avril 2006 à 23:25
yacouyahaya
Messages postés3Date d'inscriptionmercredi 19 mars 2008StatutMembreDernière intervention 6 juin 2010
-
24 juil. 2009 à 00:20
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
yacouyahaya
Messages postés3Date d'inscriptionmercredi 19 mars 2008StatutMembreDernière intervention 6 juin 2010 24 juil. 2009 à 00:20
salut les mecs, je suis un débutant mais pas un debutant en tant que tel car jais des serieux problemes en algorithme essayer de m'aider afin que je puisse un jour poster ne ce reste qu'un petit code pour qu'en fin je me sente programmeur je vous pris de m'aider les amis merci
jean_marc_n2
Messages postés170Date d'inscriptionjeudi 11 décembre 2003StatutMembreDernière intervention24 janvier 2009 10 avril 2006 à 22:18
oui c'est exact le elseif k=3 est inutile.
En fait c'est tout simple, on fait 2, 3, 5, puis on ajoute alternativement 2, 4, 2, 4, etc. Ca ne génère pas trop de nombres non premiers. On peut améliorer en éliminant les multiples de 7 assez facilement, puis les nombres de la forme 30m+5. Bien sur, dans une implémentation un peu plus sérieuse, on peut améliorer tout ça en pré-générant les d(k) pour les 1000 ou 10000 premiers nombres premiers, ce qui permet de faire un lookup plus rapide que le calcul, et avant de trouver un nombre premier dont le premier facteur est plus grand que le 10.000 nombre premier, il faut déjà un très grand nombre :-)
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 10 avril 2006 à 21:40
Hum... Intéressant la petite formule de Jean_Marc_N2 : "d = 5 + ((k - 2) \ 2) * 2 + ((k - 3) \ 2) * 4" qui remplace la forme 6n-1 et 6n+1 . Je ne connaissais pas...
Juste une petite remarque en passant, dans la function d() les deux lignes :
ElseIf k = 3 Then
d = 5
sont inutiles, puisque la formule donne le bon résultat pour le cas où k=3, mais bon...
Amicalement,
Us.
chewbaka62
Messages postés67Date d'inscriptionmardi 1 novembre 2005StatutMembreDernière intervention30 juillet 2006 10 avril 2006 à 16:42
Pas de problème, Jean-Marc. Je suis tout à fait d'accord ( et c'est normal) de faire l'objet de critiques surtout quand elles viennent de connaisseurs. Je suis là pour apprendre après tout. Il y a juste la manière de le dire. Pour changer de sujet, j'ai examiné ton code et c'est vrai que ça n'a rien à voir avec ce que j'ai fait et je t'en remercie vivement.
A bientôt et sans rancune.
Chewbaka
jean_marc_n2
Messages postés170Date d'inscriptionjeudi 11 décembre 2003StatutMembreDernière intervention24 janvier 2009 10 avril 2006 à 13:50
Hello,
je ne voulais pas être agressif, si je l'ai été je te prie de bien vouloir m'en excuser.
Je voulais simplement signaler qu'en règle générale, on ne résoud pas un problème de performances par un bricolage du langage, mais par l'utilisation d'algorithmes ou de structures de données plus efficaces.
L'algorithme que je propose peut être employé pour des nombres de toute taille, il suffit de regarder comment il fonctionne. Il est seulement limité par ce que le langage (ici VB) sait représenter en interne.
Bonne continuation :-)
chewbaka62
Messages postés67Date d'inscriptionmardi 1 novembre 2005StatutMembreDernière intervention30 juillet 2006 10 avril 2006 à 10:40
Le problème n'est pas de connaître les math. car je pense me débrouiller pas trop mal mais de traduire dans une langue que je ne maitrise pas. C'est tout ce que j'aurai à ajouter. On ne va pas polémiquer indéfiniment. :)
cs_gogomanu
Messages postés29Date d'inscriptionmardi 7 janvier 2003StatutMembreDernière intervention26 mars 2009 10 avril 2006 à 09:38
Sans vouloir en rajouter une couche je ne vois pas trop ce que le fait de débuter en VB a à voir avec l'algorithme utilisé.
Le programme d'exemple de Jean_Marc_N2 ne demande pas une maitrise du VB (addition, multiplication, division, modulo ah oui et un do while, compliqué le do while), simplement il faut s'y connaître en maths !!!
chewbaka62: si tu connais autant de théorèmes (qui me sont totalement inconnus), pourquoi implémenter la version la plus lente qui soit au lieu de (je cite) la version eliptique, de fermat, mersenne ?
et surtout pourquoi demander "comment gagner en rapidité"...
Pas très logique tout ça.
Franchement si j'étudiais toutes sortes de tri de tableau (tri indexé, tri par liste chaînées, tri radix..) il ne me viendrait pas à l'esprit de coder un tri bulle.
chewbaka62
Messages postés67Date d'inscriptionmardi 1 novembre 2005StatutMembreDernière intervention30 juillet 2006 9 avril 2006 à 22:50
Merci à Jean-Marc pour son commentaire aussi instructif ... qu'incisif. Je voudrais juste dire une chose: mon algorithme est probablement "ringard" mais néanmoins acceptable pour un débutant en VB .Net De plus, quand tu dis que ton algorithme peut être utilisé avec des nombres aussi grands que l'on veut, j'ai des doutes car au delà des 15 chiffres, ça pose problème ( il n'affiche que des zéros ). De plus j'ai bien lu sur le sujet des nombres premiers ( courbes elliptiques, théorème de Fermat, Mersenne, algorithme AKS, etc... je connais. ) Alors, un peu d'indulgence pour un débutant en "voie de développement".
Merci et à plus...
jean_marc_n2
Messages postés170Date d'inscriptionjeudi 11 décembre 2003StatutMembreDernière intervention24 janvier 2009 9 avril 2006 à 21:18
Hello,
pour la rapidité il faut surtout employer un algorithme correct (ce n'est pas le cas de celui-ci).
Celui que je donne ici en exemple (pourtant trivial) retourne la décomposition en qq millisecondes, pour des nombres jusqu'à 2,147,483,647 (c'est la limite d'un long en VB) mais ce serait pareil même pour des nombres beaucoup plus grands.
Il est des milliers de fois plus rapide que le tien, et surtout n'est pas limité en taille (les nombres peuvent être aussi grands que l'on veut). Lire un peu sur le sujet peut être utile avant de proposer une implémentation d'un algorithme mathématique, et dans le cas présent (décomposition en facteurs premiers), le problème est à l'étude depuis l'an -250... La littérature sur le sujet est, comment dire ... abondante :-)
Voici une implémentation non optimisée de la méthode "Factorisation par division". On est loin des performances qu'on peut obtenir avec les courbes elliptiques par exemple, mais on peut déjà factoriser des nombres ayant une petite dizaine de chiffres, sans problème.
'
' retourne dans s la decomposition en fateurs premiers
'
Private Function factor(nbre As Long, s As String) As Boolean
Dim n As Long, k As Long, dk As Long
Dim t As Long, q As Long, r As Long
n nbre: t 0: k = 0
Do While n <> 1
dk = d(k + 1)
q = n \ dk
r = n Mod dk
If r = 0 Then
' ici on pourrait grouper les dk si identiques
s = s & dk & " "
n = q
Else
If q > dk Then
k = k + 1
Else
s = s & n & " "
Exit Do
End If
End If
Loop
End Function
Public Function d(ByVal k As Long) As Long
If k = 1 Then
d = 2
ElseIf k = 2 Then
d = 3
ElseIf k = 3 Then
d = 5
Else
d = 5 + ((k - 2) \ 2) * 2 + ((k - 3) \ 2) * 4
End If
End Function
chewbaka62
Messages postés67Date d'inscriptionmardi 1 novembre 2005StatutMembreDernière intervention30 juillet 2006 9 avril 2006 à 14:20
Merci Redman,
Je m'en vais essayer cela dès que j'aurai un peu de temps.
Merci également à US pour son site, véritable mine à sources.
Chewbaka
OneHacker
Messages postés1447Date d'inscriptionjeudi 2 novembre 2000StatutMembreDernière intervention23 septembre 20072 9 avril 2006 à 11:01
Pour la rapidité, il faut peut-être plus de mémoire RAM mais avant tout essaye en éxécutant le code dans une procédure au nom de Sub Factorize() et fait :
Private Sub mnuFichierFactor_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuFichierFactor.Click
Dim tFactorize as new threading.thread
tFactorize.Start()
End Sub
Voilà ! Je pense que cela ira plus vite.
Redman
us_30
Messages postés2065Date d'inscriptionlundi 11 avril 2005StatutMembreDernière intervention14 mars 201610 7 avril 2006 à 23:25
Salut,
Pour gagner en rapidité, il suffit de programmer le crible d'erasthostène... puis d'utiliser un test avec les nb premiers... seul inconviénient, la mémoire... mais il y a de la marge avec le matériel de nos jours...
Sans vouloir en profiter ici, je pense que dans mon modeste site tu trouveras quelques pistes ou source d'inspiration... dont d'ailleurs certaines ont été exposées sur ce site à la critique...
24 juil. 2009 à 00:20
10 avril 2006 à 22:18
En fait c'est tout simple, on fait 2, 3, 5, puis on ajoute alternativement 2, 4, 2, 4, etc. Ca ne génère pas trop de nombres non premiers. On peut améliorer en éliminant les multiples de 7 assez facilement, puis les nombres de la forme 30m+5. Bien sur, dans une implémentation un peu plus sérieuse, on peut améliorer tout ça en pré-générant les d(k) pour les 1000 ou 10000 premiers nombres premiers, ce qui permet de faire un lookup plus rapide que le calcul, et avant de trouver un nombre premier dont le premier facteur est plus grand que le 10.000 nombre premier, il faut déjà un très grand nombre :-)
10 avril 2006 à 21:40
Juste une petite remarque en passant, dans la function d() les deux lignes :
ElseIf k = 3 Then
d = 5
sont inutiles, puisque la formule donne le bon résultat pour le cas où k=3, mais bon...
Amicalement,
Us.
10 avril 2006 à 16:42
A bientôt et sans rancune.
Chewbaka
10 avril 2006 à 13:50
je ne voulais pas être agressif, si je l'ai été je te prie de bien vouloir m'en excuser.
Je voulais simplement signaler qu'en règle générale, on ne résoud pas un problème de performances par un bricolage du langage, mais par l'utilisation d'algorithmes ou de structures de données plus efficaces.
L'algorithme que je propose peut être employé pour des nombres de toute taille, il suffit de regarder comment il fonctionne. Il est seulement limité par ce que le langage (ici VB) sait représenter en interne.
Bonne continuation :-)
10 avril 2006 à 10:40
10 avril 2006 à 09:38
Le programme d'exemple de Jean_Marc_N2 ne demande pas une maitrise du VB (addition, multiplication, division, modulo ah oui et un do while, compliqué le do while), simplement il faut s'y connaître en maths !!!
chewbaka62: si tu connais autant de théorèmes (qui me sont totalement inconnus), pourquoi implémenter la version la plus lente qui soit au lieu de (je cite) la version eliptique, de fermat, mersenne ?
et surtout pourquoi demander "comment gagner en rapidité"...
Pas très logique tout ça.
Franchement si j'étudiais toutes sortes de tri de tableau (tri indexé, tri par liste chaînées, tri radix..) il ne me viendrait pas à l'esprit de coder un tri bulle.
9 avril 2006 à 22:50
Merci et à plus...
9 avril 2006 à 21:18
pour la rapidité il faut surtout employer un algorithme correct (ce n'est pas le cas de celui-ci).
Celui que je donne ici en exemple (pourtant trivial) retourne la décomposition en qq millisecondes, pour des nombres jusqu'à 2,147,483,647 (c'est la limite d'un long en VB) mais ce serait pareil même pour des nombres beaucoup plus grands.
Il est des milliers de fois plus rapide que le tien, et surtout n'est pas limité en taille (les nombres peuvent être aussi grands que l'on veut). Lire un peu sur le sujet peut être utile avant de proposer une implémentation d'un algorithme mathématique, et dans le cas présent (décomposition en facteurs premiers), le problème est à l'étude depuis l'an -250... La littérature sur le sujet est, comment dire ... abondante :-)
Voici une implémentation non optimisée de la méthode "Factorisation par division". On est loin des performances qu'on peut obtenir avec les courbes elliptiques par exemple, mais on peut déjà factoriser des nombres ayant une petite dizaine de chiffres, sans problème.
'
' retourne dans s la decomposition en fateurs premiers
'
Private Function factor(nbre As Long, s As String) As Boolean
Dim n As Long, k As Long, dk As Long
Dim t As Long, q As Long, r As Long
n nbre: t 0: k = 0
Do While n <> 1
dk = d(k + 1)
q = n \ dk
r = n Mod dk
If r = 0 Then
' ici on pourrait grouper les dk si identiques
s = s & dk & " "
n = q
Else
If q > dk Then
k = k + 1
Else
s = s & n & " "
Exit Do
End If
End If
Loop
End Function
Public Function d(ByVal k As Long) As Long
If k = 1 Then
d = 2
ElseIf k = 2 Then
d = 3
ElseIf k = 3 Then
d = 5
Else
d = 5 + ((k - 2) \ 2) * 2 + ((k - 3) \ 2) * 4
End If
End Function
9 avril 2006 à 14:20
Je m'en vais essayer cela dès que j'aurai un peu de temps.
Merci également à US pour son site, véritable mine à sources.
Chewbaka
9 avril 2006 à 11:01
Private Sub mnuFichierFactor_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuFichierFactor.Click
Dim tFactorize as new threading.thread
tFactorize.Start()
End Sub
Voilà ! Je pense que cela ira plus vite.
Redman
7 avril 2006 à 23:25
Pour gagner en rapidité, il suffit de programmer le crible d'erasthostène... puis d'utiliser un test avec les nb premiers... seul inconviénient, la mémoire... mais il y a de la marge avec le matériel de nos jours...
Sans vouloir en profiter ici, je pense que dans mon modeste site tu trouveras quelques pistes ou source d'inspiration... dont d'ailleurs certaines ont été exposées sur ce site à la critique...
Amicalement,
Us.