Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
126 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

La multiplication ultra-rapide

Envoyé par pourexemple 
La multiplication ultra-rapide
il y a deux années
avatar
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 deux années et a été effectuée par pourexemple.
Re: La multiplication ultra-rapide
il y a deux années
avatar
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.
Re: La multiplication ultra-rapide
il y a deux années
avatar
merci samok mais wiki en dira plus long (wikipédia)
Re: La multiplication ultra-rapide
il y a deux années
avatar
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.
Pièces jointes:
ouvrir | télécharger - E99987-preview.pdf (40.7 KB)
Re: La multiplication ultra-rapide
il y a deux années
avatar
@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 deux années et a été effectuée par pourexemple.
Re: La multiplication ultra-rapide
il y a deux années
avatar
ah oui, je vois que tu ne voiles pas les choses,

bonne continuation,

S

La poésie n'est pas une solution.
Re: La multiplication ultra-rapide
il y a deux années
avatar
La multiplication par 2 est, sur tous les ordinateurs actuels, bien plus rapide que n'importe quelle addition.
Re: La multiplication ultra-rapide
il y a deux années
avatar
Je parlais de grands entiers.
Re: La multiplication ultra-rapide
il y a deux années
avatar
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.
Re: La multiplication ultra-rapide
il y a deux années
avatar
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.
Re: La multiplication ultra-rapide
il y a deux années
avatar
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&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par pourexemple.
Re: La multiplication ultra-rapide
il y a deux années
avatar
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&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par pourexemple.
Re: La multiplication ultra-rapide
il y a deux années
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&egrave;re correction date de il y a deux ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par jacquot.
Re: La multiplication ultra-rapide
il y a deux années
avatar
Salut,

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

Là est la question.

Cordialement.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 135 908, Messages: 1 312 462, Utilisateurs: 23 858.
Notre dernier utilisateur inscrit Fidelis.


Ce forum
Discussions: 2 254, Messages: 16 633.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page