Répondre à la discussion
Affichage des résultats 1 à 9 sur 9

algorithme de division entre (très grands) entiers



  1. #1
    jacknicklaus

    algorithme de division entre (très grands) entiers


    ------

    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 !

    -----
    Dernière modification par jacknicklaus ; 03/12/2021 à 09h52.
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    Paraboloide_Hyperbolique

    Re : algorithme de division entre (très grands) entiers

    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.
    Dernière modification par JPL ; 03/12/2021 à 19h07. Motif: Titre corrigé

  5. #3
    jacknicklaus

    Re : algorithme de division entre (très grands) entiers

    merci à toi, je vais regarder çà.
    Dernière modification par JPL ; 03/12/2021 à 19h08. Motif: Titre corrigé
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  6. #4
    jiherve

    Re : algorithme de division entre (très grands) entiers

    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
    l'électronique c'est pas du vaudou!

  7. A voir en vidéo sur Futura
  8. #5
    jacknicklaus

    Re : algorithme de division entre (très grands) entiers

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

    ca m'arrange pas trop...
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  9. #6
    jiherve

    Re : algorithme de division entre (très grands) entiers

    re
    ben on "normalise" en entrée et on "dénormalise" en sortie c'est peu couteux.
    JR
    l'électronique c'est pas du vaudou!

  10. Publicité
  11. #7
    CM63

    Re : algorithme de division entre (très grands) entiers

    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é
    Déjà de base.

  12. #8
    jacknicklaus

    Re : algorithme de division entre (très grands) entiers

    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...
    There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

  13. #9
    jiherve

    Re : algorithme de division entre (très grands) entiers

    bonjour
    as tu fait une recherche avec "algorithme division "?
    il en existe beaucoup.
    JR
    l'électronique c'est pas du vaudou!

Discussions similaires

  1. Bijection entre l'ensemble des entiers naturels et des entiers pairs
    Par moial dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 04/07/2014, 23h02
  2. Distance entre deux nombres premiers pour des nombres très grands
    Par FibreTigre dans le forum Mathématiques du supérieur
    Réponses: 9
    Dernier message: 12/06/2013, 22h56
  3. Groupe des entiers infiniment grands.
    Par RoBeRTo-BeNDeR dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 02/12/2012, 01h29
  4. Circuit qui permet la division de 2 entiers du 4bits
    Par af.zakaria dans le forum Électronique
    Réponses: 0
    Dernier message: 11/11/2012, 02h01
  5. division rapide des grands nombres
    Par Pole dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 23/09/2005, 18h15