Une nouvelle façon de multiplier !
Modérateur : Politburo
- phe78
- Fonctionne à 1200 bauds
- Messages : 722
- Enregistré le : 22 avr. 2011 19:08
- Localisation : Les Adrets de l'Esterel (Var)
Une nouvelle façon de multiplier !
Elle bat des records de vitesse, ça va booster nos vieilles pétoires grave....
https://www.quantamagazine.org/mathemat ... 20190411/
https://www.quantamagazine.org/mathemat ... 20190411/
-
- Fonctionne à 2400 bauds
- Messages : 2221
- Enregistré le : 13 mars 2006 15:39
- Localisation : Issy
- Contact :
Re: Une nouvelle façon de multiplier !
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 and the Apple Store
sur Windows, Linux, OS X et Android
Available now on the Google Play Store and the Apple Store
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Une nouvelle façon de multiplier !
C'est intéressant !
La méthode de Karatsuba n'est déjà pas très intuitive, mais elle est très efficace !
La méthode de Karatsuba n'est déjà pas très intuitive, mais elle est très efficace !
- badaze
- Fonctionne à 14400 bauds
- Messages : 8409
- Enregistré le : 12 févr. 2007 18:36
- Localisation : Pas très loin de Lyon
- Contact :
Re: Une nouvelle façon de multiplier !
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.
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Une nouvelle façon de multiplier !
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 : et , on a bien
Et effectivement : d'où
D'où les 7 étapes de la méthode polytechnicienne:
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...
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 : et , on a bien
Et effectivement : d'où
D'où les 7 étapes de la méthode polytechnicienne:
- Décomposer A et B en a, b, c et d
- Effectuer a.c
- Effectuer b.d
- Calculer a+b et c+d
- Effectuer le produit (a+b).(c+d)
- Soustraire à ce dernier produit a.c et b.d
- Assembler ; c'est à dire exprimer 100.ac + 10 . (ad+bc) + 1. bd
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 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Une nouvelle façon de multiplier !
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Une nouvelle façon de multiplier !
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.
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 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Une nouvelle façon de multiplier !
Effectivement le type de transformée de Fourier n'est pas précisé, seulement qu'elle est "fast".
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Une nouvelle façon de multiplier !
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)
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 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Une nouvelle façon de multiplier !
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.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3421
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Une nouvelle façon de multiplier !
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 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 .
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)
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- Hobiecat
- Fonctionne à 9600 bauds
- Messages : 3644
- Enregistré le : 06 sept. 2011 14:57
- Localisation : Normandie
Re: Une nouvelle façon de multiplier !
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.