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

division rapide des grands nombres



  1. #1
    Pole

    division rapide des grands nombres


    ------

    Bonjour,
    je me fais des bibliothèque sur les grands nombres et je bloque sur les divisions. J'ai déja posé cette question mais l'algorithme donné était assez efficace pour les nombres dans une petite base. Et moi, je travaille en base 10 000. Je cherche un algorithme assez rapide, et dont la complexité ne dépend pas de la base où je travaille.
    Merci.

    -----
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

  2. #2
    shokin

    Re : division rapide des grands nombres

    Salut,

    désolé, je n'ai pas la folie des grandeurs

    J'ai simplement vu que ce message n'avait reçu aucune réponse.

    PS : En voilà une en espérant qu'une personne puisse trouver confort en ce problème ténu et tenu.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  3. #3
    Moma

    Re : division rapide des grands nombres

    Citation Envoyé par Pole
    dont la complexité ne dépend pas de la base où je travaille.
    Merci.
    Bonjour,

    a priori, la complexité va être polynomial, et donc en puissance de log(n) si n est ta donnée. Changé la base revient à changer la base du logarithme, et la complexité ne change pas... Mais je ne suis pas sûr d'avoir compris ce que tu voulais dire.

    JPour reprendre ton problème, j'ai été confronté au même problème. Je suis d'abord passé par des chaines d'entiers, mais le procédé était plutôt lent. J'ai ensuite opté pour des approximation flotantes. en fait, je détermine les chiffres du quotient par "tranche" de la longueur du nombres de décimales des flotants. (soustraction, puis détermination du quotient pour un nombre plus petit...). Sinon, peut-être que tu pourrais consulter le bouquin de Knuth (je ne sais plus exactement son titre, mais c'est un bouquin fondamental en info, je pense que tu trouveras). Sinon, un bouqin plus récent sur les algos utiles en théories des nombres est paru recement. Un des auteurs est pomerance il me semble (je dois avoir la référence qqe part, mais je sais vraient plus où).

    Voilà à peu près ce que je peux dire pour t'aider.

    Amicalement
    Moma

  4. #4
    Pole

    Re : division rapide des grands nombres

    J'aimerai bien trouver un algorithme polynomial.

    Complexité de la base :

    c=nombre de chiffres de a - nombre de chiffres de b - 1;
    b1=b*base^c;
    r=0;
    while (b1>=b){
    while (a>=b1){
    r=r+1;
    a=a-b1;
    }
    b1=b1/base;
    if (b1>=b) alors r=r*base;
    }

    Voilà un algo assez lent pour les grandes bases.

    Moma : je ne sais pas lire l'anglais.
    Pour comprendre la récursivité croisée, il faut comprendre les arbres d'appels. Et vice versa.

Discussions similaires

  1. Envoyer des grands fichiers
    Par lui dans le forum Internet - Réseau - Sécurité générale
    Réponses: 5
    Dernier message: 23/05/2008, 16h56
  2. Lois des grands nombres
    Par christophe_de_Berlin dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 23/11/2007, 22h26
  3. Loi des grands nombres,
    Par kaizer dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 24/09/2007, 14h33
  4. Factorisation grands nombres
    Par Maquessime dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 19/04/2007, 04h42
  5. Calculs avec de grands nombres (congruences, puissances...)
    Par Antikhippe dans le forum Mathématiques du supérieur
    Réponses: 20
    Dernier message: 16/01/2005, 18h43