Discussion:Division euclidienne

Liens

le lien de Dividende va vers la définition économique. J'inverse les liens. Fafnir 11 fev 2005 à 07:27 (CET)

Méthode courante, binaire

l'article dit On montre facilement par récurrence qu'à chaque étape n de ce deuxième calcul, αn et βn sont deux entiers dont seul le (N + 1 − n)ème chiffre du développement décimal diffère J'ai l'impression que c'est plutôt de développement binaire qu'il s'agit, mais comme je ne suis pas trop sûr, je préfére ne pas effectuer la modification directement sur l'article.

Je pense qu'il s'agit bien de l'écriture en base 2. J'ai modifié l'article pour que la récurrence soit plus claire sans allusion à l'écriture en base 2. HB 25 mai 2006 à 09:03 (CEST)

Effectivement, il s'agissait bien du développement binaire. Ce qu'il reste à faire, c'est à écrire des exemples, en binaire, et en décimal ; en fait, la référence au nombre de chiffres qui diffèrent me semblait assez intéressante, parce que c'est ce qu'on voit quand on pose la division : on trouve le premier chiffre du quotient puis le deuxièmes, etc... et c'est bien sûr la même chose en binaire qu'en décimal.Salle 25 mai 2006 à 23:29 (CEST)

Informatique

Bonjour, je ne sais pas si cela est pertinent pour l'article mais j'ai remarqué, dans le domaine informatique, que de nombreux langages de développement permettait la division entière comme fonctionnalité de base. Il s'agit d'une division entière directement intégrée dans les processeurs de nos ordinateurs.

// En C
int dividende, diviseur, quotient;
quotient = dividende / diviseur;

Il faut cependant noter que cette division entière est fausse puisqu'elle ne correspond pas à la division euclidienne dans le cas des nombres négatifs, le quotient proposé dans ce cas ne permettant pas d'obtenir un reste positif.

Notamment, la division de -8 par 3 donne -2 au lieu de -3. -3 étant pourtant la bonne solution car -8 = 3 × (-3) + 1

VincentRobert

Tout à fait, j'ajoûte pour prouver que le processeur prend totalement en charge la division : l'assembleur, qui n'a a la base pas grand-chose comme fonction préfabriquée, possède une instruction de division réalisable en une seule ligne :
; pour AX = 18 et BX = 5
IDIV BX
; résultats : AX = 3 et DX = 3 (DX étant le reste)

L'assembleur étant une transcription littérale en ascii des données envoyées au processeur, il n'y a assurément pas d'algo nécessaire pour réaliser une division. --Glaviot (d) 23 février 2011 à 03:45 (CET)

« il n'y a assurément pas d'algo nécessaire pour réaliser une division ». Mmmouais le fait que l'algo soit implémenté en dur dans le hardware plutôt qu'écrit en plus ou moins mou dans le software ne le rend pas pour autant « pas nécessaire » (si je ne fais pas de contresens, l'informatique est hors mon domaine de compétence). Et, plus accessoirement, les divisions ne sont pas toutes faites sur ordinateur. Touriste (d) 23 février 2011 à 15:36 (CET)

Tout dépend du CPU. En assembleur Z-80 par exemple il n'y a pas d'instruction de division et il est nécessaire de la programmer en Z80. De façon générale je pense que «l'assembleur» au singulier n'a pas de sens puisque chaque CPU a son propre langage assembleur et qu'il y a beaucoup de CPUs différents. Dans le rapport Von Neumann les divisions étaient programmées, pas câblées (de mémoire, algorithme proche de celui des égyptiens).

Alain Busser (discuter) Alain Busser (discuter) 2 juillet 2022 à 08:48 (CEST)

Dans le même ordre d'idée

Pour les entiers naturels , division euclidienne = division entière. Pour les entiers relatifs, il y a du flottement (ex: Ivan Flores vs Donald Knuth). Tous partent de a = b*q+r, l'ensemble des (q, r) possibles étant a priori dénombrable !

• Pour les uns, calquant aux signes près la division entre naturels, l'unicité du résultat est basé sur un quotient "au plus près de zéro", et le reste est signé 2 fois sur 4.
• Ceux qui veulent embrayer sur congruences et arithmétique modulaire imposent plutôt un reste positif.
• Ces définitions divergent 2 fois sur 4.

a	b	q1	r1	q2	r2
15	7	2	1	2	1
15	-7	-2	1	-2	1
-15	7	-2	-1	-3	+6
-15	-7	2	-1	3	+6

La première école fournit un reste du signe du dividende. Il pourrait être du signe du diviseur, du signe du quotient.... Bref, traiter par dessus la jambe la question de l'unicité du résultat pousse aux confusions. Je propose que soient explicités les deux points de vue .

1. division entière usuelle : quotient au plus près de 0, et son reste
2. calcul du résidu euclidien, support des congruences, et éventuellement du quotient associé ...

---

---

Eviter une symbolique techno-centrée qui, même parfaite, rebute le lecteur. 92.157.17.30 (d) 25 août 2010 à 11:02 (CEST)

Comprendre

Je comprend rien à tout ça ! 83.202.26.120 30 janvier 2007 à 20:00 (CET)

Idem — Le message qui précède, non signé, a été déposé par un utilisateur sous l’IP 109.8.151.25 (discuter), le 20 septembre 2012.

Ajout

Il faudrait ajouter la langue espagnole vis-à-vis de cette article, car il existe sous le nom de "División euclidiana", malgré le fait que sur la page française l'article espagnol n'apparaît pas. Comment faire?

Article ésotérique

Cet article est parfaitement incompréhensible par le lecteur moyen, même cultivé. Il est rédigé en "langue mathématique internationale" accessible exclusivement aux spécialistes. Or fr-Wikipedia est, par définition, une encyclopédie (donc destinée à tous) rédigée en français. Cet article ne répond à aucun de ces deux critères et ne mérite donc nullement le classement BD. Il devrait comporter en son début une explication détaillée et accessible de ce qu'est la division euclidienne, de son histoire etc... Après cela, rien n'empêche d'être pointu et de s'adresser aux spécialistes à l'aide de signes cabalistiques. Roymail (d) 25 septembre 2009 à 14:32 (CEST)

Incompréhensible

Je suis le seul à trouver aberrant que même la partie "méthode naïve", décrite comme enfantine et naturelle, soit aussi incompréhensible pour une personne lambda que n'importe quelle autre méthode ? Pourquoi ne pas dire simplement un truc du genre :
Je veux diviser 14 par 4. Je dessine 14 cases à la suite, je colorie quatre cases, puis quatre autres, autant que possible, et au bout de 3 fois, il me reste seulement 2 cases blanches. Le quotien est donc 3, et le reste 2.
Avec, pourquoi pas, un gif animé représentant les cases et les séries de remplissage. --Glaviot (d) 23 février 2011 à 03:33 (CET)

Non visiblement tu n'es pas le seul (voir les section "comprendre" et "article ésotérique"). Ce qui est amusant c'est que l'article dans ses débuts était plus abordable [1] mais une refonte de Selenite[2] (ancien étudiant , je crois maintenant à Normale Sup) lui a fait perdre son accessibilité. Vu les trois réaction de cette pdd, j'avais raison à l'époque de vouloir une introduction plus accessible. Je retiens ton idée (pas de gif mais de schéma et, éventuellement d'animation ogv) et propose une section première approche reprenant un exemple; la mise en place de l'égalité et une allusion à Euclide. HB (d) 23 février 2011 à 11:37 (CET)

Je me permets de nuancer quand même, j'ai l'impression d'avoir une position un peu "centriste" quelque part entre l'auteur de la section et vous, probablement plus sympathique à l'auteur de la section. Je ne vois pas où cette méthode « naïve » est décrite comme « enfantine et naturelle » : il s'agit tout de même d'une sous-section d'une section consacrée à des "algorithmes". La description de l'algorithme sur un exemple plutôt que par formalisation, à la rigueur ; sa description en termes de "coloriage" me semble une bizarrerie - on n'écrit pas à destination d'un public plutôt qu'un autre mais en singeant plus ou moins les sources - si on me produit des sources traitant de l'aspect algorithmique de la division dans un style école maternelle, soit, mais existent-elles vraiment ? Une question qu'on peut en revanche se poser est de savoir s'il est pertinent de commencer par expliciter un algorithme simple mais médiocre : s'il s'agissait d'écrire un cours, à l'évidence oui, sa médiocrité est une motivation pour aller plus loin - mais si on expose un sujet de façon synthétique, les algorithmes inefficaces sont-ils à décrire ? Dans un hypothétique article détaillé algorithmes de division euclidienne, certainement oui, mais dans cet article élémentaire ? Comme toujours, la véritable solution est de consulter des sources : comment font-elles ? Touriste (d) 23 février 2011 à 15:32 (CET)

Remarque additionnelle à HB : je pense que tu renvoies à tort à la section « Article ésotérique » où l'intervenant, avec raison, se plaint de ce que l'article ne commence pas par une partie accessible à tous - il ne remet en revanche pas en cause l'existant, mais souligne simplement tout à fait justement qu'il devrait être relégué plus en profondeur dans un article plus long. Si je le comprends bien, Glaviot ne propose pas d'ajouter une ouverture plus lisible à l'article mais de remplacer une partie de l'existant par quelque chose d'une toute autre tonalité. Sur cette orientation, je ne suis pas franchement convaincu. Touriste (d) 23 février 2011 à 15:41 (CET)

Algorithme de division

il manque à mon avis l'algorithme de division selon la méthode égyptienne utilisant le principe de la base 2: pour diviser 93 par 7 on présente dans un tableau la liste des puissances de 2 et de leur produit par 7. On reconstitue 93 (ou plus exactement le multiple de 7 le plus proche de 93 par addition successive, la somme correspondante des puissances de 2 donne le quotient.

1	7
2	14
4	28
8	56

pour reconstituer 93, il faut prendre 56, prendre 28 , ne pas prendre 14 (trop grand), et prendre 7.

Le quotient est alors 8 + 4 + 1 = 13.

Je trouve un intérêt historique à cet algorithme. Mais je suis incapable d'en donner la complexité (il me semble polynomial) et plus simple que la dichotomie. Mais comme il est présenté de manière naïve et que je ne compte pas le formaliser, j'hésite à le mettre dans la partie algorithme. HB (d) 25 février 2011 à 11:52 (CET)

Une présentation "naïve", c'est mieux que rien. N'hésite pas. L'intérêt historique est indéniable. ---- El Caro ^bla 25 février 2011 à 12:26 (CET)

Si les multiplications par deux et les soustractions se font en temps constant (ce qui est le cas en codage binaire dans ce cas, avec une constante proportionnelle au logarithme du diviseur), vu que le nombre maximum de soustractions est le nombre de multiplications par deux, c'est-à-dire le logarithme du quotient en base 2, la complexité de l'algorithme est assez nettement logarithmique en les données. Ambigraphe, le 24 septembre 2012 à 21:03 (CEST)

je pense qu'il manque l'étape d'arrêt, il faut aller jusqu'à 16*7 pour voir que ça dépasse 93.Klinfran (discuter) 10 janvier 2022 à 12:35 (CET)

Corriger

"Dans les certains environnements, le reste de la division par un négatif, est négatif." supprimer "les" dans le cartouche de droite.Magnon86 (discuter) 11 novembre 2018 à 15:26 (CET)magnon86

WP:N'hésitez pas ! ; JLM (discuter) 11 novembre 2018 à 15:28 (CET)

Fait. HB (discuter) 11 novembre 2018 à 19:35 (CET)

Division Euclidienne dans d'autres ensembles

Il faudrait plutôt parler d'ensembles plus généraux quand on parle de polynômes et d'anneaux, la division Euclidienne sur les entiers en étant un cas particulier. Egalement y introduire le fait qu'il n'y a pas forcément unicité, et mettre un exemple sur les entiers de Gauss ainsi qu'une référence imnho Klinfran (discuter) 10 janvier 2022 à 12:39 (CET)

éléments d'Euclide

L'algorithme de calcul de pgcd est dans le livre VII d'Euclide et n'utilise pas la division euclidienne. Dans quelle partie des éléments Euclide parle-t-il de la division euclidienne ? Alain Busser (discuter) 2 juillet 2022 à 09:07 (CEST)

Tu as raison : Euclide ne définit pas la division euclidienne. Il parle d'un nombre qui serait «partie» d'un autre (plus grand) s'il le mesure et d'un nombre qui ne serait que «parties» d'un autre (plus grand) s'il ne mesure pas. Puis il passe rapidement à la recherche d'une mesure commune de deux nombres en soustrayant le plus petit au plus grand autant de fois que nécessaire, s'il y arrive c'est que le plus petit mesure le plus grand, sinon c'est qu'il y a un reste (qui devient le plus petit des deux nombres) et rebelote. C'est donc dans cette description de l'algorithme qu'apparait en filigrane ce qu'on appelle aujourd'hui "division euclidienne". C'est pourquoi, dans mon ajout de 2010, je dis qu'il en «explique le principe» et non qu'il la définit mais c'est peut-être trop présomptueux ou mal formulé. N'hésite pas à corriger. Rem: le lien entre division et soustractions successives est aussi souligné par Caveing ici. HB (discuter) 2 juillet 2022 à 12:16 (CEST)