Длинная арифметика от Microsoft

    Введение


    Известно, что компьютер может оперировать числами, количество бит которых ограниченно. Как правило, мы привыкли работать с 32-х и 64-х разрядными целыми числами, которым на платформе .NET соответствуют типы Int32 (int) и Int64 (long) соответственно.

    А что делать, если надо представить число, такое как, например, 29! = 8841761993739701954543616000000? Такое число не поместится ни в 64-х разрядный, ни тем более 32-х разрядный тип данных. Именно для работы с такими большими числами существует длинная арифметика.

    Длинная арифметика — в вычислительной технике операции (сложение, умножение, вычитание, деление, возведение в степень и т.д.) над числами, разрядность которых превышает длину машинного слова данной вычислительной машины. Эти операции реализуются не аппаратно, а программно, используя базовые аппаратные средства работы с числами меньших порядков.

    Длинную арифметику также можно считать одним из разделов олимпиадного программирования, поскольку очень часто при решении задач, разрядности стандартных типов не хватает для представления конечного результата. При выборе языка программирования для олимпиадных нужд не маловажным является встроенный в него набор средств (готовых библиотек, реализованных классов). Многие языки (Java, Ruby, Python) имеют встроенную поддержку длинной арифметики, что в разы может сократить время написания программы.

    Платформа .NET вплоть до 4.0 версии не имела встроенной поддержки работы с длинными числами. В 4-той же версии .NET обзавелась не только длинными, но и комплексными числами. Этот функционал доступен через сборку System.Numerics и типы BigInteger и Complex определенные в одноимённом с названием сборки пространстве имён.

    Следует сказать, что структура BigInteger должна была появиться ещё в .NET 3.5, однако на тот момент она не была полностью готова, её реализация не отвечала всем потребностям (сюда можно отнести и проблемы производительности), поэтому было принято решение отложить её выход до .NET 4.0.

    В данной статье я бы хотел рассмотреть подробности реализации длинной арифметики от Microsoft.

    Общие понятия


    Идея представления длинных чисел в памяти компьютера достаточно проста. Рассмотрим число 123456789 в десятеричной системе счисления. Очевидно, его можно представить следующим образом:

    12345678910 = 1*108 + 2*107 + 3*106 + 4*105 + 5*104 + 6*103 + 7*102 + 8*101 + 9*100

    В общем случае, любое число можно представить в виде:

    A = an-1βn-1 + an-2βn-2 +…+a1β + a0
    где β – основание системы счисления, в которой мы представляем число, а коэффициенты ai удовлетворяют двойному неравенству 0 ≤ ai < β.

    Представление числа напоминает представление многочлена, только вместо x в соответствующей степени имеем основание β в нужной степени. Как известно, многочлен a0 + a1x + a2x2 + … + anxn удобно представлять в виде массива, элементы которого представляют коэффициенты ai, а индекс i — определяет соответствующую степень x. Длинное число хранится аналогично, осталось определиться с выбором основания β.

    Например, то же самое число 123456789 можно представить в десятитысячной (β = 104) системе счисления следующим образом:

    12345678910 = 1*(104)2 + 2345*(104)1 + 6789*(104)0

    Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества: во-первых, сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789), во-вторых, значительно уменьшаем время выполнения стандартных операций над длинными числами, поскольку за раз обрабатываем 4 разряда числа. В общем, компьютер одинаково быстро складывает одноразрядные и 32-разрядные числа, поэтому этим следует воспользоваться.

    Основание системы счисления β обычно зависит от максимального размера базового типа данных на компьютере, и выбирается, исходя из следующих соображений:

    1. основание должно подходить под один из базовых типов данных;
    2. основание должно быть как можно больше, чтобы уменьшить размер представления длинного числа и увеличить скорость операций с ними, но достаточно малого размера, чтобы все операции с коэффициентами использовали базовый тип данных;
    3. для удобства вывода и отладки можно выбрать β как степень 10, β — степень двойки позволяет проводить быстрые операции на низком уровне.

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

    BigInteger от Microsoft


    Если посмотреть на структуру BigInteger через декомпилятор Reflector или dotPeek, то увидим следующие поля:

    private static readonly BigInteger s_bnMinInt = new BigInteger(-1, new uint[1]{ (uint) int.MinValue });
    private static readonly BigInteger s_bnOneInt = new BigInteger(1);
    private static readonly BigInteger s_bnZeroInt = new BigInteger(0);
    private static readonly BigInteger s_bnMinusOneInt = new BigInteger(-1);
    internal int _sign;
    internal uint[] _bits;
    private const int knMaskHighBit = -2147483648;
    private const uint kuMaskHighBit = 2147483648U;
    private const int kcbitUint = 32;
    private const int kcbitUlong = 64;
    private const int DecimalScaleFactorMask = 16711680;
    private const int DecimalSignMask = -2147483648;
    

    Структура содержит всего два экземплярных поля (_sign и _bits), остальные поля представляют собой константы и статические поля для чтения представляющие значения структуры для чисел -1, 0 и 1.

    Можно предположить, что в переменной _sign хранится знак числа, а массив _bits содержит коэффициенты ai. Учитывая, что массив _bits имеет тип uint[], можно так же предположить, что в качестве основания β взята степень двойки 232 (поскольку uint — 32 разрядное беззнаковое число).

    Итак, попробуем подтвердить или опровергнуть наши предположения.

    Конструктор, принимающий int, в качестве аргумента выглядит так:

    Конструктор принимающий int
    public BigInteger(int value)
     {
       if (value == int.MinValue)
       {
         this = BigInteger.s_bnMinInt;
       }
       else
       {
         this._sign = value;
         this._bits = (uint[]) null;
       }
     }
    

    Его реализация может рассказать немного больше о назначении переменной _sign. Как видно, если длинное число помещается в int диапазон (от -231 до 231-1), то оно хранится в переменной _sign, а массив _bits при этом не используется, он равен null. Эта оптимизация, должна ускорить работу типа BigInteger, а так же снизить размер потребляемой памяти когда число на самом деле не является большим.

    Идем дальше.

    Конструктор, принимающий uint в качестве аргумента, выглядит следующим образом:

    Конструктор принимающий uint
    public BigInteger(uint value)
     {
       if (value <= (uint) int.MaxValue)
       {
         this._sign = (int) value;
         this._bits = (uint[]) null;
       }
       else
       {
         this._sign = 1;
         this._bits = new uint[1];
         this._bits[0] = value;
       }
     }
    

    В зависимости от того помещается ли число в int диапазон, оно записывается либо в переменную _sign, либо в массив _bits.

    Следующий конструктор, принимающий 64-х разрядное число со знаком (long) поможет ответить на вопрос о выборе основания системы счисления:

    Конструктор принимающий long
    public BigInteger(long value)
     {
       if ((long) int.MinValue <= value && value <= (long) int.MaxValue)
       {
         if (value == (long) int.MinValue)
         {
           this = BigInteger.s_bnMinInt;
         }
         else
         {
           this._sign = (int) value;
           this._bits = (uint[]) null;
         }
       }
       else
       {
         ulong num;
           if (value < 0L)
           {
             num = (ulong) -value;
             this._sign = -1;
            }
           else
            {
             num = (ulong) value;
             this._sign = 1;
            }
           this._bits = new uint[2];
           this._bits[0] = (uint) num;
           this._bits[1] = (uint) (num >> 32);
       }
     }
    

    Если число не помещается в int диапазон, то, как мы видим переменная _sign содержит знак числа (-1 – для отрицательного и 1 – для положительного), а массив _bits содержит те самые коэффициенты ai и заполняется следующим образом:

    this._bits = new uint[2];
    this._bits[0] = (uint) num;
    this._bits[1] = (uint) (num >> 32);
    

    В данном случае 64-х разрядное число num разбивается на два 32-х разрядных: (uint)num и (uint)(num >> 32). Первое число представляет собой последние 32 бита числа num, в то время как второе первые 32 бита (смещение вправо на n бит равносильно целочисленному делению на 2n).

    Давайте определим, как будет храниться число long.MaxValue = 263-1 = 9223372036854775807 в структуре BigInteger. Для этого поделим его на 232:


    Фактически (uint)long.MaxValue = 4294967295, (uint)(long.MaxValue >> 32) = 2147483647.

    Значит, 9223372036854775807 = 2147483647*(232)1 + 4294967295*(232)0, и BigInteger
    будет представлен парой:

    _sign = 1
    _bits = {4294967295, 2147483647} // вспоминаем, что число храниться задом наперёд


    Для длинного числа -1234567891011121314151617181920 имеем:



    То есть число раскладывается по степеням 232 следующим образом:
    1234567891011121314151617181920 = 15*(232)3 + 2501550035*(232)2 + 3243814879*(232)1 + 4035623136*(232)0

    Значит, BigInteger будет представлен парой:

    _sign = -1 // знак числа
    _bits = {4035623136, 3243814879, 2501550035, 15}


    Число, помещающееся в int диапазон, скажем, 17 будет храниться следующим образом:

    _sign = 17
    _bits = null


    Исследовав конструкторы структуры BigInteger можно заключить:

    1. если число помещается в int диапазон, то оно хранится в переменной _sign;
    2. если число не помещается в int диапазон, то его знак хранится в переменной _sign (-1 – для отрицательного и 1 – для положительного), а массив _bits содержит коэффициенты ai разложения длинного числа с основанием 232.
    Основание β = 232, является неплохим выбором, поскольку со степенью двойки легче работать на низком уровне (умножение и деление на степень двойки соответствует битовым сдвигам влево и вправо), а так же за раз будут обрабатываться целых 32 разрядов числа, что позволяет достаточно быстро совершать операции над ними.

    В общем, структура BigInteger является полноценной реализацией длинной арифметики на платформе .NET. При этом Microsoft постаралась максимально близко приблизить её к примитивным числовым типам: экземпляр BigInteger можно использовать точно так же, как и любой другой целочисленный тип. BigInteger перегружает стандартные числовые операторы для выполнения основных математических операций, таких как сложение, вычитание, деление, умножение, вычитания, отрицание и унарное отрицание. Можно также использовать стандартные числовые операторы для сравнения двух значений BigInteger друг с другом. Как и другие типы целого числа, BigInteger поддерживает битовые операторы And, Or, XOR, сдвиг влево и сдвиг вправо.

    Для языков, не поддерживающих пользовательские операторы, структура BigInteger также предоставляет эквивалентные методы для выполнения математических операций. Это относится к методам Add, Divide, Multiply, Negate, Subtract и некоторым другим. Точно так же Microsoft поступило в реализации структуры Decimal.

    Многие члены структуры BigInteger напрямую соответствуют членам других целых типов. Кроме того, BigInteger добавляет такие элементы как:

    • IsEven – определяет является ли число чётным;
    • IsPowerOfTwo — определяет является ли число степенью двойки;
    • Sign — возвращает значение, указывающее знак числа BigInteger;
    • Abs — возвращает абсолютное значение числа BigInteger;
    • DivRem — возвращает частное и остаток от операции деления;
    • GreatestCommonDivisor — возвращает наибольший общий делитель для двух чисел;
    • Log — возвращает логарифм указанного числа в системе счисления с указанным основанием;
    • Max / Min — возвращает наибольшее / наименьшее из двух чисел;
    • ModPow — выполняет модульное деление числа, возведенного в степень другого числа;
    • Pow — возводит значение BigInteger в заданную степень.

    Пару слов о BigInteger в Mono и Java


    Следует отметить, что Mono так же обладает поддержкой длинной арифметики. Реализация структуры BigInteger в Mono практически ничем не отличается от реализации Microsoft, кроме как, того что в ней нет оптимизации для чисел представимых типом int.

    То есть число 17 в Mono будет представлено парой:

    _sign = 1 // знак числа
    _bits = {17}


    Аналогичная реализация BigInteger представлена в Java:

    public class BigInteger extends Number implements Comparable<BigInteger> 
     {
       int signum;
       int[] mag;
       private int bitCount = -1;
       private int bitLength = -1;
       private int lowestSetBit = -2;
       private int firstNonzeroByteNum = -2;
       private int firstNonzeroIntNum = -2;
       private final static long LONG_MASK = 0xffffffffL;
     }
    

    Поскольку в Java отсутствуют беззнаковые типы, то массив mag имеет тип int[]. Соответственно представления длинного числа в Java и .NET будут отличаться. В .NET представление будет немного эффективнее, поскольку тип uint охватывает больший диапазон:

    Конструктор принимающий long
    private BigInteger(long val) 
     {
        if (val < 0) {
          signum = -1;
           val = -val;
         } 
        else {
           signum = 1;
         }
        int highWord = (int)(val >>> 32);
        if (highWord == 0) {
            mag = new int[1];
            mag[0] = (int)val;
           } 
        else {
            mag = new int[2];
            mag[0] = highWord;
            mag[1] = (int)val;
           }
     }
    

    В Java, так же как и в Mono нет оптимизации для чисел, представимых типом int.

    Производительность BigInteger


    Работая с длинным числом BigInteger, необходимо помнить о возможных проблемах связанных с производительностью. Например, казалось бы, безобидный оператор ++ может оказать существенное влияние на производительность:

    int length = 1000000;
    BigInteger num = BigInteger.Parse("12345678910111213141516171819");
    for (int i = 2; i < length; i++)
     {
       if (IsPrime(i))
          num++;
     }
    Console.WriteLine(num); 
    

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

    В данном примере, можно поступить следующим образом: выполнить промежуточные операции, используя обычные числовые типы, а затем использовать BigInteger:

    int length = 1000000;
    BigInteger num = BigInteger.Parse("12345678910111213141516171819");
    int temp = 0;
    for (int i = 2; i < length; i++)
     {
       if (IsPrime(i))
          temp++;
     }
     num += temp;
     Console.WriteLine(num);
    

    Другие числовые типы .NET Framework также являются неизменяемыми. Однако поскольку тип BigInteger не имеет верхней или нижней границы, его значения могут расти до очень больших значений и иметь измеримое влияние на производительность.

    Вместо заключения


    Подводя итог, можно сказать, что платформа .NET, начиная с 4 версии, обзавелась полноценной реализацией целочисленной длинной арифметики. Возможно, для полного счастья осталось реализовать структуру BigRational, которая уже достаточно давно присутствует в статусе бета в .NET BCL.

    Описание структуры BigRational: структура BigRational основывается на типе BigInteger, который был представлен в .NET Framework 4 и позволяет создавать рациональные числа произвольной точности. Рациональное число представляет собой отношение двух целых чисел, и в этой реализации структуры BigRational в качестве делимого (числителя) и делителя (знаменателя) используется тип BigInteger.

    За замечание спасибо пользователям: gouranga
    Метки:
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 33
    • +1
      Следует сказать, что структура BigInteger появилась ещё в .NET 3.5, но была определена как internal
      • 0
        Эх, как еще в дотнете 1.1 не хватало жавовских BigInteger и BigDecimal… И вот счастье наступило только в 4й версии, да и то не полное.

        А BigDecimal::setScale () и сейчас не хватает настолько что я его из жавы утащил.
        • 0
          А что за ::? Немного С++ кагбэ напоминает :)
          • +1
            Или вы тот редкий зверь, который на С++ CLI пишет? О_о
            • +7
              С++ нотация в таких случаях самая однозначная, AFAIR.
          • +2
            >> Эх, как еще в дотнете 1.1 не хватало жавовских BigInteger и BigDecimal…

            Все-таки большинство целей, для которых в Java использовался BigDecimal (работа с деньгами и прочие моменты, где нужна десятичная арифметика без неявной потери точности), в .NET успешно покрывались обычным decimal — который при этом намного быстрее.
          • +3
            А ничего, что два куска кода в конце делают разные вещи? Один всё время проверяет одно и тоже число на IsPrime, другой по сути ищет первый не prime и дальше критит цикл в холостую? Или я что-то не понимаю?
            • +1
              Подправил, опечаточка с параметром метода IsPrime вышла.
            • +1
              Для примера со системой счисления с основанием 104 будет всё-таки так:
              12345678910 = 1*(104)2 + 2345*(104)1 + 6789*(104)0
              • 0
                Да действительно. Исправил.
                • 0
                  И всё-таки правильно так: 123456789104
                • 0
                  За какую сложность в .NET-ной реализаии BigInteger происходит умножение, деление длинного на длинное, взятие по модулю, вывод числа (который требует перевода в десятичную систему счисления)?
                  • 0
                    Здесь пишут, что для умножения используется алгоритм Карацубы, который работает за O(n^(log(2,3)))
                    Для сложения используется линейный алгоритм
                    • 0
                      Уж не знаю, что там пишут, но по судя по ILSpy, в .NET используется обычный алгоритм перемножения:

                      Код перемножения больших чисел в .NET
                      public static BigInteger operator *(BigInteger left, BigInteger right)
                      {
                      	int sign = 1;
                      	BigIntegerBuilder bigIntegerBuilder = new BigIntegerBuilder(left, ref sign);
                      	BigIntegerBuilder bigIntegerBuilder2 = new BigIntegerBuilder(right, ref sign);
                      	bigIntegerBuilder.Mul(ref bigIntegerBuilder2);
                      	return bigIntegerBuilder.GetInteger(sign);
                      }
                      
                      ...
                      
                      public void Mul(ref BigIntegerBuilder regMul)
                      {
                      	if (regMul._iuLast == 0)
                      	{
                      		this.Mul(regMul._uSmall);
                      		return;
                      	}
                      	if (this._iuLast == 0)
                      	{
                      		uint uSmall = this._uSmall;
                      		if (uSmall == 1u)
                      		{
                      			this = new BigIntegerBuilder(ref regMul);
                      			return;
                      		}
                      		if (uSmall != 0u)
                      		{
                      			this.Load(ref regMul, 1);
                      			this.Mul(uSmall);
                      			return;
                      		}
                      	}
                      	else
                      	{
                      		int num = this._iuLast + 1;
                      		this.SetSizeKeep(num + regMul._iuLast, 1);
                      		int num2 = num;
                      		while (--num2 >= 0)
                      		{
                      			uint uMul = this._rgu[num2];
                      			this._rgu[num2] = 0u;
                      			uint num3 = 0u;
                      			for (int i = 0; i <= regMul._iuLast; i++)
                      			{
                      				num3 = BigIntegerBuilder.AddMulCarry(ref this._rgu[num2 + i], regMul._rgu[i], uMul, num3);
                      			}
                      			if (num3 != 0u)
                      			{
                      				int num4 = num2 + regMul._iuLast + 1;
                      				while (num3 != 0u && num4 <= this._iuLast)
                      				{
                      					num3 = BigIntegerBuilder.AddCarry(ref this._rgu[num4], 0u, num3);
                      					num4++;
                      				}
                      				if (num3 != 0u)
                      				{
                      					this.SetSizeKeep(this._iuLast + 2, 0);
                      					this._rgu[this._iuLast] = num3;
                      				}
                      			}
                      		}
                      	}
                      }
                      
                      ...
                      
                      private static uint AddMulCarry(ref uint uAdd, uint uMul1, uint uMul2, uint uCarry)
                      {
                      	ulong num = (ulong)uMul1 * (ulong)uMul2 + (ulong)uAdd + (ulong)uCarry;
                      	uAdd = (uint)num;
                      	return (uint)(num >> 32);
                      }
                      

                      • +1
                        Действительно в классической версии .NET'a используется простое перемножение(кстати, вместо ILSpy удобно пользоваться исходниками .NET'а, их можно найти здесь)

                        Однако, если заглянуть в исходники CoreFX, то здесь уже, похоже, используется более продвинутый алгоритм, я думаю это какая-то модификация алгоритма Карацубы.
                        Здесь можно найти обсуждение.
                    • –3
                      1. По поводу взятия модуля все просто: поскольку знак хранится в отдельной переменной то получить модуль ничего не стоит (необходимо только сравнение с нулем).

                      public static BigInteger Abs(BigInteger value)
                      {
                      if (!(value >= BigInteger.Zero))
                      return -value;
                      else
                      return value;
                      }

                      2. Метод ToString, который представляет число в десятичной системе счисления для вывода, должен обработать весь массив _bits длинна которого равна [log232X] = [32*log2X], где X — длинное число. Получается, метод ToString работает за логарифмическое время от длинны числа.

                      3. Умножение и деление (как я понял) выполняется обычным способом в столбик, который занимает O(n2) времени. Однако поскольку мы обрабатываем за раз целых 232 разрядов, получаем сложность перемножения/деления равную O(log2n). Хотя возможно используется алгоритм Карацубы.
                      • 0
                        1. Взятие по модулю в смысле взятия остатка от деления.

                        2. > логарифмическое время от длинны числа.
                        Вы, вероятно, имели в виду логарифмическое время от самого числа (т. е. линейное по его длине).

                        Так вот, это очень сомнительно, потому что нельзя перевести число в двоичной системе в десятичную, просто по отдельности обработав биты его записи. Чтобы сделать это в тупую, надо его школьным алгоритмом делить каждый раз на 10 и выписывать остаток от деления как очередной разряд, то есть время будет квадратичным по длине числа. Более того, в Java-реализации длинной арифметики вывод числа это одна из самых трудоёмких операций именно потому, что реализована за квадрат (насколько я знаю).

                        3. > обрабатываем за раз целых 232 разрядов
                        > получаем сложность перемножения/деления равную O(log2n).
                        Опять же, что-то у вас смешались в кучу кони и люди. Мы, всё-таки, за раз обрабатываем 32 разряда, и это никак не повлияет на сложность, которая по-прежнему останется квадратичной.

                        Казалось бы, если у вас есть возможность посмотреть на код реализации умножения, очень легко понять, алгоритм ли это Карацубы или квадратичный.
                    • +1
                      В основных реализациях Smalltalk класс BigInteger присутствует уже лет 20 как… Причём результат выполнения арифм. операций, могущих вызвать переполнение, сам приводится к корректному типу, освобождая голову программисту более важным вещам.

                      Воистину, история развивается по спирали ))
                      • 0
                        Вообще-то unchecked переполнение (когда, например, 255 превращается в 0) может использоваться и для написания более производительного кода. Так что не все так просто :)
                      • +3
                        Давайте определим, как будет храниться число long.MaxValue = 263-1 = 9223372036854775807 в структуре BigInteger. Для этого поделим его на 232:

                        Как сложно написано, а на самом деле всё проще ведь:
                        9223372036854775807 = 0x7FFFFFFFFFFFFFFF, хранится как {0xFFFFffff, 0x7FFFfff}
                        • 0
                          Кстати, гораздо интереснее случай с минимальным long-ом чем с максимальным.

                                 ulong num;
                                 if (value < 0L)
                                 {
                                   num = (ulong) -value;
                                   this._sign = -1;
                                  }
                          
                          


                          Вот тут похоже что -value вычисляется сначала в знаковом типе, и происходит переполнение, а потом приводится к беззнаковому. В C# гарантируется, что результат будет всегда правильный в этом случае?
                          • 0
                            long i = long.MaxValue;
                            long i1 = i + 1; // i1 = long.MinValue

                            В данном коде происходит переполнение типа long, а поскольку нет соответствующих проверок на переполнение (checked), то вместо выброса исключения произойдет приведение к типу long. В результате переполнения переменная i1 будет содержать значение long.MinValue.

                            В случае если value = long.MinValue, -value = long.MaxValue + 1 = long.MinValue.

                            Это так же можно связать с тем, что для long.MinValue = -263 = 100000...000 противоположное число будет совпадать с самим числом, поскольку дополнительные коды совпадают:
                            100000...000

                            011111...111 инвертирование
                            000000...001 +1
                            __________
                            100000...000 дополнительный код для 100000...000
                            • +1
                              Да, это все понятно. Мой вопрос был скорее про то, что ведь .NET заявляется как кросс-платформенный, а это поведение завязано на платформо-зависимое поведение при переполнении и приведении типов. Отсюда был вопрос — в .NET гарантируется что (ulong) -2^63 = 2^63?
                              • 0
                                Не совсем понятно, где здесь платформо-зависимое поведение? Насколько я помню всю работу за соблюдение приведения типов и переполнение .NET берет на себя и не полагается в этом случае на платформу на которой он работает. Хотя я возможно могу ошибаться.
                                • +1
                                  Ну потому что не на всякой платформе отрицательные числа хранятся в дополнительном коде. Но я уже нашел на MSDN, что в .NET такое представление похоже что гарантируется:
                                  Int32 values are represented in 31 bits, with the thirty-second bit used as a sign bit. Positive values are represented by using sign-and-magnitude representation. Negative values are in two's complement representation.
                                  • 0
                                    Прошу прощения, а вы можете назвать пару платформ, где используется не дополнительный код?
                                    • 0
                                      Я думаю что сегодня найти такую будет не очень просто. Я спрашивал с теоретической точки зрения.

                                      Вот тут на вопрос почему кто-то еще беспокоится о платформах со странными особенностями (там правда не спрашивали про дополнительный код) в первом ответе приводят старую платформу, где не только числа представлены в обратном (а не в дополнительном) коде, но еще и размер одного байта равен 9 битам.
                                      • 0
                                        Просто я не уверен, что все еще есть хоть какой-то смысл заботиться о возможности работы на такой платформе.
                        • –3
                          > Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества: во-первых, сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789), во-вторых, значительно уменьшаем время выполнения стандартных операций над длинными числами, поскольку за раз обрабатываем 4 разряда числа.

                          ЛОЛШТО?!

                          ЗЫ. Еще П. Нортон в своей знаменитой Assembly Language for IBM PC в качестве разминки и закрепления материала показывал, как реализовать калькулятор, оперирующий десятичной целочисленной арифметикой без ограничения на разрядность чисел. 1986 год. А вы тут про дотнет. :D
                          • 0
                            Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества: во-первых, сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789)

                            Это неверно. Теоретически объём памяти не изменяется, так как мы в обоих случаях используем безизбыточные системы счисления и информацию никоим образом не сжимаем и тем более не теряем. Это всего лишь изменение основания.
                            Например, для передачи 256-значного символа требуются восьмибитовые кодовые слова (байты). Представляя 256-значный символ в шестнадцатеричной системе счисления, получим, что потребуется два символа по 4 бита, то есть тот же байт.
                            log(256)/log(16)*log2(16) = log(256)/log(2)*log2(2) => log(M)/log(N1)*log2(N1) = log(M)/log(N2)*log2(N2).
                            При практической реализации возможны некоторые дробления, так как ячейки памяти удобно бить на байты.
                            • 0
                              Стоит отметить, что под .NET также есть библиотека IntXLib, в которой используется дискретное преобразование Хартли для эффективной реализации операций с большими числами (временная сложность O(N * log N * log log N)). Автор провел тесты производительности по сравнению со стандартной реализацией (у него быстрее).
                              • 0
                                А существуют ли библиотеки для работы с большими числами с плавающей точкой? Ну чтобы, например, считать sin с произвольной точностью?
                                • 0
                                  Где вы взяли эту странную языковую конструкцию?
                                  ModPow — выполняет модульное деление числа, возведенного в степень другого числа

                                  ModPow — это операция "возведение в степень по модулю".

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