@tguev7 янв 2014 в 11:29

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

9 мин

122K

.NET * Алгоритмы * C# *

+52

Комментарии 33

@novoselov 7 янв 2014 в 11:52

Следует сказать, что структура BigInteger появилась ещё в .NET 3.5, но была определена как internal

@viklequick 7 янв 2014 в 12:04

Эх, как еще в дотнете 1.1 не хватало жавовских BigInteger и BigDecimal… И вот счастье наступило только в 4й версии, да и то не полное.

А BigDecimal::setScale () и сейчас не хватает настолько что я его из жавы утащил.

@Bringoff 7 янв 2014 в 12:23

А что за ::? Немного С++ кагбэ напоминает :)

@Bringoff 7 янв 2014 в 12:28

Или вы тот редкий зверь, который на С++ CLI пишет? О_о

@viklequick 7 янв 2014 в 13:07

С++ нотация в таких случаях самая однозначная, AFAIR.

@int19h 7 янв 2014 в 18:58

>> Эх, как еще в дотнете 1.1 не хватало жавовских BigInteger и BigDecimal…

Все-таки большинство целей, для которых в Java использовался BigDecimal (работа с деньгами и прочие моменты, где нужна десятичная арифметика без неявной потери точности), в .NET успешно покрывались обычным decimal — который при этом намного быстрее.

@ivanrt 7 янв 2014 в 12:41

А ничего, что два куска кода в конце делают разные вещи? Один всё время проверяет одно и тоже число на IsPrime, другой по сути ищет первый не prime и дальше критит цикл в холостую? Или я что-то не понимаю?

@tguev 7 янв 2014 в 13:18

Подправил, опечаточка с параметром метода IsPrime вышла.

@0x0FFF 7 янв 2014 в 15:51

Для примера со системой счисления с основанием 10⁴ будет всё-таки так:
123456789₁₀ = 1*(10⁴)² + 2345*(10⁴)¹ + 6789*(10⁴)⁰

@tguev 7 янв 2014 в 16:12

Да действительно. Исправил.

@vlivyur 5 мар 2014 в 08:52

И всё-таки правильно так: 123456789_10⁴

@Zlobober 7 янв 2014 в 15:55

За какую сложность в .NET-ной реализаии BigInteger происходит умножение, деление длинного на длинное, взятие по модулю, вывод числа (который требует перевода в десятичную систему счисления)?

@Saladin 7 янв 2014 в 16:27

Здесь пишут, что для умножения используется алгоритм Карацубы, который работает за O(n^(log(2,3)))
Для сложения используется линейный алгоритм

@KvanTTT 15 фев 2014 в 23:50

Уж не знаю, что там пишут, но по судя по 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);
}

@Saladin 11 авг 2017 в 09:00

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

Однако, если заглянуть в исходники CoreFX, то здесь уже, похоже, используется более продвинутый алгоритм, я думаю это какая-то модификация алгоритма Карацубы.
Здесь можно найти обсуждение.

@tguev 7 янв 2014 в 16:46

1. По поводу взятия модуля все просто: поскольку знак хранится в отдельной переменной то получить модуль ничего не стоит (необходимо только сравнение с нулем).

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

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

3. Умножение и деление (как я понял) выполняется обычным способом в столбик, который занимает O(n²) времени. Однако поскольку мы обрабатываем за раз целых 2³² разрядов, получаем сложность перемножения/деления равную O(log²n). Хотя возможно используется алгоритм Карацубы.

@Zlobober 7 янв 2014 в 17:29

1. Взятие по модулю в смысле взятия остатка от деления.

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

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

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

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

@HandleX 7 янв 2014 в 15:58

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

Воистину, история развивается по спирали ))

@KvanTTT 15 фев 2014 в 23:24

Вообще-то unchecked переполнение (когда, например, 255 превращается в 0) может использоваться и для написания более производительного кода. Так что не все так просто :)

@pravic 7 янв 2014 в 17:36

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

Как сложно написано, а на самом деле всё проще ведь:
9223372036854775807 = 0x7FFFFFFFFFFFFFFF, хранится как {0xFFFFffff, 0x7FFFfff}

@SkidanovAlex 7 янв 2014 в 18:39

Кстати, гораздо интереснее случай с минимальным long-ом чем с максимальным.

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

Вот тут похоже что -value вычисляется сначала в знаковом типе, и происходит переполнение, а потом приводится к беззнаковому. В C# гарантируется, что результат будет всегда правильный в этом случае?

@tguev 7 янв 2014 в 19:49

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 = -2⁶³ = 100000...000 противоположное число будет совпадать с самим числом, поскольку дополнительные коды совпадают:
100000...000

011111...111 инвертирование
000000...001 +1
__________
100000...000 дополнительный код для 100000...000

@SkidanovAlex 7 янв 2014 в 20:39

Да, это все понятно. Мой вопрос был скорее про то, что ведь .NET заявляется как кросс-платформенный, а это поведение завязано на платформо-зависимое поведение при переполнении и приведении типов. Отсюда был вопрос — в .NET гарантируется что (ulong) -2^63 = 2^63?

@Saladin 7 янв 2014 в 22:52

Не совсем понятно, где здесь платформо-зависимое поведение? Насколько я помню всю работу за соблюдение приведения типов и переполнение .NET берет на себя и не полагается в этом случае на платформу на которой он работает. Хотя я возможно могу ошибаться.

@SkidanovAlex 7 янв 2014 в 23:45

Ну потому что не на всякой платформе отрицательные числа хранятся в дополнительном коде. Но я уже нашел на 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.

@Amomum 8 янв 2014 в 13:25

Прошу прощения, а вы можете назвать пару платформ, где используется не дополнительный код?

@SkidanovAlex 8 янв 2014 в 18:32

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

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

@Amomum 9 янв 2014 в 10:54

Просто я не уверен, что все еще есть хоть какой-то смысл заботиться о возможности работы на такой платформе.

@mx2000 8 янв 2014 в 08:11

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

ЛОЛШТО?!

ЗЫ. Еще П. Нортон в своей знаменитой Assembly Language for IBM PC в качестве разминки и закрепления материала показывал, как реализовать калькулятор, оперирующий десятичной целочисленной арифметикой без ограничения на разрядность чисел. 1986 год. А вы тут про дотнет. :D

@sci_nov 9 янв 2014 в 10:59

Представляя число 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).
При практической реализации возможны некоторые дробления, так как ячейки памяти удобно бить на байты.

@KvanTTT 15 фев 2014 в 23:58

Стоит отметить, что под .NET также есть библиотека IntXLib, в которой используется дискретное преобразование Хартли для эффективной реализации операций с большими числами (временная сложность O(N * log N * log log N)). Автор провел тесты производительности по сравнению со стандартной реализацией (у него быстрее).

@KvanTTT 16 фев 2014 в 00:06

А существуют ли библиотеки для работы с большими числами с плавающей точкой? Ну чтобы, например, считать sin с произвольной точностью?

@user4000 10 авг 2017 в 07:35

Где вы взяли эту странную языковую конструкцию?

ModPow — выполняет модульное деление числа, возведенного в степень другого числа

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий