Comparer de très grands nombres stockés dans une chaîne

Question

Quelle est la meilleure façon de comparer deux très grands nombres contenus dans des chaînes littérales?

Par exemple, je veux comparer les points suivants: "90000000000000000000000000000000000000000000000000000000000000000000000000001" "100000000000000000000000000000000000000000000000000000000000000000000000000009"

ou

"0000000000111111111111111111111111111111111111111111111111111111111111111111" "0000001111111111111111111111111111111111111111111111111111111111111111111111"

Dans les deux cas, de toute évidence que le second est greate r, mais comment pourrais-je le découvrir efficacement sans itération sur les éléments?

Answer 1

Voici une autre solution:

public static int CompareNumbers(string x, string y) 
    { 
     if (x.Length > y.Length) y = y.PadLeft(x.Length, '0'); 
     else if (y.Length > x.Length) x = x.PadLeft(y.Length, '0'); 

     for (int i = 0; i < x.Length; i++) 
     { 
      if (x[i] < y[i]) return -1; 
      if (x[i] > y[i]) return 1; 
     } 
     return 0; 
    } 

Answer 2

Je prendrais personnellement l'approche la plus simple: utiliser BigInteger pour analyser les deux valeurs et comparer ces résultats. Que ne serait pas être terriblement efficace, mais ce serait très simple - et alors vous pourriez benchmark pour voir si c'est assez assez.

Sinon, vous pouvez trouver la longueur effective en ignorant les zéros en tête - et si un nombre est plus long que l'autre, alors c'est tout ce que vous devez savoir. Ou écrivez une méthode pour obtenir le chiffre "effectif" d'une chaîne qui peut être plus courte, en retournant 0 si nécessaire, puis comparez à partir de la longueur de la chaîne plus longue jusqu'à ce qu'une chaîne donne une valeur plus grande. Quelque chose comme:

// Return the digit as a char to avoid bothering to convert digits to their 
// numeric values. 
private char GetEffectiveDigit(string text, int digitNumber) 
{ 
    int index = text.Length - digitNumber; 
    return index < 0 ? '0' : text[index]; 
} 

private int CompareNumbers(string x, string y) 
{ 
    for (int i = int.Max(x.Length, y.Length); i >= 0; i--) 
    { 
     char xc = GetEffectiveDigit(x, i); 
     char yc = GetEffectiveDigit(y, i); 
     int comparison = xc.CompareTo(yc); 
     if (comparison != 0) 
     { 
      return comparison; 
     } 
    } 
    return 0; 
} 

Notez que cela ne vérifie pas que ce soit un numéro valide du tout, et il ne cherche pas vraiment à manipuler des nombres négatifs.

Answer 3

Si par comparaison vous dire vérifier booléen, cela fonctionne:

public class Program 
{ 
    static void Main(string[] args) 
    { 
     string a = "0000000090000000000000000000000000000000000000000000000000000000000000000000000000001"; 

     string b = "000100000000000000000000000000000000000000000000000000000000000000000000000000009"; 

     Console.WriteLine(FirstIsBigger(a, b)); 

     Console.ReadLine(); 
    } 

    static bool FirstIsBigger(string first, string second) 
    { 
     first = first.TrimStart('0'); 
     second = second.TrimStart('0'); 
     if (first.Length > second.Length) 
     { 
      return true; 
     } 
     else if (second.Length == first.Length) 
     { 
      for (int i = 0; i < first.Length; i++) 
      { 
       double x = char.GetNumericValue(first[i]); 
       double y = char.GetNumericValue(second[i]); 
       if (x > y) return true; 
       else if (x == y) continue; 
       else return false; 
      } 
     } 

     return false; 
    } 
}