Une nouvelle façon de multiplier !

Ici, c'est la foire aux liens, mais attention pas du lien nimportnawak (le méchant modo y veillera), mais du vrai lien 'in topic'

Modérateur : Politburo

Répondre
Avatar de l’utilisateur
phe78
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 742
Inscription : 22 avr. 2011 19:08
Localisation : Var

Une nouvelle façon de multiplier !

Message par phe78 » 25 juil. 2020 11:05

Elle bat des records de vitesse, ça va booster nos vieilles pétoires grave....

https://www.quantamagazine.org/mathemat ... 20190411/

remy
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1847
Inscription : 13 mars 2006 16:39
Contact :

Re: Une nouvelle façon de multiplier !

Message par remy » 25 juil. 2020 13:30

Maintenant il nous reste à trouver les machines ayant utilisé cette méthode dans leur ROM.
PockEmul, Emulateur de pocket Sharp, Canon, Casio, HP, TI, NEC, Panasonic, Sanco, Seiko, General, National, ....
sur Windows, Linux, OS X et Android
Available now on the Google Play Store

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3151
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

Re: Une nouvelle façon de multiplier !

Message par Hobiecat » 25 juil. 2020 13:45

C'est intéressant !

La méthode de Karatsuba n'est déjà pas très intuitive, mais elle est très efficace !

Avatar de l’utilisateur
badaze
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 7155
Inscription : 12 févr. 2007 19:36
Localisation : Pas très loin de Lyon
Contact :

Re: Une nouvelle façon de multiplier !

Message par badaze » 25 juil. 2020 15:27

C’est facile puisque j’ai compris ! Si personne n’avait pensé à cette méthode avant il existe peut-être une autre encore plus rapide.
Tout est bon dans le pocket.
Moi j'aime tout.... Casio, HP, Sharp, TI et les autres sauf que les TI semblent ne pas m'aimer :(
http://www.emmella.fr
Mes Casio - HP - Sharp - TI
Homme invisible.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2193
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Une nouvelle façon de multiplier !

Message par C.Ret » 25 juil. 2020 18:36

oh! j'ai mal à la tête.

Je préfère l'ancienne méthode, il suffit de savoir ses tables et savoir faire une addition.

L'autre méthode nécessite, pour être efficace, de savoir comment grouper les chiffres, faire des multiplications, des soustractions et regrouper avec des décalages ... sans compter que cela ne règle toujours pas le problème de bien connaitre ses tables de multiplications.

C'est bien une idée tordue et biscornue ... Ah! Pourquoi je ne suis pas surpris que cette idée alambiquée provient de l'esprit tourmenté d'un polytechnicien ??

Quand aux ROM de nos calculettes je crois me souvenir qu'elles ne connaissent pas les tables de multiplications mais utilisent des méthodes égyptiennes (bien pratique en binaire) ou des astuces et raccourcis basés sur des restes chinois.

Sinon, oui la méthode qui est annoncée comme révolutionnaire revient en fait à regrouper les calculs pour effectuer le produit de deux polynômes:

Par exemple avec des nombres à deux chiffres : Image et Image, on a bien Image

Et effectivement : Image d'où Image

D'où les 7 étapes de la méthode polytechnicienne:
  1. Décomposer A et B en a, b, c et d
  2. Effectuer a.c
  3. Effectuer b.d
  4. Calculer a+b et c+d
  5. Effectuer le produit (a+b).(c+d)
  6. Soustraire à ce dernier produit a.c et b.d
  7. Assembler ; c'est à dire exprimer 100.ac + 10 . (ad+bc) + 1. bd
Moi je suis pas polytechnicien, pour calculer A x B, je sors de ma poche de chemise une HP-15C, je la fais glisser hors de son étuis en cuir de synthèse et je fais [ON] A [ENTER] B [ x ] et j'annonce le résultat.

Vive les écoles supérieures de chimie industrielle ! Vive les polymères et à bas les polyniantniants !!!


On remarquera que l'auteur de l'article ne donne aucune illustration numérique de la façon d'effectuer des multiplications à l'aide de Transformées de Fourier ...
Dommage, cela aurait été bien plus spectaculaire que leur béotienne application numérique vaguement polynomiale...
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3151
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

Re: Une nouvelle façon de multiplier !

Message par Hobiecat » 25 juil. 2020 20:28

Attention quand même, l'article explique bien que le bénéfice des méthodes proposées est pour les grands nombres. Bien sûr, sur des exemples triviaux, ça n'a que peu d'intérêt.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2193
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Une nouvelle façon de multiplier !

Message par C.Ret » 25 juil. 2020 20:49

Oui, nous sommes d'accord, l'article explique bien.

Et si aucun exemple n'est donné avec FFT c'est justement parce que cela n'est efficace (ou possible) qu'avec les multiplications que ne peut justement pas faire une HP-15C.

Leurs deux exemples numériques illustrent bien la première partie. C'est dommage qu'ils n'aient pas trouvé le moyen d'illustrer la seconde (celle qui concerne justement les transformées rapides de Fourier[°]) avec un petit polynôme de cinq ou six monômes et autant de coefficients complexes, puis la transformation inverse. Ou alors une (ou deux en séparant partie réelle et imaginaire) petite(s) matrice(s) juste histoire de donner une idée même un peut grossière du procédé.



[°] NDRL: J'ai fermé la page, je ne suis pas sûr que l'article précise le type de transformée de Fourier utilisée.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3151
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

Re: Une nouvelle façon de multiplier !

Message par Hobiecat » 25 juil. 2020 22:05

Effectivement le type de transformée de Fourier n'est pas précisé, seulement qu'elle est "fast". :wink:

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2193
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Une nouvelle façon de multiplier !

Message par C.Ret » 26 juil. 2020 08:43

Hobiecat a écrit :
25 juil. 2020 20:28
[...]Attention quand même, l'article explique bien que le bénéfice des méthodes proposées est pour les grands nombres. [...]
Effectivement, cet article a l'intérêt de donner l'état actuel de la recherche en sciences numérique. Et par grands nombres, Harvey et van der Hoeven ne battent Fürer qu'en régime asymptotique qu'ils estimaient l'année dernière atteindre dès le calcul de multiplication de nombres d'une taille supérieure à 2^(1729^12) chiffres !

HALUCINANT !
Ca c'est de la bonne Recherche Appliquée ( il s'agit d'effectuer des calculs ) qui sert à tout le monde ( tout le monde fait des calculs avec des nombres ...astronomiquement grands... plus grands que ... toutes les galaxies réunies ... ( hein ?!)

Bon, c'est de la recherche et c'est ce qui ce fait en se moment dans les labos de nos universités...
... c'est bien ...
... même si je ne suis pas sûr que cela aide très directement nos industries, commerces ou même aide à remettre en marche nos pays...



En tout cas, en cherchant rapidement à me documenter, j'ai trouvé cette figure qui explique bien le principe de la multiplication Schönhage–Strassen , par un petit exemple numérique volontairement simple ( on n'est qu'à 2^(3^1) chiffres, ne pas s'emballer même mon HP-15C va s'en sortir sans aucun programme spécifique)

Image


On retrouve bien les 7 étapes de l'algorithme de Karatsuba ; regroupement/décomposition, transformées de Fourier Rapide (FFT), les multiplications intermédiaires (sans retenue), la transformées de Fourier rapide inverse (iFFT) et la recomposition du résultat (effectuant les retenues).

L'astuce pour que tout fonctionne est de bien choisir l'anneau dans lequel on effectue les FFT et iFFT, ici Z/=337 et la huitième racine w8 = 85.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3151
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

Re: Une nouvelle façon de multiplier !

Message par Hobiecat » 26 juil. 2020 11:20

C.Ret a écrit :
26 juil. 2020 08:43
En tout cas, en cherchant rapidement à me documenter, j'ai trouvé cette figure qui explique bien le principe de la multiplication Schönhage–Strassen , par un petit exemple numérique volontairement simple ( on n'est qu'à 2^(3^1) chiffres, ...
Merci, c'est très intéressant ! Il est clair avec la transformée de Fourier et son inverse, qu'on sort un peu des compétences de nos pockets. D'ailleurs, est-ce que certains pockets ont ces possibilités ?

Sinon pour l'application, sauf erreur, les recherches géologiques et astronomiques utilisent des grands nombres, donc j'imagine que ces méthodes sont déjà utilisées par les calculateurs qui travaillent dans ces domaines.

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 2193
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Une nouvelle façon de multiplier !

Message par C.Ret » 27 juil. 2020 19:16

Hobiecat a écrit :
26 juil. 2020 11:20
[...]! Il est clair avec la transformée de Fourier et son inverse, qu'on sort un peu des compétences de nos pockets. D'ailleurs, est-ce que certains pockets ont ces possibilités ? [...]
La seule calculatrice que je possède qui ait nativement les Transformées Discrètes de Fourier est l' HP Prime qui proposent les transformations FFT et iFFT.

D'ailleurs, ces deux instructions prennent trois arguments, le vecteur Image de dimension n, la valeur a de la n-ième racine primitive de l'unité et le module p indiquant de faire la transformée dans l'anneau Image.

On obtient donc très facilement les valeurs numériques de l'illustration. Elles ne sont pas dans le même ordre que sur la figure à l'issue de la FFT, mais ce n'est pas grave car la transformation inverse iFFT remet en quelque sorte l'ordre logique et l'on obtient bien la même convolution (indiquée sur la figure par la flèche bleue)
Schoenhage Strassen FFT iFFT on HP Prime.png
Schoenhage Strassen FFT iFFT on HP Prime.png (13.23 Kio) Consulté 167 fois
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803 + SD2iec. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator | HP-15C | CASIO fx-602p + FA-1. .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
Hobiecat
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3151
Inscription : 06 sept. 2011 14:57
Localisation : Normandie

Re: Une nouvelle façon de multiplier !

Message par Hobiecat » 27 juil. 2020 20:33

On pourrait donc s'essayer aux calculs de grands nombres sur la Prime avec ces fonctions, quoique celle-ci ait déjà de bonnes capacités avec les grands nombres.

Répondre

Revenir vers « Liens en vrac »