Approximer le produit de deux nombres sans les multiplier directement

invite51d17075 · 05/11/2011, 11h21

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 · 05/11/2011, 12h45

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.

invitefd4e7c09 · 05/11/2011, 16h09

Envoyé par 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

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 · 05/11/2011, 16h46

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.

invite51d17075 · 05/11/2011, 17h50

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

invitefd4e7c09 · 05/11/2011, 17h58

Envoyé par Tryss

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
----------
$\text{[math]}$

$\text{[math]}$ et $\text{[math]}$ sont laissées à la libre appréciation de l'opérateur.
Ils correspondent grosso-modo à :
$\text{[math]}$
$\text{[math]}$
Pour ma part je définis par exemple $\text{[math]}$ en faisant grossièrement l'approximation $\text{[math]}$ + un petit quelque chose compte tenu du couple $\text{[math]}$ mis en jeu ici.
$\text{[math]}$
$\text{[math]}$
$\text{[math]}$

Le résultat exact était $\text{[math]}$

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
----------
$\text{[math]}$
$\text{[math]}$
$\text{[math]}$
$\text{[math]}$

Le résultat exact était $\text{[math]}$

inviteea028771 · 05/11/2011, 18h06

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

invitefd4e7c09 · 05/11/2011, 18h44

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 $\text{[math]}$ par les dix secondes :

$\text{[math]}$ vaut approximativement $\text{[math]}$
La valeur exacte étant $\text{[math]}$

invite4492c379 · 05/11/2011, 18h45

Envoyé par anthony_unac

Coupons les termes par tranche de deux :

: 84 73
x 73 51
----------
$\text{[math]}$

$\text{[math]}$ et $\text{[math]}$ sont laissées à la libre appréciation de l'opérateur.
Ils correspondent grosso-modo à :
$\text{[math]}$
$\text{[math]}$
Pour ma part je définis par exemple $\text{[math]}$ en faisant grossièrement l'approximation $\text{[math]}$ + un petit quelque chose compte tenu du couple $\text{[math]}$ mis en jeu ici.
$\text{[math]}$
$\text{[math]}$
$\text{[math]}$

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.

invitefd4e7c09 · 05/11/2011, 19h02

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 $\text{[math]}$ .

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

invitefd4e7c09 · 06/11/2011, 00h05

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

$\text{[math]}$

On en déduit alors que $\text{[math]}$ et que $\text{[math]}$

invitefd4e7c09 · 06/11/2011, 10h47

Re,

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

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

Je cherche à présent à affiner le résultat : $\text{[math]}$ en appliquant la méthode de Newton Raphson biaisée. J'aboutis à la relation :

$\text{[math]}$

On trouve alors un résultat affiné : $\text{[math]}$

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.

invitefd4e7c09 · 08/11/2011, 21h47

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
----------
$\text{[math]}$

$\text{[math]}$

$\text{[math]}$

Le résultat exact était $\text{[math]}$

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 · 09/11/2011, 00h14

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.

invitefd4e7c09 · 09/11/2011, 13h35

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:
*********
$\text{[math]}$

L'idée c'est de parvenir à l'approximation : $\text{[math]}$
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: $\text{[math]}$
$\text{[math]}$
Cela me fourni les 4 premiers chiffres significatifs : $\text{[math]}$

Exemple 2:
*********
$\text{[math]}$

L'idée c'est de parvenir à l'approximation : $\text{[math]}$
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 : $\text{[math]}$
$\text{[math]}$
Cela me fourni les 4 premiers chiffres significatifs : $\text{[math]}$

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

Exemple 3 :
**********
$\text{[math]}$

L'idée c'est de parvenir à l'approximation : $\text{[math]}$
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: $\text{[math]}$
$\text{[math]}$
Cela me fourni les 4 premiers chiffres significatifs : $\text{[math]}$

Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Re : Approximer le produit de deux nombres sans les multiplier directement

Discussions similaires

primitive d'un produit de deux variables

aide sur résultat d'un produit scalaire ???

multiplier les entrées et les sorties d'un pic (multiplexage ?)

Développement d'un produit de deux polynômes

notation d'un résultat de produit vectoriel