Forum Prepas.org

fakbill a écrit :Chez nous on dirait que c'est une façon bien "française" de voir la chose

Surtout que c'est peut-être tentant mais inexact.

C'est évidemment un peu compliqué, surtout pour aboutir à un résultat faux. Mais je pense que c'est ainsi que le professeur de Bidoof a obtenu son résultat.

Cependant, ça a un intérêt : en réparant l'erreur sur la partie entière, on montre correctement que $ N(n\, m)\leqslant N(n)+N(m) $. L'exemple proposé par un autre intervenant montre quant à lui seulement que $ N(n\, m)\geqslant N(n)+N(m) $ et non l'égalité : on pourrait envisager d'autres exemples où il faudrait encore plus de bits pour le produit, et c'est d'ailleurs ce qui se passe si on part d'un mauvais exemple (comme 7 et 8). C'est la conjonction des deux qui permet de conclure rigoureusement.

Par ailleurs, voir le lien entre nombre de chiffres et logarithme est intéressant pour développer la compréhension des logarithmes d'une part et aussi pour trouver des écritures scientifiques en base 2 (ce qui est pertinent pour comprendre les flottants) et enfin pour faire le lien entre le nombre chiffres corrects gagnés à chaque itération d'un algo de calcul numérique (ex. recherche de zéro de fonction par dichotomie) et la complexité.

YS1 a écrit : on pourrait envisager d'autres exemples où il faudrait encore plus de bits pour le produit, et c'est d'ailleurs ce qui se passe si on part d'un mauvais exemple (comme 7 et 8 ).

???

7 s'écrit sur 3 bits, 8 s'écrit sur 4 bits et 7*8=56 s'écrit sur 6 bits soit 3+4-1, donc à la lumière de ce seul exemple, on peut croire que $ N(n\,m)=N(n)+N(m)-1 $, ce qui n'est pas le cas.

YS1 a écrit :7 s'écrit sur 3 bits, 8 s'écrit sur 4 bits et 7*8=56 s'écrit sur 6 bits soit 3+4-1, donc à la lumière de ce seul exemple, on peut croire que N(n\,m)=N(n)+N(m)-1, ce qui n'est pas le cas.

Je relevais ceci :

YS1 a écrit :on pourrait envisager d'autres exemples où il faudrait encore plus de bits pour le produit

Il n'y a aucun produit qui nécessite plus de bits que n+m, le max c'est n+m, voilà tout.
Il suffit de poser la multiplication à l'ancienne pour le voir.

Il suffit de poser la multiplication à l'ancienne pour le voir. : hé oui...voila.

11*11=1001. Rajouter autant de zéros à la fin que nécessaire. C'est le maximum, car a<2^m et b<2^m implique ab<2^(m+n).

L'erreur vient du fait que pour coder 2^(m+n)-2^m-2^n+1, il faut m+n-1[=log du résultat]+1=m+n.