std.bigint

Арифметика произвольной точности ('bignum').

Производительность оптимизирована для чисел менее ~1000 десятичных разрядов. Для машин X86 используются высокооптимизированные ассемблерные подпрограммы.

В настоящее время реализованы следующие алгоритмы:

• Умножение Карацубы
• Возведение в квадрат оптимизировано независимо от умножения
• Деление "разделяй и властвуй"
• Бинарное возведение в степень

Лицензия:

Boost License 1.0.

Авторы:

Don Clugston

Источник

std/bigint.d

struct BigInt;

Структура, представляющая целое число произвольной точности.

Поддерживаются все арифметические операции, за исключением сдвига вправо без знака (>>>). Поддерживаются побитовые операции (|, &, ^, ~), и они ведут себя так, как если бы BigInt был числом со знаком дополнения до двух и бесконечной длины.

BigInt реализует семантику значений с копированием при записи. Это означает, что присваивание выполняется быстро, но операции, такие как x++, приведут к выделению памяти. (Однако обратите внимание, что для большинства операций bigint выделение памяти неизбежно.)

Примеры:

BigInt a = "9588669891916142";
BigInt b = "7452469135154800";
auto c = a * b;
writeln(c); // BigInt("71459266416693160362545788781600")
auto d = b * a;
writeln(d); // BigInt("71459266416693160362545788781600")
writeln(d); // c
d = c * BigInt("794628672112");
writeln(d); // BigInt("56783581982794522489042432639320434378739200")
auto e = c + d;
writeln(e); // BigInt("56783581982865981755459125799682980167520800")
auto f = d + c;
writeln(f); // e
auto g = f - c;
writeln(g); // d
g = f - d;
writeln(g); // c
e = 12345678;
g = c + e;
auto h = g / b;
auto i = g % b;
writeln(h); // a
writeln(i); // e
BigInt j = "-0x9A56_57f4_7B83_AB78";
BigInt k = j;
j ^^= 11;
writeln(k^^11); // j

this(Range)(Range s)
Constraints: if (isBidirectionalRange!Range && isSomeChar!(ElementType!Range) && !isInfinite!Range && !isNarrowString!Range);

pure this(Range)(Range s)
Constraints: if (isNarrowString!Range);

Создать BigInt из десятичной или шестнадцатеричной строки. Число должно быть представлено в виде десятичной или шестнадцатеричной литералы. Оно может иметь ведущий + или - знак, за которым следуют 0x или 0X в случае шестнадцатеричного представления. Подчеркивания разрешены в любом месте после 0x и/или знака числа.

Параметры:

Range s

конечный двунаправленный диапазон любого типа символов

Исключения:

std.conv.ConvException если строка не представляет допустимое число

this(Range)(bool isNegative, Range magnitude)
Constraints: if (isInputRange!Range && isUnsigned!(ElementType!Range) && (hasLength!Range || isForwardRange!Range) && !isInfinite!Range);

Создать BigInt из знака и абсолютного значения.

Абсолютное значение — это входной диапазон беззнаковых целых чисел, удовлетворяющий либо std.range.primitives.hasLength, либо std.range.primitives.isForwardRange. Первый (самый левый) элемент абсолютного значения рассматривается как наиболее значимый.

Параметры:

bool isNegative	true для отрицательного, false для неотрицательного (игнорируется, когда абсолютное значение равно нулю)
Range magnitude	конечный диапазон беззнаковых целых чисел

Примеры:

ubyte[] magnitude = [1, 2, 3, 4, 5, 6];
auto b1 = BigInt(false, magnitude);
writeln(cast(long)b1); // 0x01_02_03_04_05_06L
auto b2 = BigInt(true, magnitude);
writeln(cast(long)b2); // -0x01_02_03_04_05_06L

pure nothrow @safe this(T)(T x)
Constraints: if (isIntegral!T);

Создать BigInt из встроенного целого типа.

Примеры:

ulong data = 1_000_000_000_000;
auto bigData = BigInt(data);
writeln(bigData); // BigInt("1_000_000_000_000")

pure nothrow @safe this(T)(T x)
Constraints: if (is(immutable(T) == immutable(BigInt)));

Создать BigInt из другого BigInt.

Примеры:

const(BigInt) b1 = BigInt("1_234_567_890");
BigInt b2 = BigInt(b1);
writeln(b2); // BigInt("1_234_567_890")

pure nothrow @safe BigInt opAssign(T)(T x)
Constraints: if (isIntegral!T);

Присваивание из встроенных целочисленных типов.

Примеры:

auto b = BigInt("123");
b = 456;
writeln(b); // BigInt("456")

pure @nogc @safe BigInt opAssign(T : BigInt)(T x);

Присваивание из другого BigInt.

Примеры:

auto b1 = BigInt("123");
auto b2 = BigInt("456");
b2 = b1;
writeln(b2); // BigInt("123")

pure nothrow @safe BigInt opOpAssign(string op, T)(T y)
Constraints: if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == ">>" || op == "<<" || op == "^^" || op == "|" || op == "&" || op == "^") && isIntegral!T);

Реализует операторы присваивания от встроенных целых чисел вида BigInt op= integer.

Примеры:

auto b = BigInt("1_000_000_000");

b += 12345;
writeln(b); // BigInt("1_000_012_345")

b /= 5;
writeln(b); // BigInt("200_002_469")

pure nothrow @safe BigInt opOpAssign(string op, T)(T y)
Constraints: if ((op == "+" || op == "-" || op == "*" || op == "|" || op == "&" || op == "^" || op == "/" || op == "%") && is(T : BigInt));

Реализует операторы присваивания вида BigInt op= BigInt.

Примеры:

auto x = BigInt("123");
auto y = BigInt("321");
x += y;
writeln(x); // BigInt("444")

const pure nothrow @safe BigInt opBinary(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "-" || op == "|" || op == "&" || op == "^" || op == "/" || op == "%") && is(T : BigInt));

Реализует бинарные операторы между BigInt.

Примеры:

auto x = BigInt("123");
auto y = BigInt("456");
BigInt z = x * y;
writeln(z); // BigInt("56088")

const pure nothrow @safe BigInt opBinary(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "-" || op == "/" || op == "|" || op == "&" || op == "^" || op == ">>" || op == "<<" || op == "^^") && isIntegral!T);

Реализует бинарные операторы между BigInt и встроенными целыми числами.

Примеры:

auto x = BigInt("123");
x *= 300;
writeln(x); // BigInt("36900")

const pure nothrow @safe auto opBinary(string op, T)(T y)
Constraints: if (op == "%" && isIntegral!T);

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

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

BigInt	%	uint	→	long
BigInt	%	long	→	long
BigInt	%	ulong	→	BigInt
BigInt	%	другой тип	→	int

Примеры:

auto  x  = BigInt("1_000_000_500");
long  l  = 1_000_000L;
ulong ul = 2_000_000UL;
int   i  = 500_000;
short s  = 30_000;

assert(is(typeof(x % l)  == long)   && x % l  == 500L);
assert(is(typeof(x % ul) == BigInt) && x % ul == BigInt(500));
assert(is(typeof(x % i)  == int)    && x % i  == 500);
assert(is(typeof(x % s)  == int)    && x % s  == 10500);

const pure nothrow @safe BigInt opBinaryRight(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T);

const pure nothrow @safe BigInt opBinaryRight(string op, T)(T y)
Constraints: if (op == "-" && isIntegral!T);

const pure nothrow @safe T opBinaryRight(string op, T)(T x)
Constraints: if ((op == "%" || op == "/") && isIntegral!T);

Реализует операторы со встроенными целыми числами слева и BigInt справа.

Примеры:

auto x = BigInt("100");
BigInt y = 123 + x;
writeln(y); // BigInt("223")

BigInt z = 123 - x;
writeln(z); // BigInt("23")

// Dividing a built-in integer type by BigInt always results in
// something that fits in a built-in type, so the built-in type is
// returned, not BigInt.
assert(is(typeof(1000 / x) == int));
writeln(1000 / x); // 10

const pure nothrow @safe BigInt opUnary(string op)()
Constraints: if (op == "+" || op == "-" || op == "~");

pure nothrow @safe BigInt opUnary(string op)()
Constraints: if (op == "++" || op == "--");

Реализует BigInt унарные операторы.

Примеры:

auto x = BigInt("1234");
writeln(-x); // BigInt("-1234")

++x;
writeln(x); // BigInt("1235")

const pure @nogc @safe bool opEquals()(auto ref const BigInt y);

const pure nothrow @nogc @safe bool opEquals(T)(const T y)
Constraints: if (isIntegral!T);

const nothrow @nogc bool opEquals(T)(const T y)
Constraints: if (isFloatingPoint!T);

Реализует проверку равенства BigInt с другими BigInt и встроенными числовыми типами.

Примеры:

// Note that when comparing a BigInt to a float or double the
// full precision of the BigInt is always considered, unlike
// when comparing an int to a float or a long to a double.
assert(BigInt(123456789) != cast(float) 123456789);

const pure nothrow @nogc @safe T opCast(T : bool)();

Реализует приведение к bool.

Примеры:

// Non-zero values are regarded as true
auto x = BigInt("1");
auto y = BigInt("10");
assert(x);
assert(y);

// Zero value is regarded as false
auto z = BigInt("0");
assert(!z);

const pure @safe T opCast(T : ulong)();

Реализует приведение к целочисленным типам.

Исключения:

std.conv.ConvOverflowException если число выходит за пределы диапазона целевого типа.

Примеры:

import std.conv : to, ConvOverflowException;
import std.exception : assertThrown;

writeln(BigInt("0").to!int); // 0

writeln(BigInt("0").to!ubyte); // 0
writeln(BigInt("255").to!ubyte); // 255
assertThrown!ConvOverflowException(BigInt("256").to!ubyte);
assertThrown!ConvOverflowException(BigInt("-1").to!ubyte);

const nothrow @nogc @safe T opCast(T)()
Constraints: if (isFloatingPoint!T);

Реализует приведение к типам с плавающей точкой.

Примеры:

writeln(0x1.abcd_e8p+124f); // cast(float)BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000")
// cast(double)BigInt("0x1abc_def1_2345_6000_0000_0000_0000_0000")
writeln(0x1.abcd_ef12_3456p+124);
// cast(real)BigInt("0x1abc_def1_2345_6000_0000_0000_0000_0000")
writeln(0x1.abcd_ef12_3456p+124L);

writeln(-0x1.3456_78p+108f); // cast(float)BigInt("-0x1345_6780_0000_0000_0000_0000_0000")
// cast(double)BigInt("-0x1345_678a_bcde_f000_0000_0000_0000")
writeln(-0x1.3456_78ab_cdefp+108);
// cast(real)BigInt("-0x1345_678a_bcde_f000_0000_0000_0000")
writeln(-0x1.3456_78ab_cdefp+108L);

Примеры:

Округление при приведении к типу с плавающей точкой

// BigInts whose values cannot be exactly represented as float/double/real
// are rounded when cast to float/double/real. When cast to float or
// double or 64-bit real the rounding is strictly defined. When cast
// to extended-precision real the rounding rules vary by environment.

// BigInts that fall somewhere between two non-infinite floats/doubles
// are rounded to the closer value when cast to float/double.
writeln(0x1.aaa_aaep+28f); // cast(float)BigInt(0x1aaa_aae7)
writeln(0x1.aaa_ab0p+28f); // cast(float)BigInt(0x1aaa_aaff)
writeln(-0x1.aaaaaep+28f); // cast(float)BigInt(-0x1aaa_aae7)
writeln(-0x1.aaaab0p+28f); // cast(float)BigInt(-0x1aaa_aaff)

writeln(0x1.aaa_aaaa_aaaa_aa00p+60); // cast(double)BigInt(0x1aaa_aaaa_aaaa_aa77)
writeln(0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(0x1aaa_aaaa_aaaa_aaff)
writeln(-0x1.aaa_aaaa_aaaa_aa00p+60); // cast(double)BigInt(-0x1aaa_aaaa_aaaa_aa77)
writeln(-0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(-0x1aaa_aaaa_aaaa_aaff)

// BigInts that fall exactly between two non-infinite floats/doubles
// are rounded away from zero when cast to float/double. (Note that
// in most environments this is NOT the same rounding rule rule used
// when casting int/long to float/double.)
writeln(0x1.aaa_ab0p+28f); // cast(float)BigInt(0x1aaa_aaf0)
writeln(-0x1.aaaab0p+28f); // cast(float)BigInt(-0x1aaa_aaf0)

writeln(0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(0x1aaa_aaaa_aaaa_aa80)
writeln(-0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(-0x1aaa_aaaa_aaaa_aa80)

// BigInts that are bounded on one side by the largest positive or
// most negative finite float/double and on the other side by infinity
// or -infinity are rounded as if in place of infinity was the value
// `2^^(T.max_exp)` when cast to float/double.
// cast(float)BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999")
writeln(float.infinity);
// cast(float)BigInt("-999_999_999_999_999_999_999_999_999_999_999_999_999")
writeln(-float.infinity);

assert(double.infinity > cast(double) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999"));
assert(real.infinity > cast(real) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999"));

const pure nothrow @nogc T opCast(T)()
Constraints: if (is(immutable(T) == immutable(BigInt)));

Реализует приведение к/от квалифицированных BigInt.

Предупреждение

Приведение к/от const или immutable может нарушить гарантии системы типов. Используйте с осторожностью.

Примеры:

const(BigInt) x = BigInt("123");
BigInt y = cast() x;    // cast away const
writeln(y); // x

const pure nothrow @nogc @safe int opCmp(ref const BigInt y);

const pure nothrow @nogc @safe int opCmp(T)(const T y)
Constraints: if (isIntegral!T);

const nothrow @nogc @safe int opCmp(T)(const T y)
Constraints: if (isFloatingPoint!T);

const pure nothrow @nogc @safe int opCmp(T : BigInt)(const T y);

Реализует сравнение BigInt с BigInt или BigInt со встроенными числовыми типами.

Примеры:

auto x = BigInt("100");
auto y = BigInt("10");
int z = 50;
const int w = 200;

assert(y < x);
assert(x > z);
assert(z > y);
assert(x < w);

Примеры:

auto x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
BigInt y = x - 1;
BigInt z = x + 1;

double d = 0x1.abcde8p124;
assert(y < d);
assert(z > d);
assert(x >= d && x <= d);

// Note that when comparing a BigInt to a float or double the
// full precision of the BigInt is always considered, unlike
// when comparing an int to a float or a long to a double.
assert(BigInt(123456789) < cast(float) 123456789);

const pure nothrow @nogc @safe long toLong();

Возвращает:

Значение этого BigInt как long, или long.max/long.min если оно выходит за пределы представимого диапазона.

Примеры:

auto b = BigInt("12345");
long l = b.toLong();
writeln(l); // 12345

const pure nothrow @nogc @safe int toInt();

Возвращает:

Значение этого BigInt как int, или int.max/int.min если оно выходит за пределы представимого диапазона.

Примеры:

auto big = BigInt("5_000_000");
auto i = big.toInt();
writeln(i); // 5_000_000

// Numbers that are too big to fit into an int will be clamped to int.max.
auto tooBig = BigInt("5_000_000_000");
i = tooBig.toInt();
writeln(i); // int.max

const pure nothrow @nogc @property @safe size_t uintLength();

Количество значащих uints, используемых для хранения этого числа. Абсолютное значение этого BigInt всегда меньше 2^{32*uintLength}

const pure nothrow @nogc @property @safe size_t ulongLength();

Количество значащих ulongs, используемых для хранения этого числа. Абсолютное значение этого BigInt всегда меньше 2^{64*ulongLength}

const void toString(Writer)(ref scope Writer sink, string formatString);

const void toString(Writer)(ref scope Writer sink, ref scope const FormatSpec!char f);

const void toString(scope void delegate(const(char)[]) sink, string formatString);

const void toString(scope void delegate(const(char)[]) sink, ref scope const FormatSpec!char f);

Преобразовать BigInt в string, передав его в указанный приемник.

Параметры:

Writer sink	Интерфейс вывода для приема, возможно, разнесенных фрагментов отформатированной строки.
string formatString	Строка формата, определяющая формат вывода. Доступные форматы вывода: "d" Десятичный "o" Восьмеричный "x" Шестнадцатеричный, строчные буквы "X" Шестнадцатеричный, заглавные буквы "s" Стандартный формат (такой же, как "d") null Стандартный формат (такой же, как "d")

Примеры:

toString редко вызывается напрямую; обычно для этого используется std.format.format:

import std.format : format;

auto x = BigInt("1_000_000");
x *= 12345;

writeln(format("%d", x)); // "12345000000"
writeln(format("%x", x)); // "2_dfd1c040"
writeln(format("%X", x)); // "2_DFD1C040"
writeln(format("%o", x)); // "133764340100"

const pure nothrow @nogc @safe size_t toHash();

Возвращает:

Уникальный хэш значения BigInt, подходящий для использования в таблице хеширования.

Примеры:

toHash редко вызывается напрямую; оно используется неявно, когда BigInt используется в качестве ключа ассоциативного массива.

string[BigInt] aa;
aa[BigInt(123)] = "abc";
aa[BigInt(456)] = "def";

writeln(aa[BigInt(123)]); // "abc"
writeln(aa[BigInt(456)]); // "def"

const T getDigit(T = ulong)(size_t n)
Constraints: if (is(T == ulong) || is(T == uint));

Получает n-е число в базовом представлении, составляющем всё BigInt.

Параметры:

T	тип для представления базового представления
size_t n	n-е число для извлечения. Должно быть меньше ulongLength или uintLength относительно T.

Возвращает:

n-е ulong в представлении этого BigInt.

Примеры:

auto a = BigInt("1000");
writeln(a.ulongLength()); // 1
writeln(a.getDigit(0)); // 1000

writeln(a.uintLength()); // 1
writeln(a.getDigit!uint(0)); // 1000

auto b = BigInt("2_000_000_000_000_000_000_000_000_000");
writeln(b.ulongLength()); // 2
writeln(b.getDigit(0)); // 4584946418820579328
writeln(b.getDigit(1)); // 108420217

writeln(b.uintLength()); // 3
writeln(b.getDigit!uint(0)); // 3489660928
writeln(b.getDigit!uint(1)); // 1067516025
writeln(b.getDigit!uint(2)); // 108420217

pure nothrow @safe string toDecimalString(const(BigInt) x);

Параметры:

const(BigInt) x

BigInt для преобразования в десятичное string.

Возвращает:

Строка, представляющая BigInt в виде десятичного числа.

Примеры:

auto x = BigInt("123");
x *= 1000;
x += 456;

auto xstr = x.toDecimalString();
writeln(xstr); // "123456"

@safe string toHex(const(BigInt) x);

Параметры:

const(BigInt) x

BigInt для преобразования в шестнадцатеричное string.

Возвращает:

Строка, представляющая BigInt в шестнадцатеричном (основание 16) виде с заглавными буквами.

Примеры:

auto x = BigInt("123");
x *= 1000;
x += 456;

auto xstr = x.toHex();
writeln(xstr); // "1E240"

Unsigned!T absUnsign(T)(T x)
Constraints: if (isIntegral!T);

Возвращает абсолютное значение x, преобразованное в соответствующий беззнаковый тип.

Параметры:

T x	Целочисленное значение, для которого требуется получить абсолютное значение.

Возвращает:

Абсолютное значение x.

Примеры:

writeln((-1).absUnsign); // 1
writeln(1.absUnsign); // 1

pure nothrow @safe void divMod(const BigInt dividend, const BigInt divisor, out BigInt quotient, out BigInt remainder);

Находит частное и остаток для данного делимого и делителя в одной операции.

Параметры:

BigInt dividend	BigInt для деления
BigInt divisor	BigInt для деления делимого
BigInt quotient	присваивается результат деления
BigInt remainder	присваивается остаток от деления

Примеры:

auto a = BigInt(123);
auto b = BigInt(25);
BigInt q, r;

divMod(a, b, q, r);

writeln(q); // 4
writeln(r); // 23
writeln(q * b + r); // a

pure nothrow @safe BigInt powmod(BigInt base, BigInt exponent, BigInt modulus);

Быстрое вычисление степени по модулю для операндов BigInt.

Параметры:

BigInt base	BigInt - базовые операнды.
BigInt exponent	BigInt - показатель степени основания.
BigInt modulus	BigInt - модуль для модулярного вычисления base ^ exponent.

Возвращает:

Значение степени по модулю (base ^ exponent) % modulus.

Примеры:

для powmod

BigInt base = BigInt("123456789012345678901234567890");
BigInt exponent = BigInt("1234567890123456789012345678901234567");
BigInt modulus = BigInt("1234567");

BigInt result = powmod(base, exponent, modulus);
writeln(result); // 359079