Как написать biginteger

Время на прочтение
9 мин

Количество просмотров 111K

Введение

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

123456789₁₀ = 1*10⁸ + 2*10⁷ + 3*10⁶ + 4*10⁵ + 5*10⁴ + 6*10³ + 7*10² + 8*10¹ + 9*10⁰

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

A = a_n-1β^n-1 + a_n-2β^n-2 +…+a₁β + a₀
где β – основание системы счисления, в которой мы представляем число, а коэффициенты a_i удовлетворяют двойному неравенству 0 ≤ a_i < β.

Представление числа напоминает представление многочлена, только вместо x в соответствующей степени имеем основание β в нужной степени. Как известно, многочлен a₀ + a₁x + a₂x² + … + a_nxⁿ удобно представлять в виде массива, элементы которого представляют коэффициенты a_i, а индекс i — определяет соответствующую степень x. Длинное число хранится аналогично, осталось определиться с выбором основания β.

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

123456789₁₀ = 1*(10⁴)² + 2345*(10⁴)¹ + 6789*(10⁴)⁰

Представляя число 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 содержит коэффициенты a_i. Учитывая, что массив _bits имеет тип uint[], можно так же предположить, что в качестве основания β взята степень двойки 2³² (поскольку uint — 32 разрядное беззнаковое число).

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

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

public BigInteger(int value)
 {
   if (value == int.MinValue)
   {
     this = BigInteger.s_bnMinInt;
   }
   else
   {
     this._sign = value;
     this._bits = (uint[]) null;
   }
 }

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

Идем дальше.

Конструктор, принимающий 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) поможет ответить на вопрос о выборе основания системы счисления:

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 содержит те самые коэффициенты a_i и заполняется следующим образом:

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 бит равносильно целочисленному делению на 2ⁿ).

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

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

Значит, 9223372036854775807 = 2147483647*(2³²)¹ + 4294967295*(2³²)⁰, и BigInteger
будет представлен парой:

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

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

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

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

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

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

_sign = 17
_bits = null

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

1. если число помещается в int диапазон, то оно хранится в переменной _sign;
2. если число не помещается в int диапазон, то его знак хранится в переменной _sign (-1 – для отрицательного и 1 – для положительного), а массив _bits содержит коэффициенты a_i разложения длинного числа с основанием 2³².

Основание β = 2³², является неплохим выбором, поскольку со степенью двойки легче работать на низком уровне (умножение и деление на степень двойки соответствует битовым сдвигам влево и вправо), а так же за раз будут обрабатываться целых 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 охватывает больший диапазон:

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

Все широко известные целочисленные типы данных в .NET имеют свои диапазоны значений, которые мы можем получить, используя свойства MaxValue или MinValue. Неизменяемы тип данных BigInteger представляет собой целое число со знаком, которое, в теории, не имеет верхних и нижних границ. Чтобы воспользоваться этим типом данных, необходимо подключить пространство имен System.Numerics.

Когда могут потребоваться большие числа?

Очевидно, что в 99% случаев вам вряд ли удастся провести какой-либо практически применимый расчёт, чтобы его результат превысил все возможные верхние границы целочисленных типов данных. Например, вряд ли когда либо у человека накопиться на счёту больше 18 446 744 073 709 551 615 (тип ulong) долларов. Однако, если дело касается каких-либо математических расчётов, попыток доказать какую-либо теорему, например для всего множества натуральных чисел и т.д., то, вполне возможно, что наступит момент, когда ваше очередное число не поместиться даже в тип ulong. Ну, или простой пример — попробуйте, используя все известные целочисленные типы рассчитать факториал 100 (100!). Результат такого вычисления — число со 158 знаками. Но на экране вы его не увидите.

Видимо, для подобных ситуаций, в свое время, в .NET появился специальный тип целочисленных значений — BigInteger.

Создание экземпляра BigInteger

Чтобы создать экземпляр BigInteger мы можем использовать несколько способов.

Использование оператора new

BigInteger big = new(134000);
BigInteger big2 = new(ulong.MaxValue);
BigInteger big3 = new(123456789.777777);

в параметры конструктора мы можем передавать целые числа, числа с плавающей запятой или массив типа byte[]:

byte[] byteArray = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
BigInteger big4 = new BigInteger(byteArray);

Присвоение значения переменной типа BigInteger

Второй, более привычный способ — присвоение значения переменной типа BigInteger, например:

BigInteger big3 = 123456;
BigInteger big4 = (BigInteger)123456.7777777;

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

Использование методов Parse и TryParse

Также, для создания экземпляра BigInteger мы можем использовать методы Parse и TryParse, которые извлекают число из строки:

string positiveString = "91389681247993671255432112022112134334002222222";
BigInteger posBigInt = 0;
try
{
    posBigInt = BigInteger.Parse(positiveString);
    Console.WriteLine(posBigInt);
}
catch (FormatException)
{
    Console.WriteLine("Невозможно конвертировать втроку '{0}' в значение BigInteger.", positiveString);
}

Использование свойств BigInteger

Также мы можем присвоить переменной значения 0 и 1, используя статические свойства BigInteger:

BigInteger bigNull = BigInteger.Zero;
BigInteger bigOne = BigInteger.One;
Console.WriteLine(bigNull);
Console.WriteLine(bigOne);

Выполнение операций с BigInteger

C BigInteger мы можем выполнять такие же операции, как и с обычными числами в C# — сложение, умножение, деление и т.д. Для этого в BigInteger присутствуют все необходимые перегруженные операторы.

Кроме этого, в BigInteger реализованы методы, аналогичные математическим методам из Math — возведение в степень, модуль числа и т.д. Ниже представлены основные методы BigInteger для выполнения математических операций:

Свойства BigInteger

У BigInteger имеется ряд свойств, позволяющих проводить необходимые проверки числа и возвращать новые экземпляры BigInteger:

Чему равен факториал 100?

Попробуем воспользоваться структурой BigInteger и рассчитать чему же равен факториал 100:

static BigInteger Factorial(int n)
{ 
    if ((n==0)||(n==1))
        return (BigInteger)n;
    return (BigInteger)n*Factorial(n-1);
}

static void Main(string[] args)
{
    Console.WriteLine(Factorial(100));
}

Результат:

Итого

Структура BigInteger представляет целочисленное значение неограниченного размера (этот тип данных не имеет границ MaxValue и MinValue). BigInteger содержит методы и свойства, позволяющие проводить основные математические операции с большими числами — возведение в степень, получение логарифма и так далее. Кроме этого, в BigInteger перегружены основные операторы — сложение, вычитание, умножение, деление, которые позволяют выполнять основные математические операции с BigInteger, как и с другими, известными нам, целочисленными типами.

Вступление

Класс BigInteger используется для математических операций с большими целыми числами с слишком большими величинами для примитивных типов данных. Например, 100-факториал составляет 158 цифр — намного больше, чем может представлять long . BigInteger предоставляет аналоги всем примитивным целочисленным операторам Java и всем соответствующим методам из java.lang.Math а также нескольким другим операциям.

Синтаксис

• BigInteger variable_name = new BigInteger («12345678901234567890»); // десятичное целое в виде строки
• BigInteger variable_name = new BigInteger («1010101101010100101010011000110011101011000111110000101011010010», 2) // двоичное целое в виде строки
• BigInteger variable_name = new BigInteger («ab54a98ceb1f0800», 16) // шестнадцатеричное целое число в виде строки
• BigInteger variable_name = new BigInteger (64, new Random ()); // генератор псевдослучайных чисел, обеспечивающий 64 бита для построения целого числа
• BigInteger variable_name = new BigInteger (новый байт [] {0, -85, 84, -87, -116, -21, 31, 10, -46}); // подписали двухдополнительное представление целого (big endian)
• BigInteger variable_name = new BigInteger (1, новый байт [] {- ​​85, 84, -87, -116, -21, 31, 10, -46}); // Непрерывное представление целых чисел без знака (положительное целое число)

замечания

BigInteger sum = BigInteger.ZERO;
for(int i = 1; i < 5000; i++) {
   sum.add(BigInteger.valueOf(i));  
}

sum = sum.add(BigInteger.valueOf(i));

инициализация

Класс java.math.BigInteger обеспечивает аналоги операций для всех примитивных целочисленных операторов Java и для всех соответствующих методов из java.lang.Math . Поскольку пакет java.math не будет автоматически доступен, вам может потребоваться импортировать java.math.BigInteger прежде чем вы сможете использовать простое имя класса.

Чтобы преобразовать значения long или int в BigInteger используйте:

long longValue = Long.MAX_VALUE;
BigInteger valueFromLong = BigInteger.valueOf(longValue); 

или, для целых чисел:

int intValue = Integer.MIN_VALUE; // negative
BigInteger valueFromInt = BigInteger.valueOf(intValue);

который расширит целое число intValue до long, используя расширение бита знака для отрицательных значений, так что отрицательные значения останутся отрицательными.

Чтобы преобразовать числовую String в BigInteger используйте:

String decimalString = "-1";
BigInteger valueFromDecimalString = new BigInteger(decimalString);

Следующий конструктор используется для преобразования строкового представления BigInteger в указанном радиусе в BigInteger .

String binaryString = "10";
int binaryRadix = 2;
BigInteger valueFromBinaryString = new BigInteger(binaryString , binaryRadix);

Java также поддерживает прямое преобразование байтов в экземпляр BigInteger . В настоящее время может использоваться только подписанная и беззнаковая кодировка большого конца:

byte[] bytes = new byte[] { (byte) 0x80 }; 
BigInteger valueFromBytes = new BigInteger(bytes);

Это будет генерировать экземпляр BigInteger со значением -128, поскольку первый бит интерпретируется как бит знака.

byte[] unsignedBytes = new byte[] { (byte) 0x80 };
int sign = 1; // positive
BigInteger valueFromUnsignedBytes = new BigInteger(sign, unsignedBytes);

Это будет генерировать экземпляр BigInteger со значением 128, поскольку байты интерпретируются как беззнаковое число, а знак явно установлен в 1, положительное число.

Существуют предопределенные константы для общих значений:

• BigInteger.ZERO — значение «0».
• BigInteger.ONE — значение «1».
• BigInteger.TEN — значение «10».

Существует также BigInteger.TWO (значение «2»), но вы не можете использовать его в своем коде, потому что он является private .

Сравнение BigIntegers

Вы можете сравнить BigIntegers же, как вы сравниваете String или другие объекты в Java.

Например:

BigInteger one = BigInteger.valueOf(1);
BigInteger two = BigInteger.valueOf(2);

if(one.equals(two)){
    System.out.println("Equal");
}
else{
    System.out.println("Not Equal");
}

Выход:

Not Equal

Замечания:

В общем, не используйте использование оператора == для сравнения BigIntegers

• == operator: сравнивает ссылки; т.е. имеют ли два значения один и тот же объект
• Метод equals() : сравнивает содержимое двух BigIntegers.

Например, BigIntegers не следует сравнивать следующим образом:

if (firstBigInteger == secondBigInteger) {
  // Only checks for reference equality, not content equality!
}

Это может привести к неожиданному поведению, поскольку оператор == проверяет только ссылочное равенство. Если оба BigIntegers содержат один и тот же контент, но не относятся к одному и тому же объекту, это не сработает. Вместо этого сравните BigIntegers, используя методы equals , как описано выше.

Вы также можете сравнить свой BigInteger с постоянными значениями, такими как 0,1,10.

например:

BigInteger reallyBig = BigInteger.valueOf(1);
if(BigInteger.ONE.equals(reallyBig)){
    //code when they are equal.
}    

Вы также можете сравнить два BigIntegers с помощью метода compareTo() , как compareTo() ниже: compareTo() возвращает 3 значения.

• 0: Когда оба равны .
• 1: Когда первое больше второго (одно в скобках).
• -1: Когда первое меньше секунды.

BigInteger reallyBig = BigInteger.valueOf(10);
BigInteger reallyBig1 = BigInteger.valueOf(100);

if(reallyBig.compareTo(reallyBig1) == 0){
    //code when both are equal.
}
else if(reallyBig.compareTo(reallyBig1) == 1){
    //code when reallyBig is greater than reallyBig1.
}
else if(reallyBig.compareTo(reallyBig1) == -1){
    //code when reallyBig is less than reallyBig1.
}

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

Дополнение: 10 + 10 = 20

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("10");

BigInteger sum = value1.add(value2);
System.out.println(sum);

выход: 20

Субстрат: 10 — 9 = 1

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("9");

BigInteger sub = value1.subtract(value2);
System.out.println(sub);

выход: 1

Отдел: 10/5 = 2

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("5");

BigInteger div = value1.divide(value2);
System.out.println(div);

выход: 2

Отдел: 17/4 = 4

BigInteger value1 = new BigInteger("17");
BigInteger value2 = new BigInteger("4");

BigInteger div = value1.divide(value2);
System.out.println(div);

выход: 4

Умножение: 10 * 5 = 50

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("5");

BigInteger mul = value1.multiply(value2);
System.out.println(mul);

выход: 50

Мощность: 10 ^ 3 = 1000

BigInteger value1 = new BigInteger("10");
BigInteger power = value1.pow(3);
System.out.println(power);

выход: 1000

Остаток: 10% 6 = 4

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("6");

BigInteger power = value1.remainder(value2);
System.out.println(power);

выход: 4

GCD: наибольший общий делитель (GCD) для 12 и 18 — 6 .

BigInteger value1 = new BigInteger("12");
BigInteger value2 = new BigInteger("18");

System.out.println(value1.gcd(value2));

Выход: 6

Максимум два BigIntegers:

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("11");

System.out.println(value1.max(value2));

Выход: 11

Минимум двух BigIntegers:

BigInteger value1 = new BigInteger("10");
BigInteger value2 = new BigInteger("11");

System.out.println(value1.min(value2));

Выход: 10

Двоичные логические операции на BigInteger

BigInteger поддерживает двоичные логические операции, доступные также для типов Number . Как и во всех операциях, они реализуются путем вызова метода.

Двоичный или:

BigInteger val1 = new BigInteger("10");
BigInteger val2 = new BigInteger("9");

val1.or(val2);

Выход: 11 (что эквивалентно 10 | 9 )

Двоичные и:

BigInteger val1 = new BigInteger("10");
BigInteger val2 = new BigInteger("9");

val1.and(val2);

Выход: 8 (что эквивалентно 10 & 9 )

Binary Xor:

BigInteger val1 = new BigInteger("10");
BigInteger val2 = new BigInteger("9");

val1.xor(val2);

Выход: 3 (что эквивалентно 10 ^ 9 )

RightShift:

BigInteger val1 = new BigInteger("10");

val1.shiftRight(1);   // the argument be an Integer    

Выход: 5 (эквивалентно 10 >> 1 )

Сдвиг влево:

BigInteger val1 = new BigInteger("10");

val1.shiftLeft(1);   // here parameter should be Integer    

Выход: 20 (эквивалентно 10 << 1 )

Двоичная инверсия (нет):

BigInteger val1 = new BigInteger("10");

val1.not();

Выход: 5

NAND (And-Not): *

BigInteger val1 = new BigInteger("10");
BigInteger val2 = new BigInteger("9");

val1.andNot(val2);

Выход: 7

Создание случайных BigIntegers

Класс BigInteger имеет конструктор, предназначенный для генерации случайных BigIntegers , учитывая экземпляр java.util.Random и int который определяет, сколько бит будет иметь BigInteger . Его использование довольно просто — когда вы вызываете конструктор BigInteger(int, Random) следующим образом:

BigInteger randomBigInt = new BigInteger(bitCount, sourceOfRandomness);

то вы получите BigInteger , значение которого находится в ^bitCount от 0 (включительно) и до 2 ^bitCount (исключение).

Это также означает, что new BigInteger(2147483647, sourceOfRandomness) может вернуть все положительные значения BigInteger с достаточным временем.

Какова будет sourceOfRandomness ? Например, new Random() достаточно хорош в большинстве случаев:

new BigInteger(32, new Random());

Если вы хотите отказаться от скорости для более качественных случайных чисел, вместо этого вы можете использовать new SecureRandom () :

import java.security.SecureRandom;

// somewhere in the code...
new BigInteger(32, new SecureRandom());

Вы даже можете реализовать алгоритм «на лету» с анонимным классом! Обратите внимание , что выкатывает свой собственный алгоритм ГСЧ закончится вас с низким качеством случайностью, поэтому всегда обязательно использовать алгоритм , который , как доказано , чтобы быть достойной , если вы не хотите, чтобы в результате BigInteger (ы) быть предсказуемым.

new BigInteger(32, new Random() {
    int seed = 0;

    @Override
    protected int next(int bits) {
        seed = ((22695477 * seed) + 1) & 2147483647; // Values shamelessly stolen from Wikipedia
        return seed;
    }
});

В предыдущих темах мы рассмотрели проблему в решениях, где получаются большие значения. Встроенные примитивные типы (int, long, double) имеют сравнительно малый числовой диапазон значений, и если нам необходимо оперировать огромными числами нужно использовать встроенную поддержку работы с длинными числам на платформе .NET. Для работы с BigInteger нужно подключить пространство имен System.Numerics, и инициализировать экземпляр объекта с помощью оператора new:

//Листинг программы
using System;
using System.Numerics;                                    //обязательное подключение пространства имен
namespace Serg40in {
  class Program     {
    static void Main(string[] args) {
        BigInteger bigInt = new BigInteger(123456789123456789); //большое int
        Console.ReadKey();
    }
  }
}

Как видно из примера, создается переменная (экземпляр объекта BigInteger) bigInt. Конструкция объявления почти такая же как и с примитивами (int num=10), только после знака присвоения используется оператор new BigInteger() и в скобках указывается значение.

Или можно использовать следующую сокращенную форму конструкции создания переменной BigInteger, где значение переменной summDigits сохраняется в создаваемую BigInteger переменную:

int summDigits=320002;
BigInteger bigSummDigits = summDigits;

Или мы можем указать изначальное числовое значение, но нужно быть внимательным, так как изначальное значение не должно быть больше long.MaxValue:

BigInteger bigSummDigits = 15500;                               //корректное обьявления
BigInteger bigLen = 12345678901234567890;                       //некорректное обьявления!
BigInteger bigHeigth = new BigInteger(12345678901234567890);    //корректное обьявления

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

string strNumber="123456678909987654321123455678900009987654321234545678890098876543321";
BigInteger bigInt = BigInteger.Parse(strNumber);

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

System.FormatException: Не удалось выполнить синтаксический анализ значения

Поэтому, хорошей практикой при конвертации значений, будет использование известного нам TryParse(), чтобы исключить неожиданный критический выход (crash, крах, крит) из программы:

string strNumber="fhfhfgh321в";
if (BigInteger.TryParse(strNumber, out BigInteger bigInt)) {
   Console.Write("Корректное число: n" + bigInt);
} else {
   Console.Write("Некорректное число: n" + strNumber);
}

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

С переменными BigInteger типа, можно использовать любые операции, которые можно использовать для примитивных типов:

//Листинг программы
using System;
using System.Numerics; 			//обязательное подключение пространства имен
namespace Serg40in {
 class Program     {
  static void Main(string[] args) {
	BigInteger result;
	BigInteger operandOne=9999999;
	BigInteger operandTwo=999999;

	result=operandOne+operandTwo;
	 Console.WriteLine($"{operandOne}+{operandTwo} = {result}");   //9999999+999999 = 10999998     
	result=operandOne-operandTwo;
	 Console.WriteLine($"{operandOne}-{operandTwo} = {result}");   //9999999-999999 = 9000000
	result=operandOne*operandTwo;
	 Console.WriteLine($"{operandOne}*{operandTwo} = {result}");   //9999999*999999 = 9999989000001
	result=operandOne/operandTwo;
	 Console.WriteLine($"{operandOne}/{operandTwo} = {result}");   //9999999/999999 = 10
	Console.ReadKey();
  }
 }
}

Но если мы в предыдущем примере переменные operandOne и operandTwo инициализируем отличным от BigInteger типом, то у нас не получится получать точное математическое значение и все приведется в числовой диапазон выбранного типа:

//Листинг программы
using System;
using System.Numerics; 			//обязательное подключение пространства имен
namespace Serg40in {
 class Program     {
  static void Main(string[] args) {
	BigInteger result;
	int operandOne=100000000;
	int operandTwo=33333333;

	result=operandOne+operandTwo;
	 Console.WriteLine($"{operandOne}+{operandTwo} = {result}");	//9999999+999999 = 133333333        
	result=operandOne-operandTwo;
	 Console.WriteLine($"{operandOne}-{operandTwo} = {result}");	//9999999-999999 = 66666667         
	result=operandOne*operandTwo;
	 Console.WriteLine($"{operandOne}*{operandTwo} = {result}");	//9999999*999999 = 591639808
	result=operandOne/operandTwo;
	 Console.WriteLine($"{operandOne}/{operandTwo} = {result}");	//9999999/999999 = 3
	Console.ReadKey();
  }
 }
}

Рассмотрим и то, что остаток от деления у нас получился целым, так как BigInteger — это большое целое, и разработчиками языка эта структура была создана для работы именно с целыми значениями. Если грубо сказать BigInteger это резиновый int. Для хранения больших дробных значений используется тип decimal.

Ниже приведем пример где можем получить остаток от деления тремя способами, первый это оператор %, второй — метод структуры BigInteger – DivRem,третий — метод Remainder это получение остатка от деления:

//Листинг программы
using System;
using System.Numerics; 			//обязательное подключение пространства имен
namespace Serg40in {
 class Program     {
  static void Main(string[] args) {
	BigInteger result;
	BigInteger operandOne=100000000;
	BigInteger operandTwo=12345678;
	BigInteger remainder;
	result=operandOne / operandTwo;
	remainder=operandOne % operandTwo;
	 Console.WriteLine($"{operandOne}/{operandTwo} = {result}");	   //100000000 / 12345678= 8
	 Console.WriteLine($"{operandOne}%{operandTwo} = {remainder}");    //100000000 % 12345678= 1234576
	result=BigInteger.DivRem(operandOne, operandTwo, out remainder);
	 Console.WriteLine($"{operandOne}/{operandTwo} = {result}");       //100000000 / 12345678= 8
	 Console.WriteLine($"{operandOne}%{operandTwo} = {remainder}");    //100000000 % 12345678= 1234576
	result=BigInteger.Remainder(operandOne, operandTwo);
	Console.WriteLine($"{operandOne}%{operandTwo} = {result}");        //100000000 % 12345678= 1234576
	Console.ReadKey();
  }
 }
}

В строке, где используется BigInteger.DivRem(), методиспользует три операнда: делимое, делитель, переменная где будет храниться остаток от деления — remainder. А результат выполнения BigInteger.DIvRem(), целое частное, сохраниться в переменной result.

Структура BigInteger имеет много методов и свойств, рассмотрим их вкратце, сначала изучим свойства, при инициализированной переменной:

BigInteger bigOne = 1024;

.IsEven:указывает, равно ли значение текущего объекта BigInteger четному числу

Console.WriteLine($"Число {bigOne} четное = {bigOne.IsEven}"); // True

.IsOne: указывает, равно ли значение текущего объекта BigInteger значению One

Console.WriteLine($"Число {bigOne} равно единице = {bigOne.IsOne}"); // False

.IsPowerOfTwo: указывает, равно ли значение текущего объекта BigInteger степени двух

Console.WriteLine($"Число {bigOne} степень двойки = {bigOne.IsPowerOfTwo}");// True

.IsZero: указывает, равно ли значение текущего объекта BigInteger значению Zero

Console.WriteLine($"Число {bigOne} равно нулю = {bigOne.IsZero}"); // False

.MinusOne: получает значение, представляющее минус единицу (-1)

.One: получает значение, представляющее единицу (1)

.Sign: получает число, указывающее знак (-1, 1 или 0) текущего объекта BigInteger

Console.WriteLine($"Sign числа {bigOne} = {bigOne.Sign}"); // 1

Теперь с примерами рассмотрим методы структуры BigInteger, при инициализированных двух переменных:

BigInteger bigOne = 1024;

BigInteger bigTwo = 24;

Abs(BigInteger): получает абсолютное значение объекта BigInteger

Console.WriteLine(BigInteger.Abs(bigOne)); // 1024

Add(BigInteger, BigInteger): складывает два значения BigInteger и возвращает результат

Console.WriteLine(BigInteger.Add(bigOne, bigTwo)); // 1048

Compare(BigInteger, BigInteger): сравнивает два значения BigInteger и возвращает целое значение, которое показывает, больше или меньше первое значение по сравнению со вторым или равно ему (1 — больше, -1, 0)

Console.WriteLine(BigInteger.Compare(bigOne, bigTwo)); // 1

Divide(BigInteger, BigInteger): делит одно значение BigInteger на другое и возвращает целочисленный результат

Console.WriteLine(BigInteger.Divide(bigOne, bigTwo)); // 42

DivRem(BigInteger, BigInteger, BigInteger): делит одно значение BigInteger на другое, возвращает результат, а также возвращает остаток в виде параметра вывода

BigInteger bigRemainder;                                                // 16
Console.WriteLine(BigInteger.DivRem(bigOne, bigTwo, out bigRemainder)); // 42

Equals(BigInteger): возвращает значение, определяющее равны ли текущий экземпляр и указанный объект BigInteger

Console.WriteLine(bigOne.Equals(bigTwo)); // False

Max(BigInteger, BigInteger): возвращает наибольшее из двух значений BigInteger

Console.WriteLine(BigInteger.Max(bigOne, bigTwo)); // 1024

Min(BigInteger, BigInteger): возвращает наименьшее из двух значений BigInteger

Console.WriteLine(BigInteger.Min(bigOne, bigTwo)); // 24

Multiply(BigInteger, BigInteger): возвращает произведение двух значений BigInteger

Console.WriteLine(BigInteger.Multiply(bigOne, bigTwo)); // 24576

Negate(BigInteger): меняет знак указанного значения BigInteger

Console.WriteLine(BigInteger.Negate(bigOne)); // -1024

Parse(String): преобразует строковое представление числа в его эквивалент типа BigInteger

Console.WriteLine(BigInteger.Parse("1024")+bigOne); // 2048

Pow(BigInteger, Int32): возводит значение BigInteger в заданную степень.

Console.WriteLine(BigInteger.Pow(bigOne,10)); // 1267650600228229401496703205376

Remainder(BigInteger, BigInteger): выполняет целочисленное деление двух значений BigInteger и возвращает остаток.

Console.WriteLine(BigInteger.Remainder(bigOne, bigTwo)); // 16

Subtract(BigInteger, BigInteger): вычитает одно значение BigInteger из другого и возвращает результат.

Console.WriteLine(BigInteger.Subtract(bigOne, bigTwo)); // 1000

ToString(): преобразует числовое значение текущего объекта BigInteger в эквивалентное ему строковое представление.

Console.WriteLine(bigOne.ToString()+bigTwo); // 102424

Подытожим. Если нам необходимо использовать большие числа, превосходящие по значению экстремумы примитивных типов, то используем BigInteger. Но при этом мы должны четко понимать, что структура длинных чисел подразумевает встроенную программную обработку больших значений, что приводит к большой нагрузке на процессор. И в обыденных действиях с малыми числовыми диапазонами используем только примитивные типы данных (int, long, short, byte, double и т.д.), так как операции с ними происходят значительно быстрее.

Больше про BigInteger на странице с документацией

https://docs.microsoft.com/ru-ru/dotnet/api/system.numerics.biginteger?view=net-5.0

https://habr.com/ru/post/207754/

Loop_24

При введенном любом целом n, найти значение факториала n (n!). При некорректном числе — контролировано завершить программу.

Пример использования: 
Выходные данные 1: Введите целое число неравное нулю
Входные данные  1: 25
Выходные данные 1: Факториал (25!) = 15511210043330985984000000

Пример использования: 
Выходные данные 2: Введите целое число неравное нулю
Входные данные  2: -5
Выходные данные 2: Факториал (-5!) = -120

Пример использования: 
Выходные данные 3: Введите целое число неравное нулю
Входные данные  3: 3.4
Выходные данные 3: Вы ввели некорректное значение

Решение:

Изначально в группе using добавим использование библиотеки System.Numerics. Следующим шагом пригласим пользователя ввести целое число. Если число некорректно — выводим сообщение об ошибке ввода и завершаем программу. Иначе проверяем его значение: если число больше ноля — то начальное значение переменной цикла будет единица, а последнее значение n. Если же n меньше ноля — начальное значение переменной цикла будет n, а последнее значение, при котором произведение чисел не будет равна нулю, будет -1. Нужно не забыть про возможно введенный ноль, где результат значения 0! будет являться единица. Организуем цикл for, где в теле программы инициализируем BigInteger переменную правильно, так как это произведение, то любой множитель равный нулю приведет к ошибке вычисления выражения:

//Листинг решения задачи loop_24
using System;
using System.Numerics;
namespace Serg40in {
 class Program {
  static void Main () {
	Console.WriteLine("Введите целое число");
	if (int.TryParse(Console.ReadLine(), out int n)) {
	   BigInteger factorial = 1;
	   int start = n < 0 ?  n: 1;
	   int end   = n < 0 ? -1: n;
	   for (int i = start; i <= end; i++)
	      factorial *= i;
	   Console.WriteLine($"Факториал ({n}!) = {factorial}");
	} else Console.WriteLine("Вы ввели некорректное значение");
	Console.ReadKey();
  }
 }
}

Ниже приведены задания по теме для самостоятельного решения:

• При решении не использовать класс Math, пользовательские методы, конструкцию try-catch;
• Значения в выводе на консоли должны быть только корректные;
• Алгоритм оптимизировать по скорости исполнения при малых значениях;
• Программа не должна критически останавливаться с ошибкой конвертирования данных;
• Интерфейс консольного приложения обязан быть опрятным и дружелюбным!

Home_67. По данному числу n!=0, найдите произведение четных чисел от 1 до n, или от n до 1, если n < 0.

Home_68. Написать программу для нахождения a в степени n, введенных построчно с клавиатуры.

Home_69. По данным с клавиатуры двум целым числа a и b, вычислите произведение чисел на отрезке от a до b.

Home_70. По данным построчно двум целым числам a и b, узнать какое выражение больше a^b или b^a.

Home_71. Выведите количество натуральных делителей целого числа x, исключая единицу и само число.

Home_72. По данному числу N найдите те числа, где сумма цифр квадрата числа больше N.

Home_73. По данным построчно двум целым числам a и b, вычислите количество и произведение чисел на отрезке от a до b оканчивающихся на 19.

Home_74. Найти среднее арифметическое чисел из числового диапазона от a до b.

BigInteger class is used for the mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types.

In this way, BigInteger class is very handy to use because of its large method library and it is also used a lot in competitive programming. 
Now below is given a list of simple statements in primitive arithmetic and its analogous statement in terms of BigInteger objects.

Example:

int a, b;                
BigInteger A, B; 

Initialization is as follows:

a = 54;
b = 23;

A  = BigInteger.valueOf(54);
B  = BigInteger.valueOf(37); 

And for Integers available as strings you can initialize them as follows:

A  = new BigInteger(“54”);
B  = new BigInteger(“123456789123456789”); 

Some constants are also defined in BigInteger class for ease of initialization as follows:

A = BigInteger.ONE;
// Other than this, available constant are BigInteger.ZERO 
// and BigInteger.TEN 

Mathematical operations are as follows:  

int c = a + b;
BigInteger C = A.add(B); 

Other similar functions are subtract(), multiply(), divide(), remainder(), but all these functions take BigInteger as their argument so if we want this operation with integers or string convert them to BigInteger before passing them to functions as shown below: 

String str = “123456789”;
BigInteger C = A.add(new BigInteger(str));
int val  = 123456789;
BigInteger C = A.add(BigInteger.valueOf(val)); 

Extraction of value from BigInteger is as follows:

int x   =  A.intValue();   // value should be in limit of int x
long y   = A.longValue();  // value should be in limit of long y
String z = A.toString();  

Comparison 

if (a < b) {}         // For primitive int
if (A.compareTo(B) < 0)  {} // For BigInteger 

Actually compareTo returns -1(less than), 0(Equal), 1(greater than) according to values. For equality we can also use: 

if (A.equals(B)) {}  // A is equal to B 

Methods of BigInteger Class

Illustration: 

Factorial of 100 contains 158 digits in it so we can’t store it in any primitive data type available. We can store as large an Integer as we want in it. There is no theoretical limit on the upper bound of the range because memory is allocated dynamically but practically as memory is limited you can store a number that has Integer.MAX_VALUE number of bits in it which should be sufficient to store mostly all large values.

Example:

Output: 

2432902008176640000

Tip: If we have to write above program in C++, that would be too large and complex, we can look at Factorial of Large Number. 

So after the above knowledge of the function of BigInteger class, we can solve many complex problems easily, but remember as BigInteger class internally uses an array of integers for processing, the operation on an object of BigIntegers are not as fast as on primitives that are add function on BigIntgers doesn’t take the constant time it takes time proportional to the length of BigInteger, so the complexity of program will change accordingly.

This article is contributed by Utkarsh Trivedi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Must Read:

• Large Fibonacci Numbers in Java
• BigInteger class also provides quick methods for prime numbers.