La multiplication ultra-rapide
Salut,
Décrire une multiplication sur les entiers quasi aussi rapide que l'addition (en utilisant les processeurs actuels).
Cordialement.
Décrire une multiplication sur les entiers quasi aussi rapide que l'addition (en utilisant les processeurs actuels).
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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
S
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.
bonne continuation,
S
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.
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.
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
$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.
Là est la question.
Cordialement.