Комментарии 33
Следует сказать, что структура BigInteger появилась ещё в .NET 3.5, но была определена как internal
Эх, как еще в дотнете 1.1 не хватало жавовских BigInteger и BigDecimal… И вот счастье наступило только в 4й версии, да и то не полное.
А BigDecimal::setScale () и сейчас не хватает настолько что я его из жавы утащил.
А BigDecimal::setScale () и сейчас не хватает настолько что я его из жавы утащил.
А что за ::? Немного С++ кагбэ напоминает :)
>> Эх, как еще в дотнете 1.1 не хватало жавовских BigInteger и BigDecimal…
Все-таки большинство целей, для которых в Java использовался BigDecimal (работа с деньгами и прочие моменты, где нужна десятичная арифметика без неявной потери точности), в .NET успешно покрывались обычным decimal — который при этом намного быстрее.
Все-таки большинство целей, для которых в Java использовался BigDecimal (работа с деньгами и прочие моменты, где нужна десятичная арифметика без неявной потери точности), в .NET успешно покрывались обычным decimal — который при этом намного быстрее.
А ничего, что два куска кода в конце делают разные вещи? Один всё время проверяет одно и тоже число на IsPrime, другой по сути ищет первый не prime и дальше критит цикл в холостую? Или я что-то не понимаю?
Для примера со системой счисления с основанием 104 будет всё-таки так:
12345678910 = 1*(104)2 + 2345*(104)1 + 6789*(104)0
12345678910 = 1*(104)2 + 2345*(104)1 + 6789*(104)0
За какую сложность в .NET-ной реализаии BigInteger происходит умножение, деление длинного на длинное, взятие по модулю, вывод числа (который требует перевода в десятичную систему счисления)?
Уж не знаю, что там пишут, но по судя по 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, то здесь уже, похоже, используется более продвинутый алгоритм, я думаю это какая-то модификация алгоритма Карацубы.
Здесь можно найти обсуждение.
Однако, если заглянуть в исходники 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). Хотя возможно используется алгоритм Карацубы.
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 разряда, и это никак не повлияет на сложность, которая по-прежнему останется квадратичной.
Казалось бы, если у вас есть возможность посмотреть на код реализации умножения, очень легко понять, алгоритм ли это Карацубы или квадратичный.
2. > логарифмическое время от длинны числа.
Вы, вероятно, имели в виду логарифмическое время от самого числа (т. е. линейное по его длине).
Так вот, это очень сомнительно, потому что нельзя перевести число в двоичной системе в десятичную, просто по отдельности обработав биты его записи. Чтобы сделать это в тупую, надо его школьным алгоритмом делить каждый раз на 10 и выписывать остаток от деления как очередной разряд, то есть время будет квадратичным по длине числа. Более того, в Java-реализации длинной арифметики вывод числа это одна из самых трудоёмких операций именно потому, что реализована за квадрат (насколько я знаю).
3. > обрабатываем за раз целых 232 разрядов
> получаем сложность перемножения/деления равную O(log2n).
Опять же, что-то у вас смешались в кучу кони и люди. Мы, всё-таки, за раз обрабатываем 32 разряда, и это никак не повлияет на сложность, которая по-прежнему останется квадратичной.
Казалось бы, если у вас есть возможность посмотреть на код реализации умножения, очень легко понять, алгоритм ли это Карацубы или квадратичный.
В основных реализациях Smalltalk класс BigInteger присутствует уже лет 20 как… Причём результат выполнения арифм. операций, могущих вызвать переполнение, сам приводится к корректному типу, освобождая голову программисту более важным вещам.
Воистину, история развивается по спирали ))
Воистину, история развивается по спирали ))
Давайте определим, как будет храниться число long.MaxValue = 263-1 = 9223372036854775807 в структуре BigInteger. Для этого поделим его на 232:
Как сложно написано, а на самом деле всё проще ведь:
9223372036854775807 = 0x7FFFFFFFFFFFFFFF, хранится как {0xFFFFffff, 0x7FFFfff}
Кстати, гораздо интереснее случай с минимальным long-ом чем с максимальным.
Вот тут похоже что -value вычисляется сначала в знаковом типе, и происходит переполнение, а потом приводится к беззнаковому. В C# гарантируется, что результат будет всегда правильный в этом случае?
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
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 битам.
Вот тут на вопрос почему кто-то еще беспокоится о платформах со странными особенностями (там правда не спрашивали про дополнительный код) в первом ответе приводят старую платформу, где не только числа представлены в обратном (а не в дополнительном) коде, но еще и размер одного байта равен 9 битам.
> Представляя число 123456789 в десятитысячной системе счисления, мы получаем сразу два преимущества: во-первых, сокращаем количество потребляемой памяти, так как вместо массива из 9 чисел нам достаточно хранить массив из 3 чисел (1, 2345 и 6789), во-вторых, значительно уменьшаем время выполнения стандартных операций над длинными числами, поскольку за раз обрабатываем 4 разряда числа.
ЛОЛШТО?!
ЗЫ. Еще П. Нортон в своей знаменитой Assembly Language for IBM PC в качестве разминки и закрепления материала показывал, как реализовать калькулятор, оперирующий десятичной целочисленной арифметикой без ограничения на разрядность чисел. 1986 год. А вы тут про дотнет. :D
ЛОЛШТО?!
ЗЫ. Еще П. Нортон в своей знаменитой 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 — выполняет модульное деление числа, возведенного в степень другого числа
ModPow — это операция "возведение в степень по модулю".
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Длинная арифметика от Microsoft