Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 17.06.2014 | нет комментариев

Вступление

Вестимо, что компьютер может оперировать числами, число бит которых ограниченно. Как правило, мы привыкли трудиться с 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-1mk!>Конструктор принимающий 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.

Основание Дозволено также применять типовые числовые операторы для сопоставления 2-х значений BigInteger друг с ином. Как и другие типы целого числа, BigInteger поддерживает битовые операторы And, Or, XOR, сдвиг налево и сдвиг вправо.

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

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

  • IsEven – определяет является ли число чётным;
  • IsPowerOfTwo — определяет является ли число степенью двойки;
  • Sign — возвращает значение, указывающее знак числа BigInteger;
  • Abs — возвращает безусловное значение числа BigInteger;
  • DivRem — возвращает частное и остаток от операции деления;
  • GreatestCommonDivisor — возвращает крупнейший всеобщий делитель для 2-х чисел;
  • Log — возвращает логарифм указанного числа в системе счисления с указанным основанием;
  • Max / Min — возвращает наибольшее / наименьшее из 2-х чисел;
  • 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 = 0; i < length; i  )
 {
   if (IsPrime(num))
      num  ;
 }
Console.WriteLine(num); 


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

В данном примере, дозволено поступить дальнейшим образом: исполнить промежуточные операции, применяя обыкновенные числовые типы, а после этого применять BigInteger:

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


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

Взамен завершения


Подводя вывод, дозволено сказать, что платформа .NET, начиная с 4 версии, обзавелась полновесной реализациейцелочисленной длинной арифметики. Допустимо, для полного счастья осталось реализовать класс BigDecimal, но это теснее вовсе иная история.

 

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB