Approximer le produit de deux nombres sans les multiplier directement

[ansset]

dixit wiki :
Exemple 1 : En supposant que x = 435,728 et y = 1,6275 comment effectuer, sans calculatrice, le produit xy ?

On calcule log(x)
x = 4,35728.102 donc la caractéristique est 2, la mantisse se lit dans une table de logarithme : 0,6392
log(x) = 2,6392
on calcule log(y) , caractéristique 0, mantisse 0,2115
log(y) = 0,2115
Il suffit de calculer log(xy) = log(x) + log(y) = 2,8507, d'isoler la caractéristique : 2 et la mantisse 0,8507 qui par lecture inverse dans la table de log donne 7091.

le produit xy est donc environ 7,091.102 = 709,1
-----

[invite4492c379]

Hello,
je pense qu'Anthony cherche à ne pas utilise la multiplication scolaire mais à trouver une méthode qui ne recquiert pas l'utilisation de tables quelconqies, juste du papier un crayon et peu de mémoire.

[anthony_unac]

dixit wiki :
Exemple 1 : En supposant que x = 435,728 et y = 1,6275 comment effectuer, sans calculatrice, le produit xy ?

On calcule log(x)
x = 4,35728.102 donc la caractéristique est 2, la mantisse se lit dans une table de logarithme : 0,6392
log(x) = 2,6392
on calcule log(y) , caractéristique 0, mantisse 0,2115
log(y) = 0,2115
Il suffit de calculer log(xy) = log(x) + log(y) = 2,8507, d'isoler la caractéristique : 2 et la mantisse 0,8507 qui par lecture inverse dans la table de log donne 7091.

le produit xy est donc environ 7,091.102 = 709,1

J'ai déjà lu cet article, il est pas mal mais pour aboutir au résultat l'opérateur exploite la fameuse table sur laquelle figure toute une liste de mantisses.
Pour ma part, je me place dans un contexte ou l'opérateur est sans outils autre que ces doigts et son crayon.

[inviteea028771]

Dans ce cas deux possibilités :
- il va avoir beaucoup de multiplications à faire et dans ce cas il recalcule une table de logarithme (pénible, mais une fois calculée il peut s'en servir facilement)
- il ne va pas avoir beaucoup de multiplication à faire et dans ce cas il fait ses multiplications normalement sans se poser de questions.

[ansset]

il existe une ou plusieurs methodes pour les contruire.
en fait il y a peu de multiplication , par contre faut bien remplir le tableau , donc un peu laborieux

[anthony_unac]

Dans ce cas deux possibilités :
- il va avoir beaucoup de multiplications à faire et dans ce cas il recalcule une table de logarithme (pénible, mais une fois calculée il peut s'en servir facilement)
- il ne va pas avoir beaucoup de multiplication à faire et dans ce cas il fait ses multiplications normalement sans se poser de questions.

Et bien je vous propose quelque chose qui semble fonctionner pas trop mal mais bon (faut voir sur le terrain) :


Exemple 1 : Produit de deux termes comportant un nombre pair de chiffres
*********

: 8473
x 7351
--------

Coupons les termes par tranche de deux :

: 84 73
x 73 51
----------


et sont laissées à la libre appréciation de l'opérateur.
Ils correspondent grosso-modo à :


Pour ma part je définis par exemple en faisant grossièrement l'approximation + un petit quelque chose compte tenu du couple mis en jeu ici.




Le résultat exact était


Exemple 2 : Produit de deux termes comportant un nombre impair de chiffres
*********

: 141
x 526
-------

Coupons les termes par tranche de deux en ajoutant au préalable des zéros :

: 14 10
x 52 60
----------





Le résultat exact était

[inviteea028771]

Tu es en train de nous réinventer l'algorithme de Karatsuba (tu t'en rapproches en tout cas)

http://fr.wikipedia.org/wiki/Algorithme_de_Karatsuba

[anthony_unac]

Il semblerait que l'approximation se dégrade avec l'augmentation du nombre de chiffres constituant chaque facteur.
A titre d'exemple voici ce que l'on obtient avec cette méthode lorsqu'on multiplie les dix premières décimales de par les dix secondes :

vaut approximativement
La valeur exacte étant

[invite4492c379]

Coupons les termes par tranche de deux :

: 84 73
x 73 51
----------


et sont laissées à la libre appréciation de l'opérateur.
Ils correspondent grosso-modo à :


Pour ma part je définis par exemple en faisant grossièrement l'approximation + un petit quelque chose compte tenu du couple mis en jeu ici.

Tu calcules en base 100, tu approximes ab*cd par
(ac+x₀)10⁴ + (bd+x₁)10²=ac10⁴+x₀10⁴+bd10²+x₁10²
ab*cd=ac10⁴+(ac+bd)10²+bd

L'erreur commise est de D(x₀,x₁)=x₀10⁴+(x₁-ac)10²+bd

Si tu passes à plus de chiffres tu vas avoir du mal à minimiser cette erreur à mon avis.

[anthony_unac]

Au final, je crois que seuls les trois premiers chiffres sont corrects avec cette méthode et le reste est plus ou moins faux (ou juste) suivant les valeurs attribuées aux différents .

Néanmoins cela n'a pas que des inconvénients car ça permet d'approximer encore plus vite le produit de deux facteurs. Ainsi peut être approximé tout aussi bien par . Cela fournira les mêmes trois premiers chiffres significatifs avec cette méthode.

[anthony_unac]

En reprenant l'exemple du message , on remarque qu'il est possible de trouver la valeur exacte de . A partir de la méthode vous obtenez les premiers chiffres justes soit et vous savez que le résultat est un nombre à chiffres finissant par .
Le résultat est donc de la forme ou est le nombre de dizaines. Ce chiffre peut être défini à l'aide de la racine numérique (RN) de



On en déduit alors que et que

[anthony_unac]

Re,

La nuit porte conseil alors voici une façon d'affiner la méthode précédente :

Je repars sur l'exemple :
******************
En appliquant la méthode de tronçonnage des digits, on aboutit à
Je rappelle également que ce résultat peut être aisément trouvé en effectuant le produit tronqué : .

Je cherche à présent à affiner le résultat : en appliquant la méthode de Newton Raphson biaisée. J'aboutis à la relation :



On trouve alors un résultat affiné :

NB : Cet affinage nécessite de savoir extraire une racine carré à la main ce qui est très simple quand on connait la méthode de Héron en partant d'une bonne approximation à la louche.

[anthony_unac]

Et bien je vous propose quelque chose qui semble fonctionner pas trop mal sur le terrain :


Exemple : Produit de deux termes comportant un nombre pair de chiffres
*********

: 8473
x 7351
--------

Coupons les termes par tranche de deux :

: 84 73
x 73 51
----------






Le résultat exact était

Avec cette méthode on obtient en général un chiffre erroné (le 4e en partant de la droite) que l'on peut facilement corrigé avec les propriétés de la racine numérique.

[inviteea028771]

Pour reprendre ton exemple :
: 84 73
x 73 51
----------
84*73*10^4 + (84*73+73*51-(84-73)*(73-51))*10^2 + 73*51

= 62285023

On obtient le résultat exact avec 3 multiplications de la moitié du nombre de chiffres. Mais bon, ça n'est pas une méthode nouvelle (1960), elle est même employée en pratique.

[anthony_unac]

Ah c'était donc ça la relation exacte !
Merci de l'info !
Je ne savais pas que tout ceci datait des années 60
Dans la foulée je cherche aujourd'hui à approximer les grosses multiplications.
Disons que j'arrive à en tirer 4 chiffres significatifs en seulement 2 multiplications de deux chiffres et 4 termes de 4 chiffres à additionner ce qui est déjà pas mal

Exemple 1:
*********


L'idée c'est de parvenir à l'approximation :
Pour ce faire, j'analyse sur chaque facteur de la multiplication l'écart entre la 4e et la 2e digit :
(5-4)=1
(3-6)=-3
Les signes sont opposés donc le produit tronqué par excès:

Cela me fourni les 4 premiers chiffres significatifs :

Exemple 2:
*********


L'idée c'est de parvenir à l'approximation :
Pour ce faire, j'analyse sur chaque facteur de la multiplication l'écart entre la 4e et la 2e digit :
(5-4)=1
(6-3)=3
Les signes sont identiques donc le produit tronqué par défaut :

Cela me fourni les 4 premiers chiffres significatifs :

Mais tout ceci n'est valable que dans le cas des grandes multiplications de la forme n.m........*n'.m'.........

Exemple 3 :
**********


L'idée c'est de parvenir à l'approximation :
Pour ce faire, j'analyse sur chaque facteur de la multiplication l'écart entre la 3e et la 1e digit :
(3-1)=2
(7-9)=-2
Les signes sont opposés donc le produit tronqué par excès:

Cela me fourni les 4 premiers chiffres significatifs :