algorithme de division entre (très grands) entiers

[jacknicklaus]

Bonjour,


pour le fun, je me lance dans le codage des fonctions arithmétiques usuelles sur grands nombres entiers (centaines de milliers de chiffres, pour avoir l'ordre de grandeur) : addition, multiplication, division euclidienne.
En ce qui concerne la division, je veux obtenir quotient et reste. Je pourrais reproduire l'algorithme "potence" appris à l'école, mais je suppose qu'il en existe de plus efficaces. Auriez vous un peu de littérature ou des pistes à me conseiller à ce sujet ?

J'utilise un langage relativement proche de python, et ma représentation interne d'un grand entier est basée sur une liste d'entiers dont chacun "tient" dans 31 bits, de sorte que la multiplication de deux éléments de liste ne déborde pas (le langage supporte les entiers 64 bits). Mais bon je pense que c'est assez neutre pour ma question, vu que c'est un algorithme que je cherche, et non du code tout fait ni une librairie toute faite.


merci d'avance !
-----

[Paraboloide_Hyperbolique]

Bonjour,

En regardant les références utilisées par la bibliothèque GMP, je suppose qu'il doit y avoir des choses intéressantes: https://gmplib.org/gmp-man-6.2.1.pdf (à partir de la page 130 (136))

Par exemple, j'ai trouvé ceci qui semble intéressant pour un algorithme de division entre entiers: https://gmplib.org/~tege/divcnst-pldi94.pdf

Voyez si cela vous semble intéressant ou non.

[jacknicklaus]

merci à toi, je vais regarder çà.

[jiherve]

bonsoir,
si tu n'es pas pressé la méthode euclidienne fonctionne sur n'importe quel taille d'entier juste un bricolage à faire si N<D.
autrement encore et encore le CORDIC!
JR

[A voir en vidéo sur Futura]

[jacknicklaus]

Si je comprends correctement le CORDIC, on ne peut faire des divisions a/b que dans des cas restreints à .

ca m'arrange pas trop...

[jiherve]

re
ben on "normalise" en entrée et on "dénormalise" en sortie c'est peu couteux.
JR

[CM63]

Bonjour,

Autre info : les langages de programmation Python et Java (ainsi que Javascript) possède un type d'entier "à nombre illimité de chiffres" (ou plutôt, qui n'est limitée que par les spécifications de la machine). Ce type d'entier possède une division euclidienne qui pourrait te convenir. Évidemment j'imagine que les calculs sont lents, mais tu n'es peut-être pas pressé

[jacknicklaus]

Bonjour CM63, je ne cherche pas à utiliser Python ou Java, mon but est de coder moi même, pour le fun, un algo si possible rapide, de division d'entier.

L'idéal serait en effet de trouver les specs des algo internes de division utilisés dans Python ou autre. Mais là.... Je ne sais pas du tout où obtenir de telles infos...

[jiherve]

bonjour
as tu fait une recherche avec "algorithme division "?
il en existe beaucoup.
JR