более простой большой сумматор в C#?

Question

У меня была задача в школе написать большой сумматор. Это метод, который может сочетать очень большие числа. У нас было 10 минут, и я сделал это вовремя. Учитель одобрил это.

Я не слишком доволен результатом, хотя, и я думал, что, возможно, ошибаюсь.

Вот моя версия:

using System; 
using System.Text; 

namespace kæmpe_adder 
{ 
    static class Program 
    { 
     static void Main() 
     { 
      var x = "1111"; 
      var y = "111111111"; 

      Console.WriteLine(BigAdder(x, y)); 
      Console.ReadLine(); 
     } 
     public static StringBuilder BigAdder(string x, string y) 
     { 
      var a = new StringBuilder(x); 
      var b = new StringBuilder(y); 
      return BigAdder(a, b); 
     } 
     public static StringBuilder BigAdder(StringBuilder x, StringBuilder y) 
     { 
      int biggest; 
      int carry = 0; 
      int sum; 
      var stringSum = new StringBuilder(); 

      if (x.Length > y.Length) 
      { 
       y.FillString(x.Length - y.Length); 
       biggest = x.Length; 
      } 
      else if (y.Length > x.Length) 
      { 
       x.FillString(y.Length - x.Length); 
       biggest = y.Length; 
      } 
      else 
      { 
       biggest = y.Length; 
      } 

      for (int i = biggest - 1; i >= 0; i--) 
      { 
       sum = Convert.ToInt32(x[i].ToString()) + Convert.ToInt32(y[i].ToString()) + carry; 
       carry = sum/10; 
       stringSum.Insert(0, sum % 10); 
      } 

      if (carry != 0) 
      { 
       stringSum.Insert(0, carry); 
      } 

      return stringSum; 
     } 
     public static void FillString(this StringBuilder str, int max) 
     { 
      for (int i = 0; i < max; i++) 
      { 
       str.Insert(0, "0"); 
      } 
     } 
    } 
} 

Когда я писал это, я подумал о том, как вы делаете это с двоичными файлами.

Есть ли более короткий и/или, возможно, более простой способ сделать это?

Answer 1

С алгебраической точки зрения ваш код выглядит правильно. С точки зрения дизайна вы определенно предпочтете инкапсулировать каждое из этих больших чисел в классе, чтобы вам не приходилось ссылаться на строковые/строковые сборщики все время. Я также не большой поклонник этого подхода FillString, кажется разумнее добавить цифры, в то время как оба числа имеют ненулевые значения, а затем просто добавьте перенос на большее число, пока вы не закончите.

Не знаете, в чем вопрос о бинарниках? Номера нормальной длины (32 бит и 64 бит) добавляются ЦП в виде одной операции.

Answer 2

Существует множество реализаций с открытым исходным кодом, которые вы можете использовать для вдохновения.

http://www.codeproject.com/KB/cs/biginteger.aspx

http://biginteger.codeplex.com/

В общем, я бы рекомендовал использовать массив байт или долго для лучшей производительности, но преобразование из строки в массив будет нетривиальным.

Сохраните номера в обратном порядке; это делает поиск эквивалентных мест тривиальным.

Это облегчает добавление разного размера струне номера:

int place = 0; 
int carry = 0; 

while (place < shorter.Length) { 
    result.Append (AddDigits (longer[place], shorter[place], ref carry)); 
    ++place; 
} 

while (place < longer.Length) { 
    result.Append (AddDigits (longer[place], 0, ref carry)); 
    ++place; 
} 

if (carry != 0) 
    result.Append (carry.ToString());