Discussion :

[Jo'CaML]

Voilà, dans le cadre d'un maudit TIPE de classe de spé ( tipe = travaux perso encadrés ), j'aimerais avoir une réponse à une question que je me pose depuis trois siècles....

A quoi ça sert les algo de multiplication rapide d'entiers/polynômes ?

Quand est on ammené concrètement à manipuler des objets aussi grands ??!

[v4np13]

La rapidité et l'efficacité (on se trompe moins facilement)

[progfou]

On peut être amené à les manipuler pour les calculs sur les algo de cryptage (nombres premiers de plusieurs centaines de chiffres) par exemple.

[gangsoleil]

Bonjour,

Il est bien évident que sur les calculs simples, que ta multiplication soit bète et méchante ou performante, tu n'en as rien à faire.

En revanche, dès que tu commences à avoir pas mal de chiffres, tu t'apercois que les calculs deveinnenent de plsu en plus longs.
Ainsi, la multiplication de l'algorithme de Karatsuba, lorsque je l'ai implémentée, devenait intéressante à partir de 40 ou 50 chiffres (pour chacun des nombres à multiplier).
Pour multiplier deux nombres de plus de 600 chiffres, nous avons laissés tourner le programme plusieurs heures.
Ce qui est toujours mieux que de le laisser tourner plusieurs jours.

Maintenant, si tu cherches l'application de gros calculs très longs, tu peux prendre la météo : ils collectent des données en permanence, pour alimenter un super-calculateur qui doit donner un résultat en un temps fini et prévu à l'avance. Dans ce cas précis, il est nécessaire de pouvoir interrompre le calcul parce que c'est l'heure, et avoir un résultat partiel.

[Jo'CaML]

Ah, je me disais bien aussi que ça servait à quelque chose

Merci beaucoup pour vos réponses, ça me fait plaisir de pas m'être acharné pour rien sur ce maudit algo FFT de Schonhage et Strassen !!

Dernier truc... pour la crypto c'est impeccable, par contre, à propos de la météo, est ce que quelqu'un saurait le genre de calculs que l'on a a mener exactement pour faire des prévisions, ou même dans les modèles d'évolution du climat ?

[pascal_damien]

Salut,


Je ne sais pas si c'est le modèle utilisé maintenant, mais j'avais lu quelque chose qui indiquait que la météo utilisait la méthode des éléments finis (ici en divisant l'atmosphère) avec les mesures permettant de donner les conditions initiales. Comme c'est très pointu, je pense que tu auras plus de chance avec une recherche sur l'Internet.

[Jo'CaML]

Ouais, j'ai regardé un peu, apparement il s'agit essentiellement de résoudre des équadiffs monstreuses par des procédés numériques, en cherchants des solutions sur des domaines de plus en plus fractionnés... ça a l'air très très très compliqué en tous cas.

Par contre je n'ai pas vu la moindre trace d'une multiplication rapide de grands entiers

Si quelqu'un connaît d'autres domaines d'application concrète de la multiplication rapide, son savoir est toujours le bienvenu !!

[alveric]

Ouais, j'ai regardé un peu, apparement il s'agit essentiellement de résoudre des équadiffs monstreuses par des procédés numériques, en cherchants des solutions sur des domaines de plus en plus fractionnés... ça a l'air très très très compliqué en tous cas.

Par contre je n'ai pas vu la moindre trace d'une multiplication rapide de grands entiers

En effet, la resolution d'equadiff pour des elements finis, c'est plutot des cacluls matriciels... Et des tres bourrins des qu'on veut avoir quelque chose d'utilisable.

[gangsoleil]

Certes,

En fait, je croyais que le but était de comprendre l'utilité d'une multiplication rapide, pas spécifiquement sur les grands entiers.
Or lorsque l'on a de grandes matrices à mutliplier, le nombre de calculs est tout de suite gigantesque. Donc même si on ne gagne qu'une fraction de seconde par opération c'est intéressant.

[ceugniet]

Certes,

En fait, je croyais que le but était de comprendre l'utilité d'une multiplication rapide, pas spécifiquement sur les grands entiers.
Or lorsque l'on a de grandes matrices à mutliplier, le nombre de calculs est tout de suite gigantesque. Donc même si on ne gagne qu'une fraction de seconde par opération c'est intéressant.

Les algorithmes de multiplication rapide en grands nombres ne sont rapides "qu'au voisinage de l'infini" comme on dit si joliment. Je pense qu'effectivement ils sont probablement intéressants pour le cryptage avec de grands nombres. La raison est simple : dès que le nombre de bits significatifs dépasse 53, le hardware de la machine ne peut plus faire le calcul en une instruction machine, il faut alors recourir à un algorithme spécifique qui passe bien sûr par un découpage des grands nombres en petits morceaux qui peuvent être traités individuellement par les unités de calcul de la machine. Mais si tes nombres ne dépassent pas les 53 bits (ou le double si des unités spécifiques autorisent la quadruple précision) alors aucun "algorithme rapide" ne battra les performances standard du multiplieur hardware.
Dans le cas de la météorologie, je suis quasiment certain que l'on n'a pas besoin d'une précision dépassant le standard IEEE. La lourdeur des calculs météo tient au nombre de calculs à faire, pas à la taille des opérandes. Donc, pas d'algo spécifiques grands nombres en météo.

Donc même si on ne gagne qu'une fraction de seconde par opération c'est intéressant.

Non, il n'y a aucune nanoseconde à gagner sur chaque opération, le hardware sera meilleur dans tous les cas.

À part la cryptographie, on peut imaginer la recherche en arithmétique. C'est un chercheur en arithmétique faisant des calculs en entier et en multiple précision (donc sur de grands nombres) qui a découvert le bug de la première puce Pentium, en trouvant quelques résultats faux.

Il y a aussi les fanas du calcul des miliards de décimales de pi...