C#. Длинная арифметика. Урок 1. Чтение и вывод больших чисел

Длинная арифметика   9 февраля 2013  Автор статьи:  

В данной статье мы начнем знакомиться с большими числами. Большие числа — это такие числа, которые без дополнительной обработки не помещаются в базовые типы данных. Например: 123456789012345678901234567890
Очевидно, что это число не поместится ни в int, ни в long. Такие числа очень часто применяются в криптографии. В рамках данного курса мы научимся хранить такие числа и выполнять основные арифметические операции над ними. Сразу хочу сказать, что в C# уже есть классы, которые выполняют схожий функционал, и данный курс рассчитан только на понимание работы длинной арифметики, а не на практическом применении классов из него в дальнейшем.
Теперь перейдем к главному вопросу длинной арифметики — «Как хранить большие числа?». В рамках данного курса мы напишем специальный класс обертку для целых чисел, который будет называться BigInteger. Данный класс будет содержать в себе массив целых чисел, притом большое число в нем будет содержаться следующим образом, сначала будет идти младшие разряды числа, а затем старшие. Это связанно с тем, что число у нас может в дальнейшем увеличиваться, а рост массива происходит в правую сторону. Очевидно, что большие числа мы будем получать скорей всего из строки, поэтому давайте подумаем каким образом мы будем получать из строки массив. Так как мы хотим в каждом элементе массива хранить не один разряд, а желательно побольше, то нам необходимо выбрать базу для длинной арифметике. База — это число по основанию которого мы собираемся проводить арифметические операции в том плане, что в одной ячейке будет хранится определенное количество чисел. Так как мы будем реализовывать большие числа на основе целочисленного типа данных int, то мы будем хранить 8 цифр числа в одной ячейке. Для этого нам достаточно порезать исходную строку по 8 чисел, начиная с конца, если в конце у нас останется меньше 8 то это ничего страшного. На самом деле как бы вы не реализовали эту процедуру в любом случае она будет работать за линейной время. Для того, чтобы вывести число достаточно пройти массив с конца на перед, при этом не забывая там, где нужно дописывать нули, так как очевидно, что лидирующие нули мы не храним. Мою реализацию чтения и вывода больших чисел вы можете увидеть ниже:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LongMathematic
{
public class BigInteger
{
private List arr = new List();//массив который хранит большое числа
private static int order = 8;//база
public BigInteger(string s)
{
int tempValue = 0;//временное значение
int tempOrder = 0;//временный порядок
for (int i = s.Length - 1; i >= 0; i--)
{
if (tempOrder == order)//если число уже нужной длины
{
arr.Add(tempValue);
tempValue = int.Parse(s[i].ToString());
tempOrder = 1;

}
else//если еще меньше базы
{
tempValue = tempValue + (int)Math.Pow(10,tempOrder) * int.Parse(s[i].ToString());
tempOrder++;
}

}
if(tempOrder!=0){//если мы вообще получили не пустую строку
arr.Add(tempValue);//докладываем остаток
}
}
public string ToString()
{
StringBuilder ans = new StringBuilder();
ans.Append(arr[arr.Count - 1].ToString());
for (int i = arr.Count - 2; i >= 0; i--)
{
string temp = arr[i].ToString();
int zeroCount = order - temp.Length;//подсчитываем количество не хватающих нулей
for (int j = 0; j < zeroCount; j++) { ans.Append('0'); } ans.Append(temp); } return ans.ToString(); } } }

  • Евгений

    Никакая статья !!!

    Хранить числo «1» в интовом массиве — это кощунство !!!

    Реализация автора — будет занимать в памяти в четыре раза больше места, чем нужно на самом деле.

    Автор — как ты собираешся умножать свой массив ???

    Попробуй вывести на экран такое:

    List list = new List(new uint[] { 0x3FFFFFFF, 0x00000001 });

    Подсказка — результат должен быть таким: 4611686018158952449.

    • Здравствуй дорогой школьник. Я понимаю твое ужасное возмущение, и в дальнейших статьях будет данная реализация значительно улучшена, но даже в таком виде при смене базы она признана всеми светилами науками как оптимальная, естественно, если ты напишешь умножение на основе сверток, то оно будет чуть побыстрее моей реализации. А вообще если так по хорошему, то сначала читают цикл статей до конца, а потом уже высказывают свое мнение. По крайне мере, я могу гарантировать, что моя длинная арифметика работает быстрее, чем базовая в Java. Ну и наконец отвечу на твои возмущения:
      1)Хранить числo «1» в интовом массиве — это кощунство !!!

      Кто его там хранит никому кроме тебя видимо не понятно.

      2)Автор — как ты собираешся умножать свой массив ??? Как минимум двумя способами, которые описаны в следующих статьях( для перехода на них нужно нажать кнопочку далее внизу этой статьи)

  • Dranked Wizard

    Пойду лучше документы с универа заберу

Научиться программировать

  • на Delphi

  • на Java

  • на C++