В этом скромном рецепте мы покажем вам самописный алгоритм для работы с числами с BigInt из std.bigint, который тем не менее, может пригодиться вам при работе с некоторыми приложениями арифметики больших чисел.
Как ни странно, стандартная библиотека D содержит достаточно минималистичный набор операций с числами BigInt, а для по-настоящему больших чисел документация из стандартной библиотеки D предлагает использовать сторонние библиотеки, к примеру, GMP. Также, если вы ожидали генерировать большие числа (в данном случае, имеются в виду только целые числа с большим количеством цифр), используя генераторы случайных из std.random, то тут вас ждет разочарование: с типом BigInt, несмотря на всю шаблонную магию, функции наподобие uniform не работают.
Вы удивитесь, но в std.random тоже нет функционала для создания достаточно случайного числа, и потому, алгоритм для этой цели нам пришлось писать самостоятельно. Самый банальный вариант для создания случайного большого числа — это случайным образом отбирать его цифры и проверять на попадание сконструированного числа в диапазон от нуля до некоторого n.
Но, это заведомо проигрышный вариант, поскольку в std.bigint для типа BigInt предусмотрен вариант сборки числа из некоторого массива байтов, а отдельного метода по сборке из цифр — нет (кроме как напрямую упомянуть строку цифр собираемого числа). Однако, это не мешает почти никак: в нашем алгоритме мы будем использовать сборку числа из байтов, генерируя байты случайным образом и для этого важен только один нюанс — сколько байтов нужно сгенерировать.
Ответить на данный вопрос достаточно просто: фактически, нужно столько же байтов, сколько в принципе содержится в числе n. На самом деле, нужно не больше того количества байтов, которое содержится в числе n (меньше или равно количеству байтов в n), однако, ради упрощения алгоритма мы будем считать, что количества байтов в n и свежесгенерированном числе равные. Простейшее усовершенствование мы оставляем как упражнение читателю.
План прост: узнаем количество байтов в числе n, генерируем целый массив случайных байтов, размерность которого будет равна количеству байтов в n. Далее из массива байтов конструируем BigInt и проверяем его вхождение в диапазон от (0; n) — и если число не попало в этот диапазон, то повторяем описанные шаги.
Реализуется это так:
import std.bigint;
alias BigInteger = BigInt;
auto randomBigInteger(BigInteger b)
{
BigInteger result = "0";
auto countOfBytes(BigInteger number)
{
ulong count = 0;
while (number != 0)
{
number >>= 8;
count++;
}
return count;
}
auto generateRandomBytes(ulong number)
{
auto rng = Random(unpredictableSeed);
ubyte[] r;
foreach (e; 0..number)
{
r ~= cast(ubyte) uniform(0, 256, rng);
}
return r;
}
auto numberOfBytes = countOfBytes(b);
auto isInRange(BigInteger number)
{
return ((number < b) && (number > 0));
}
while (!isInRange(result))
{
ubyte[] magnitude = generateRandomBytes(numberOfBytes);
result = BigInteger(false, magnitude);
}
return result;
}Некоторые пояснения: реализовано тут все так, как и указано выше, однако, мы не упомянули, про особенность конструктора BigInt— этот конструктор принимает булевый флаг, который обозначает знак числа, и набор байтов, которые представляют само число. Эта особенность и используется в данном коде, остальной функционал в коде тривиален.
Рецепт прост, понятен, но тем не менее требует усовершенствований и может быть использован в некоторых интересных приложениях, о которых мы расскажем в одной из следующих статей.
На этом все.