Pull to refresh

Comments 33

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

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

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

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

Однако, если заглянуть в исходники CoreFX, то здесь уже, похоже, используется более продвинутый алгоритм, я думаю это какая-то модификация алгоритма Карацубы.
Здесь можно найти обсуждение.
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). Хотя возможно используется алгоритм Карацубы.
1. Взятие по модулю в смысле взятия остатка от деления.

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

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

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

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

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

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

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



Вот тут похоже что -value вычисляется сначала в знаковом типе, и происходит переполнение, а потом приводится к беззнаковому. В C# гарантируется, что результат будет всегда правильный в этом случае?
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
Да, это все понятно. Мой вопрос был скорее про то, что ведь .NET заявляется как кросс-платформенный, а это поведение завязано на платформо-зависимое поведение при переполнении и приведении типов. Отсюда был вопрос — в .NET гарантируется что (ulong) -2^63 = 2^63?
Не совсем понятно, где здесь платформо-зависимое поведение? Насколько я помню всю работу за соблюдение приведения типов и переполнение .NET берет на себя и не полагается в этом случае на платформу на которой он работает. Хотя я возможно могу ошибаться.
Ну потому что не на всякой платформе отрицательные числа хранятся в дополнительном коде. Но я уже нашел на 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.
Прошу прощения, а вы можете назвать пару платформ, где используется не дополнительный код?
Я думаю что сегодня найти такую будет не очень просто. Я спрашивал с теоретической точки зрения.

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

ЛОЛШТО?!

ЗЫ. Еще П. Нортон в своей знаменитой Assembly Language for IBM PC в качестве разминки и закрепления материала показывал, как реализовать калькулятор, оперирующий десятичной целочисленной арифметикой без ограничения на разрядность чисел. 1986 год. А вы тут про дотнет. :D
Представляя число 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).
При практической реализации возможны некоторые дробления, так как ячейки памяти удобно бить на байты.
Стоит отметить, что под .NET также есть библиотека IntXLib, в которой используется дискретное преобразование Хартли для эффективной реализации операций с большими числами (временная сложность O(N * log N * log log N)). Автор провел тесты производительности по сравнению со стандартной реализацией (у него быстрее).
А существуют ли библиотеки для работы с большими числами с плавающей точкой? Ну чтобы, например, считать sin с произвольной точностью?
Где вы взяли эту странную языковую конструкцию?
ModPow — выполняет модульное деление числа, возведенного в степень другого числа

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

Articles