factorisation de nombres et temps de traitement

michael11 · 25-12-2010 09:05:36

Bonjour,
Je suis un amateur mais passionné. Ainsi j'ai réussi à trouver deux méthodes mathématiques pour factoriser des nombres divisibles. J'en ai tiré les algorithmes en C. Et je les ai comparés en vitesse à celui qui consiste calculer le reste des divisions successives d'un nombre qu'on incrémente de 2 à chaque pas de la boucle.
Je pense qu'elles sont nouvelles mais n'est pas trop sûr de leurs intérêts. En effet la première est deux fois et demi plus lente!
Mais la deuxième est presque deux fois plus rapide que l'algorithme de référence.
J'ai vu dans ce forum un programme en python qui indique des temps. Ce serait bien d'indiquer aussi le ratio par rapport à cet algorithme de référence. Ainsi on aurait un point de comparaison pour ces temps de traitement.
Merci de vos réponses.

yoshi · 25-12-2010 10:34:34

Bonjour,

Bienvenue sur BibM@th et joyeux Noël...

Ce serait bien d'indiquer aussi le ratio par rapport à cet algorithme de référence.

Je veux bien, mais
- Quel algorithme de référence ?
- Qu'est-ce que tu appelles ratio ? Et tu le calcules comment ?

Tu peux toujours publier tes sources dans ce forum ; ayant tâté (un peu) du C, je devrais être capable de les traduire en Python et ainsi d'étalonner les vitesses...

Tu peux aussi faire le contraire, prendre le code source de ma dernière version de calcul du nombre d'or par exemple (ou la décomposition via la méthode de rho-pollard ou autre), le traduire en C, et comparer les temps de calcul (que j'ai donnés hors affichage) pour :
- 5000 décimales : 0.25 s
- 10000 décimales : 0.94 s
- 15000 décimales : 2.05 s
- 20000 décimales : 2.36 s

http://www.bibmath.net/forums/viewtopic.php?id=3907&p=2 message #33

Pour ce code, je précise que
* C'est la technique de calcul d'une racine carrée "à la main", avec stylo et papier, qui est adaptée,
* Que je ne fais de calculs que sur des nombres entiers (leur taille, en Python, ne dépend que de la qté de RAM,
* Que je transforme le résultat de la division par 2 en string, puis que j'y place le point décimal en tant que caractère à part entière.

A la réflexion, je doute qu'il soit possible, sans artifice très gourmand en temps de calcul, de gérer en C des entiers de 5000, 10000, 15000 ou 20000 chiffres...
Donc, j'en reviens à ma première suggestion

@+

le reste des divisions successives d'un nombre qu'on incrémente de 2 à chaque pas de la boucle.

C'est ça que tu appelles "algorithme de référence" ?
Les divisions successives par quel(s) nombre(s) ?

Dernière modification par yoshi (25-12-2010 10:37:32)

michael11 · 26-12-2010 11:10:25

Bonjour,

Merci de ta réponse et joyeux Noël aussi!
Comme je ne sais pas coder en Python je choisis aussi ta première proposition.

Voici ce que j'appelle l'algorithme de référence.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
double duration;
clock_t start, end;
__int64 entier;
__int64 diviseur;
__int64 racine;
__int64 reste;

start = clock();

for(entier=1001;entier<10000001;entier+=2)
// La première boucle sert à "faire du volume" pour obtenir des temps
{

racine = sqrt(entier) + 2;
diviseur = 3;
while (diviseur < racine)
// La deuxième boucle est le réel programme de factorisation
{
reste = entier % diviseur;
if (reste == 0)
{
//printf("le nombre %I64u est divisble par %I64u\n", entier, diviseur);
break;
}
diviseur += 2;
}
}
end = clock();
duration = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("%f sec\n", duration);
return 0;
}

Bien évidemment ,étant amateur aussi en C, ce code est aussi perfectible quant à son écriture. Mais l'algorithme en lui même est celui qui est utilisé dans la plus simple expression de factorisation de nombre.
Attention : il ne sert qu'à trouver le plus petit diviseur d'un nombre.

Sur mon vieux coucou (un pentium3) pour 1001<entier<10000001 j'obtiens 92,773 secondes.

yoshi · 26-12-2010 16:54:48

Salut,

1. Qu'est-ce que c'est que ça : CLOCKS_PER_SEC je le prends où ? C'est spécifique à C ?
2. Tout ce que je sais, c'est que ma fonction time me donne un temps en s depuis "epoch".
3. C est réputé plus rapide de 25 à 30% par rapport à python..

Je recommence mes tests : les résultats sont hallucinants, compte tenu de ce que j'ai écrit ci-dessus, d'autant que mon processeur est un AMD X3 triple cœur, je devrais plus être bien plus rapide or je suis je ne sais combien de fois plus lent :
92 s pour traiter tous les cas (de 2 en 2) entre 1001 et 100000001 (dix millions un) ? Diantre..
Mon temps Python : 247 s...
Il y a un réel problème dont je ne sais où il se cache : ton prog C sur ma machine, via dev-C++ : 25.7 s
Mon prog python :

from math import sqrt

from time import time

tp_d=time()

for i in xrange(1001,10000001,2):

    racine =int(sqrt(i))+2

    for diviseur in xrange(3,racine,2):

        reste=i%diviseur

        if reste==0:

            #print "Le nombre",i,"est divisible par",diviseur

            break

print

tp_f=time()

print 'Temps écoulé :',int(100*(tp_f-tp_d))/100.0,' s'

@+

michael11 · 26-12-2010 21:19:29

Bonjour,

Merci d'avoir pris la peine d'essayer mon code!
1) CLOCKS_PER_SEC est une variable propre à la fonction clock_t décrite dans la librairie time.h : cf le lien
http://msdn.microsoft.com/fr-fr/library … 80%29.aspx
4) Je code en C et ne connais pas python.

Par contre je suis toujours à la recherche de savoir si un facteur d'accélération de 2 par rapport à ce programme que j'appelle de référence (celui sur lequel on a échangé) peut intéresser quelqu'un. En effet je n'ai pas de culture en ce domaine et hormis quelques articles de vulgarisation je n'ai aucune idée de l'état actuel des améliorations vis-à-vis de ce programme.

@+

yoshi · 26-12-2010 21:37:57

Re,

Facteur d'accélération x2 ?
Tu codes ça comment ?
Si tu veux bien le faire savoir, si ton code est très complexe, je risque d'avoir du mal à suivre, alors peut-être serait-il judicieux de l'écrire en pseudo-code, i.e. en langage de tous les jours.
Je vais voir si je peux adapter en C mon calcul du nombre d'or, mais je serais surpris de réussir : je ne crois pas qu'on puisse manipuler en C des entiers de plusieurs milliers de chiffres...

J'ai repensé à ce différentiel de vitesse : python est interprété, C est compilé, c'est déjà une grosse différence...

Je vais aussi essayer d'optimiser mon code...

@+

michael11 · 27-12-2010 08:15:14

Bonjour,

Merci de tes réponses mais je crois que j'exprime mal mon problème.
Prenons l'article de Wikipedia par exemple :http://fr.wikipedia.org/wiki/Crible_quadratique#cite_note-0
Il parle du crible quadratique qui est plus performant (donc plus rapide) que le crible généralisé.
Puis il donne une vielle formule des familles extrêmement intéressante mais que je ne comprends pas et que je ne veux même pas essayer de comprendre tellement je suis sûr de perdre mon temps!

L[tex]O\left(e^\sqrt{\log n \log\log n}\right)=L_n\left[1/2,1\right][/tex]

avec la notation O de Landau et la notation L (en)."

Damned : le copier/coller de la fonction (du Latex peut-être?) ne fonctionne pas!

Bref des exemples concrêts m'auraient fait un bien fou, du style pour n=123456789 le crible quadratique prend
7 secondes tandis que le crible quadratique n'en prend qu'une.

Sur cette base j'aurais pu calculer le facteur d'accélération qui ici aurait été de 7.
Or le second algorithme dont je parle dans mon premier post n'a un facteur d'accélération que de 2. Et tu as raison d'en parler, de 2 que pour les petits nombres (inférieurs à 64 bits). Mais, et là j'en suis certain, qui est de plus en plus performant au fur et à mesure que la taille des chiffres grandit (mais là il faut que je le prouve via l'informatique).

Je me suis mis au C pour vérifier mon algorithme (qui a la base est une relation mathématique). Si tu me dis :
1) qu'un facteur 2 est ridicule : alors je stoppe tout.
2) que ce facteur 2 est exploitable seulement s'il augmente avec la taille des chiffres : alors s'il le faut je me mette au Python qui comme j'ai cru le comprendre dans tes explications permet de travailler sur des chiffres de plusieurs milliers de chiffres. J'exposerais alors le résultat dans un blog.

Voilà je pense clairement exposé mon dilemme.

yoshi · 27-12-2010 11:26:19

Re,

Oui c'était bien du LaTeX : la preuve ! J'ai juste ajouté deux balises tex et /tex entre crochets...

Un facteur 2 ridicule ? Qui serais-je pour dire des choses pareilles ?
Non, pas ridicule, une gageure oui...
Des générations de mathématiciens se sont colletés avec la problématique, sans résultats autres que ceux que tu connais...
Maintenant, les amateurs éclairés, ça existe : le propre d'une idée géniale est d'apporter un éclairage nouveau et inédit, donc pas envisagé jusqu'alors.
On a tous des blocages, des idées préconçues : je le vérifie chaque semaine...
Si tu réussis, à toi la médaille Fields (et le prix qui va avec)...

Oui, pour travailler avec des grands nombres entiers, tu as intérêt à travailler en Python, mais reste avec une version 2.6.5, tu pourras y adjoindre un accélérateur (écrit en C), psyco, et permettant de gagner jusqu'à 30 % de vitesse d'exécution.
D'autre part, il te sera plus facile de traduire ton algo en Python qu'en C...

Maintenant, oui, ton truc présentera un intérêt pour les grands nombres, : diviser le temps par 2 pour passer de 25 s à 12 s, bof...
Pour descendre de 48 à 24 h, oui...
C'est la même problématique que chercher à accélérer son PC à tout prix : si c'est pour passer d'un temps d'ouverture de son traitement de textes favori de 2 s à 1,5 s le jeu en vaut-il la chandelle ?

A titre indicatif, mon calcul du nombre d'or avec 20000 décimales est à la base, une manipulation de nombre entiers de plus en plus en grands : 4 chiffres, 6 chiffres... 1000... 5000... 10000....20000...
Je ne suis pas allé au delà...
Je transforme le nombre entier final en string, je remplace le 2 de tête par un 3, reconvertit, divise le nombre entier final de 20000 chiffres par 2, je le transforme en string et j'intercale un point décimal...

Courage !
Je suis à ton écoute pour tout développement complémentaire...

@+

Je viens de relire mon programme et mes commentaires dans cette discussion : je me suis dit que je n'étais pas logique avec moi-même : j'ai fait une modif dans ma dernière version et j'ai gagné 10 % au bas mot.
30000 décimales en moins de 8 s...

Golgup · 27-12-2010 12:22:22

Hi!

Je suis d'avis que Michael dévoile l'aspect mathématique de son invention!

@+

michael11 · 27-12-2010 19:28:09

Bonjour Yoshi,

Tu m'as convaincu : je me mets à Python.
Je te tiendrais au courant mais comme je suis naturellement lent et ne dispose pas de beaucoup de temps, je te donne rendez-vous dans 1 mois au mieux.

A plus tard et merci de ton soutient.

Forum de mathématiques - Bibm@th.net

#1 25-12-2010 09:05:36

factorisation de nombres et temps de traitement

#2 25-12-2010 10:34:34

Re : factorisation de nombres et temps de traitement

#3 26-12-2010 11:10:25

Re : factorisation de nombres et temps de traitement

#4 26-12-2010 16:54:48

Re : factorisation de nombres et temps de traitement

#5 26-12-2010 21:19:29

Re : factorisation de nombres et temps de traitement

#6 26-12-2010 21:37:57

Re : factorisation de nombres et temps de traitement

#7 27-12-2010 08:15:14

Re : factorisation de nombres et temps de traitement

#8 27-12-2010 11:26:19

Re : factorisation de nombres et temps de traitement

#9 27-12-2010 12:22:22

Re : factorisation de nombres et temps de traitement

#10 27-12-2010 19:28:09

Re : factorisation de nombres et temps de traitement

Réponse rapide

Pied de page des forums