Division de grands nombres

Signaler
Messages postés
6
Date d'inscription
lundi 8 octobre 2007
Statut
Membre
Dernière intervention
11 novembre 2007
-
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
-
Bonjour à tous,
J'ai besoin de trouver un algorithme mieux optimisé pour pouvoir diviser un nombre par un autre. Les nombres sont contenu dans des tableaux où chaque cellule contient un chiffre (ex.: 123 =
{1,2,3}). Voici le mien, qui est vraiment très lent... :


public static int[] hugeDiv(int []n1 , int[] n2 ){

    int[]zero = new int[1];
    zero[0]=0;
    int[] un = new int[1];
    un[0]=1;
    if(isEqual(n1,n2) == true) return un;
    if(isSmaller(n1,n2) == true) return zero;

    int[] resultat = new int[n1.length];
    int[] tmp;
    int[] n2foisj;

    for(int i=0;i<resultat.length;i++){
        n2foisj = hugeCopy(zero);
        tmp = hugeGetPart(n1,i+1);
        for(int j=0;isSmaller(n2foisj,tmp)==true;j++){
            resultat[i] = j;
            n2foisj = hugeMultDigit(n2,j+1);
            if(n2foisj==null) n2foisj = hugeCopy(zero);
        }
        resultat[i] = resultat[i]%10;
        tmp = hugeSub(tmp,n2foisj);
    }
    return resultat;

}

toutes les autres fonctions marchent impécablement(hugeMult=*,hugeSub=-,hugeGetPart([],i)=retourne les i premiers digits du tableau []).

Merci d'Avance =D

6 réponses

Messages postés
2333
Date d'inscription
samedi 28 février 2004
Statut
Membre
Dernière intervention
26 juillet 2013
34
Salut:

Je me rappelle dans mes études en particulier la matière d'architecture des microprocesseurs il y a plusieurs alogorithmes pour faire la division et les autres opérations arithmétiques.

Cherches l'algorithme qui te convient.
Messages postés
6
Date d'inscription
lundi 8 octobre 2007
Statut
Membre
Dernière intervention
11 novembre 2007

Merci d'avance Ombitious =D
Messages postés
34
Date d'inscription
lundi 19 mars 2007
Statut
Membre
Dernière intervention
15 novembre 2007

Salut,

tu devrais convertir tes nombres en hexadecimal et en suite faire ta division, ca devrai pouvoir accelerer ton algo

<hr size="2" width="100%" />

  .oO BOZZO Oo.
Messages postés
34
Date d'inscription
lundi 19 mars 2007
Statut
Membre
Dernière intervention
15 novembre 2007

re-Salut,

sinon :

123456789987654321        123456789                                     987654321
------------------------- = ---------------- * 1000000000  + -------------------
98765421                             98765421                                      98765421

et ainsi de suite ...

avec cette methode tu peut découper tes nombres de maniere a laisser le circuit de calcul du proccesseur faire les divisions et ensuite faire les multiplications et additions pour trouver ton resutat.

       256      2                 5               6ex : ----- --- * 100 + --- * 10 + --- 40 + 10 + 0.11 = 51.2
         5        5                 5               5

<hr size ="2" width="100%" />

  .oO BOZZO Oo.
Messages postés
6
Date d'inscription
lundi 8 octobre 2007
Statut
Membre
Dernière intervention
11 novembre 2007

Effectivement Bozzo, je n'y avais pas pensé... merci bien pour cette astuce xD
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
21
Sinon, pour info, il existe les BigInteger, qui fonctionnent très bien.

division entiere :
BigInteger a = new BigInteger("123456789123456789123456789123456789");
BigInteger b = new BigInteger("123456789123456789123456789123456789");
BigInteger c = a.divide(b);


division avec reste :

BigInteger a = new BigInteger("123456789123456789123456789123456789");

BigInteger b = new BigInteger("123456789123456789123456789123456789");
BigInteger[] result = a.divideAndRemainder(b);
BigInteger d = result[0];
BigInteger r = result[1];



Cependant je doute qu'ils soient extrêmement optimisés, en particulier ils sont immuables, comme les String.