Complexité d'un algorithme
dans Arithmétique
Bonjour
J'aimerais avoir un exemple concret concernant le temps réel d'exécution d'un algorithme d'exponentiation modulaire.
Par exemple pour un ordinateur avec microprocesseur de 2GHz, Combien de temps ça lui prendra pour calculer $5^e=c[m]$ avec $m$ et $e$ des nombres à 100 millions de chiffres en base 10.
Je sais que le temps d'exécution est de $O\big(\log(e)\big)$ mais c'est un exemple concret que je cherche pour le test de Miller-Rabin et autres.
Merci à vous.
J'aimerais avoir un exemple concret concernant le temps réel d'exécution d'un algorithme d'exponentiation modulaire.
Par exemple pour un ordinateur avec microprocesseur de 2GHz, Combien de temps ça lui prendra pour calculer $5^e=c[m]$ avec $m$ et $e$ des nombres à 100 millions de chiffres en base 10.
Je sais que le temps d'exécution est de $O\big(\log(e)\big)$ mais c'est un exemple concret que je cherche pour le test de Miller-Rabin et autres.
Merci à vous.
Réponses
-
Pas de réponse ??:-(
La question qui me tracasse c'est pourquoi dans les forums ils disent que ça prend un temps fou pour un seul test de Rabin-Miller pour $e$ de l'ordre de $10^t$ avec $t=10^8$ alors qu'un processeur de 2GHZ est censé faire 2 milliards d'opérations en une seule seconde. -
Bonjour.
De quel type sont les opérations dont vous parlez ?
Des nombres de 100000000 de chiffres en base 10, ça ne se manipule pas comme un flottant quelconque. En tous cas pas de manière triviale.
A bientôt.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Bonjour,
Et si on connait déjà l'écriture du nombre en base binaire, ça change quelque chose ? -
Bonjour
"2 milliards d'opérations en une seule seconde."
Alors, il faut s'entendre. C'est 2 milliards de cycles d'horloge. Mais les "opérations" nécessitent souvent plus qu'un cycle d'horloge, même s'il est vrai qu'une addition ne prend qu'un cycle d'horloge.
Ensuite, on peut faire 2 milliards d'additions en 1 seconde sur 64 bits ! (Pour un système 64 bits). Pas sur 100 millions de chiffres en base 10. :-)
Enfin, c'est une grande fraude. Même si ton processeur peut marcher à ces fréquences d'horloge là, il ne le fait pas la plupart du temps, car ton pc surconsomme de l'énergie. Donc pour éviter cela, ton processeur sera à 500MHz la plupart du temps. Désolé.Ce site est fatigant. Les gens modifient sans cesse leurs messages passés, et on ne comprend plus rien à la discussion. Je suis nostalgique du temps où, si on postait une bêtise, on devait l'assumer. Et si on cite le passage pour l'ancrer, l'administrateur supprime en disant qu'on n'a pas besoin de recopier le message passé. -
Merci beaucoup pour tes explications.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 29
+16 Invités