Division de grands nombres

Question

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

Ombitious_Developper · Answer

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.

yopyoopyop · Answer

Merci d'avance Ombitious =D

z bozzo · Answer

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.

z bozzo · Answer

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.

yopyoopyop · Answer

Effectivement Bozzo, je n'y avais pas pensé... merci bien pour cette astuce xD

cs_jojolemariole · Answer

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.

Division de grands nombres

6 réponses

Votre réponse

Discussions similaires