Как сравнить большие целые числа, хранящиеся в массиве int?

Question

Я пытаюсь реализовать класс BigInteger в C#. Прямо сейчас я застрял в методе isLessThan(HugeInteger b). Это мой класс и соответствующие методы.

class HugeInteger 
{ 
    public int[] array = new int[40]; 

    public HugeInteger(String s) 
    { 
     this.input(s); 
    } // end constructor 

    /*To read a huge integer having upto 40 digits, I am using an integer array to store 
     these values(input is read as a string for this matter) and later on will override 
     ToString() for output if needed.*/ 
    private void input(String s) 
    { 
     char[] charInteger = s.ToCharArray(); 
     int index = 0; 
     for (int i = 0; i <= 39 - charInteger.Length; i++) 
     { 
      array[i] = 0; 
     } 
     for (int i = 39 - charInteger.Length + 1; i <= 39; i++) 
     { 

      array[i] = int.Parse(charInteger[index].ToString()); 
      index++; 
     } 
    } 

    public bool isLessThan(HugeInteger that) 
    { 

     for (int i = 0; i <= 39; i++) 
     { 
      if (this.array[i] < that.array[i]) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 
} 

В принципе, у меня есть 40 цифр, хранящихся в целочисленном массиве для каждого объекта HugeInteger. Но я точно знаю, что мой метод isLessThan(HugeInteger b) ошибочен и что есть что-то простое, что я пропускаю. Итак, как мне нужно сделать правильный метод isLessthan(HugeInteger b)?

Edit: Мой метод isLessThan не работает в некоторых случаях, как, если я попытаюсь сравнить «9873» и «75», я получаю true, но мне нужно false. Извините за то, что я не понимаю.

Примечание: Я вставляю свои входы (например, 9873 или 75) в виде строки, а затем анализирую их на int в моем методе input, а затем сохраняю их в целочисленном массиве.

Answer 1

ОК, давайте реализуем сравнения; типичный способ использует универсальное сравнение (в некоторых языках это даже имеет специальный оператор <=>)

class HugeInteger { 
    ... 

    // Universal comparator 
    // +1 left > right 
    // 0 left == right 
    // -1 left < right 
    public static int Compare(HugeInteger left, HugeInteger right) { 
     // first, we should deal with null's; let null be the leaset possible value 

     // left and right are just the references of one inctance? 
     if (Object.ReferenceEquals(left, right)) 
     return 0; 
     else if (left == null) 
     return -1; 
     else if (right == null) 
     return 1; 

     // Now we checked for null, let's compare both arrays 

     //DONE: no 39, 40 or other magic numbers, but Length 
     for (int i = 0; i < left.array.Length; ++i) 
     if (left.array[i] < right.array[i]) 
      return -1; 
     else if (left.array[i] > right.array[i]) 
      return 1; 

     return 0; // no differences found, so left equals to right 
    } 

Имея компаратор реализован очень легко написать isLessThan, isGreaterThan:

public bool isLessThan(HugeInteger other) { 
     return Compare(this, other) < 0; 
    } 

    public bool isGreaterThan(HugeInteger other) { 
     return Compare(this, other) > 0; 
    } 
    .... 

Answer 2

Вот как вы можете исправить ваш метод

public bool isLessThan(HugeInteger that) 
{ 
    for (int i = 0; i <= 39; i++) 
    { 
     if (this.array[i] < that.array[i]) 
     { 
      return true; 
     } 
     if (this.array[i] > that.array[i]) 
     { 
      return false; 
     } 
    } 
    return false; 
} 

В принципе, если сравнивать цифры, если они не равны, то вы знаете, если один больше или меньше, чем другие. Вы продолжаете, только если они равны. То, что у вас сейчас есть, - это проверить, есть ли по крайней мере одна соответствующая цифра в первом номере, которое меньше второго. Так что для 9873 и 75 это правда, потому что 3 < 5. Где, как с моим изменением, оно вернет false, как только оно сравнится 9 и 0.

Answer 3

При переполнении понесены, коды условий процессора устанавливаются так, что последующая инструкция может НЕИСПРАВИТЬ, чтобы доставить правильный результат, поэтому вся ваша фантастическая логика ничтожно, если вы не прогнозируете переполнения до того, как они произойдут.

(Вы не можете обнаружить переполнение: если я спрошу, например,

если (MUCHTOOLARGENUMBER> SOMEREASONABLEVALUE) {

я нет никакой гарантии, каким образом тест будет оценивать.)