La multiplication ultra-rapide

Salut,

Décrire une multiplication sur les entiers quasi aussi rapide que l'addition (en utilisant les processeurs actuels).

Cordialement.



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par pourexemple.

nyaka écrire les nombres sous forme d'exponentielle de base $12$.
Après $\forall x,y\,12^x\times12^y=12^{x+y}$.

Inutile de me demander pourquoi $12$ ni de me féliciter pour cette méthode géniale.

S

La poésie n'est pas une solution.

merci samok mais wiki en dira plus long (wikipédia)

de rien max8128, mais peux-tu m'indiquer où est référencée la méthode jointée à ce post ?

S

La poésie n'est pas une solution.

@Samok : ce n'est pas tout à fait cela, je parle des grands entiers (bien sûr).

C'est un vieille algo., qui autrefois était inutilisable et qui maintenant l'est, si vous trouvez l'algo., je vous dis pourquoi maintenant il est utilisable.

Cordialement.



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par pourexemple.

ah oui, je vois que tu ne voiles pas les choses,

bonne continuation,

S

La poésie n'est pas une solution.

La multiplication par 2 est, sur tous les ordinateurs actuels, bien plus rapide que n'importe quelle addition.

Je parlais de grands entiers.

Salut,

Je donne la multiplication :

Soit $(p_i)_{i=1...n}$ une suite finie d'entiers premiers entre eux, avec les $p_i<2^{32}$.

On note $M=\prod p_i$.

Alors si $a<\sqrt M$, $b<\sqrt M$, $a_i=a \mod p_i$ et $b_i=a \mod p_i$.

La multiplication rapide consiste en $(a\times b)_i= a_i \times b_i \mod p_i$.

Là je n'ai rien spoiler, en effet cela était connue, mais où est le problème pourquoi cela n'est pas utilisable...

Cordialement.

Bien, maintenant que tu as un peu exposé ton idée, il reste à en évaluer la complexité et à la comparer avec d'autres algorithmes déjà connus.
J'ai dans l'idée que ce n'est probablement pas meilleur que celui de Schönhage-Strassen ou celui de Fürer.
En fait, je crains même que pour de grands entiers, ce ne soit pas meilleur que la multiplication naïve.

À toi de nous prouver le contraire.

Déjà, ne parlons pas de complexité asymptotique, mais mesurer.

Fait un test, et dis nous ce que tu obtiens... je rappelle que cette algo. est hautement parallélisable.

PS : j'ai le souvenir d'un article dans pour la Science, ou un informaticien ( Jean-Paul Delahaye professeur à Lille) expliquais qu'il était le plus rapide, mais pas exploitable



Edité 2 fois. La dernière correction date de il y a quatre années et a été effectuée par pourexemple.

Sinon pour la complexité j'ai au plus $E(4n/20)+1$ opérations élémentaires (en comptant la multiplication entre 2 entier de moins de 32 bits comme une opération élémentaires, ainsi que le modulo ), pour une multiplication de 2 entiers de tailles n (en bits).

$E$ la partie entière.

PS1 : donc l'algo. est linéaire.

PS2 : mais ce n'est pas là que se pose le problème, pourquoi c'est algo est (pour le moment) inexploitable.



Edité 3 fois. La dernière correction date de il y a quatre années et a été effectuée par pourexemple.

Sauf qu'il faut connaître à l'avance la taille des à manipuler dans un algorithme, ce qui n'est pas toujours possible (avec à la clef un coût de complétion de la représentation en O(n^2) il me semble), et que même dans ce cas, le coût des opérations sur les entiers serait en O(n) indépendamment de la taille réelle des arguments. Et comment fait-on la division euclidienne dans une telle represéntation ?



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par jacquot.

Salut,

Citation
Parisse
Et comment fait-on la division euclidienne dans une telle représentation ?

Là est la question.

Cordialement.

Liste des forums - Statistiques du forum

Total
Discussions: 148 852, Messages: 1 501 169, Utilisateurs: 28 326.
Notre dernier utilisateur inscrit Alex46.

---

Ce forum
Discussions: 2 527, Messages: 18 780.