std.numeric

Этот модуль является портом фрагмента заголовка numeric из стандартной библиотеки шаблонов Александра Степанова (Standard Template Library) с несколькими дополнениями.

Лицензия:

Лицензия Boost 1.0.

Авторы:

Андрей Александреску, Дон Клугстон, Роберт Жак, Илья Ярошенков

Источник

std/numeric.d

перечисление CustomFloatFlags: int;

Флаги формата для CustomFloat.

signed

Добавляет бит знака для поддержки знаковых чисел.

storeNormalized

По умолчанию хранить значения в нормализованной форме. Фактическая точность мантиссы увеличивается на 1 бит, предполагая неявный старший бит 1 вместо 0. т.е. 1.nnnn вместо 0.nnnn. Действительно для всех типов IEE754

allowDenorm

Хранит мантиссу в денормализованной форме IEEE754, когда порядок равен 0. Необходима для представления значения 0.

infinity

Позволяет хранить значения бесконечности IEEE754.

nan

Позволяет хранить значения IEEE754 Not a Number.

probability

Если установлено, выбирает смещение порядка так, чтобы max_exp = 1. т.е. так, чтобы максимальное значение было >= 1.0 и < 2.0. Игнорируется, если смещение порядка указано вручную.

negativeUnsigned

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

allowDenormZeroOnly

Если установлено, 0 - единственное допустимое денормализованное число IEEE754. Требует allowDenorm и storeNormalized.

ieee

Включает все варианты IEEE754.

none

Не включает ни одного из вышеперечисленных вариантов.

шаблон CustomFloat(uint bits) if (bits == 8 || bits == 16 || bits == 32 || bits == 64 || bits == 80)

шаблон CustomFloat(uint precision, uint exponentWidth, CustomFloatFlags flags = CustomFloatFlags.ieee) if (((flags & flags.signed) + precision + exponentWidth) % 8 == 0 && (precision + exponentWidth > 0))

структура CustomFloat(uint precision, uint exponentWidth, CustomFloatFlags flags, uint bias) if (isCorrectCustomFloat(precision, exponentWidth, flags));

Позволяет коду пользователя определять пользовательские форматы чисел с плавающей точкой. Эти форматы предназначены только для хранения; все операции над ними выполняются путём неявного преобразования в real сначала. После завершения операции результат может быть сохранён в значении пользовательской плавающей точки путём присваивания.

Примеры:

import std.math : sin, cos;

// Define a 16-bit floating point values
CustomFloat!16                                x;     // Using the number of bits
CustomFloat!(10, 5)                           y;     // Using the precision and exponent width
CustomFloat!(10, 5,CustomFloatFlags.ieee)     z;     // Using the precision, exponent width and format flags
CustomFloat!(10, 5,CustomFloatFlags.ieee, 15) w;     // Using the precision, exponent width, format flags and exponent offset bias

// Use the 16-bit floats mostly like normal numbers
w = x*y - 1;

// Functions calls require conversion
z = sin(+x)           + cos(+y);                     // Use unary plus to concisely convert to a real
z = sin(x.get!float)  + cos(y.get!float);            // Or use get!T
z = sin(cast(float) x) + cos(cast(float) y);           // Or use cast(T) to explicitly convert

// Define a 8-bit custom float for storing probabilities
alias Probability = CustomFloat!(4, 4, CustomFloatFlags.ieee^CustomFloatFlags.probability^CustomFloatFlags.signed );
auto p = Probability(0.5);

шаблон FPTemporary(F) if (isFloatingPoint!F)

Определяет самый быстрый тип для хранения временных значений вычисления, предназначенного в конечном итоге для получения результата типа F (где F должно быть одним из float, double, или real). При выполнении многоступенчатого вычисления вы можете хранить промежуточные результаты как FPTemporary!F.

Необходимость в FPTemporary вытекает из оптимизированных операций с плавающей точкой и регистров, присутствующих практически во всех процессорах. При сложении чисел в примере, сложение фактически может выполняться в real точности внутри. В этом случае, хранение промежуточных result в double format не только менее точно, но и (удивительно) медленнее, поскольку преобразование из real в double выполняется в каждом проходе цикла. Поскольку это проигрышная ситуация, FPTemporary!F определён как самый быстрый тип для вычислений с точностью F. Нет необходимости определять тип для самых точных вычислений, поскольку это всегда real.

Наконец, нет гарантии, что использование FPTemporary!F всегда будет самым быстрым, так как скорость вычислений с плавающей точкой зависит от очень многих факторов.

Примеры:

import std.math : approxEqual;

// Average numbers in an array
double avg(in double[] a)
{
    if (a.length == 0) return 0;
    FPTemporary!double result = 0;
    foreach (e; a) result += e;
    return result / a.length;
}

auto a = [1.0, 2.0, 3.0];
assert(approxEqual(avg(a), 2));

шаблон secantMethod(alias fun)

Реализует метод секущих для нахождения корня функции fun, начиная с точек [xn_1, x_n] (желательно близких к корню). Num может быть float, double, или real.

Примеры:

import std.math : approxEqual, cos;

float f(float x)
{
    return cos(x) - x*x*x;
}
auto x = secantMethod!(f)(0f, 1f);
assert(approxEqual(x, 0.865474));

T findRoot(T, DF, DT)(scope DF f, const T a, const T b, scope DT tolerance)
Ограничения: if (isFloatingPoint!T && is(typeof(tolerance(T.init, T.init)) : bool) && is(typeof(f(T.init)) == R, R) && isFloatingPoint!R);

T findRoot(T, DF)(scope DF f, const T a, const T b);

Находит действительный корень действительной функции f(x) с помощью отсечения.

Учитывая функцию f и диапазон [a .. b] такой, что f(a) и f(b) имеют противоположные знаки или хотя бы одно из них равно ±0, возвращает значение x в диапазоне, которое наиболее близко к корню f(x). Если f(x) имеет более одного корня в диапазоне, один выбирается произвольно. Если f(x) возвращает NaN, возвращается NaN; в противном случае этот алгоритм гарантированно выполняется.

Использует алгоритм, основанный на TOMS748, который использует обратную кубическую интерполяцию, когда это возможно, в противном случае возвращается к параболической или секущей интерполяции. По сравнению с TOMS748, эта реализация улучшает производительность в худшем случае более чем в 100 раз, а типичную производительность - в 2 раза. Для 80-битных вещественных чисел для достижения полной машинной точности большинство проблем требуют от 8 до 15 вызовов f(x). Худшая производительность (патологические случаи) приблизительно вдвое превышает количество битов.

Ссылки

"On Enclosing Simple Roots of Nonlinear Equations", G. Alefeld, F.A. Potra, Yixun Shi, Mathematics of Computation 61, pp733-744 (1993). Исходный код Fortran доступен на www.netlib.org в качестве алгоритма TOMS478.

Кортеж!(T, T, R, R) findRoot(T, R, DF, DT)(scope DF f, const T ax, const T bx, const R fax, const R fbx, scope DT tolerance)
Ограничения: if (isFloatingPoint!T && is(typeof(tolerance(T.init, T.init)) : bool) && is(typeof(f(T.init)) == R) && isFloatingPoint!R);

Кортеж!(T, T, R, R) findRoot(T, R, DF)(scope DF f, const T ax, const T bx, const R fax, const R fbx);

T findRoot(T, R)(scope R delegate(T) f, const T a, const T b, scope bool delegate(T lo, T hi) tolerance = (T a, T b) => false);

Находит корень действительной функции f(x) с помощью отсечения, позволяя указать условие завершения.

Параметры:

DF f	Функция для анализа
T ax	Левая граница начального интервала f известного, содержащего корень.
T bx	Правая граница начального интервала f известного, содержащего корень.
R fax	Значение f(ax).
R fbx	Значение f(bx). fax и fbx должны иметь противоположные знаки. (f(ax) и f(bx) обычно известны заранее.)
DT tolerance	Определяет условие раннего завершения. Получает текущие верхнюю и нижнюю границы корня. Делегат должен вернуть true когда эти границы приемлемы. Если эта функция всегда возвращает false, будет достигнута полная машинная точность.

Возвращает:

Кортеж, состоящий из двух диапазонов. Первые два элемента — это диапазон (в x) корня, а вторая пара элементов — соответствующие значения функции в этих точках. Если был найден точный корень, оба первых элемента будут содержать корень, а вторая пара элементов будет равна 0.

Кортеж!(T, "x", Unqual!(ReturnType!DF), "y", T, "error") findLocalMin(T, DF)(scope DF f, const T ax, const T bx, const T relTolerance = sqrt(T.epsilon), const T absTolerance = sqrt(T.epsilon))
Ограничения: if (isFloatingPoint!T && __traits(compiles, () { T _ = DF.init(T.init); } ));

Найдите реальный минимум вещественной функции f(x) с помощью метода отсечения. Учитывая функцию f и диапазон (ax .. bx), возвращает значение x в диапазоне, которое наиболее близко к минимуму f(x). f никогда не вычисляется в конечных точках ax и bx. Если у f(x) есть более одного минимума в диапазоне, один из них будет выбран произвольно. Если f(x) возвращает NaN или -Бесконечность, (x, f(x), NaN) будет возвращено; в противном случае, этот алгоритм гарантированно сработает.

Параметры:

DF f	Функция для анализа
T ax	Левая граница начального диапазона f, известного как содержащий минимум.
T bx	Правая граница начального диапазона f, известного как содержащий минимум.
T relTolerance	Относительная точность.
T absTolerance	Абсолютная точность.

Предпосылки

ax и bx должны быть конечными вещественными числами.
relTolerance должно быть нормальным положительным вещественным числом.
absTolerance должно быть нормальным положительным вещественным числом, не меньше T.epsilon*2.

Возвращает:

Кортеж, состоящий из x, y = f(x) и error = 3 * (absTolerance * fabs(x) + relTolerance). Используемый метод представляет собой комбинацию поиска по золотому сечению и последующей параболической интерполяции. Скорость сходимости никогда не будет значительно медленнее, чем для поиска Фибоначчи.

Ссылки

"Algorithms for Minimization without Derivatives", Richard Brent, Prentice-Hall, Inc. (1973)

См. также:

findRoot, std.math.isNormal

Примеры:

import std.math : approxEqual;

auto ret = findLocalMin((double x) => (x-4)^^2, -1e7, 1e7);
assert(ret.x.approxEqual(4.0));
assert(ret.y.approxEqual(0.0));

CommonType!(ElementType!Range1, ElementType!Range2) euclideanDistance(Range1, Range2)(Range1 a, Range2 b)
Constraints: if (isInputRange!Range1 && isInputRange!Range2);

CommonType!(ElementType!Range1, ElementType!Range2) euclideanDistance(Range1, Range2, F)(Range1 a, Range2 b, F limit)
Constraints: if (isInputRange!Range1 && isInputRange!Range2);

Вычисляет евклидово расстояние между входными диапазонами a и b. Две диапазона должны иметь одинаковую длину. В версии с тремя параметрами вычисление прекращается, как только расстояние станет больше или равно limit (это полезно для экономии вычислений, если требуется небольшое расстояние).

CommonType!(ElementType!Range1, ElementType!Range2) dotProduct(Range1, Range2)(Range1 a, Range2 b)
Constraints: if (isInputRange!Range1 && isInputRange!Range2 && !(isArray!Range1 && isArray!Range2));

CommonType!(F1, F2) dotProduct(F1, F2)(in F1[] avector, in F2[] bvector);

F dotProduct(F, uint N)(ref scope const F[N] a, ref scope const F[N] b)
Constraints: if (N <= 16);

Вычисляет скалярное произведение входных диапазонов a и b. Две диапазона должны иметь одинаковую длину. Если оба диапазона определяют длину, проверка выполняется один раз; в противном случае она выполняется на каждой итерации.

CommonType!(ElementType!Range1, ElementType!Range2) cosineSimilarity(Range1, Range2)(Range1 a, Range2 b)
Constraints: if (isInputRange!Range1 && isInputRange!Range2);

Вычисляет косинусное сходство входных диапазонов a и b. Две диапазона должны иметь одинаковую длину. Если оба диапазона определяют длину, проверка выполняется один раз; в противном случае она выполняется на каждой итерации. Если в любом диапазоне все элементы равны нулю, возвращается 0.

bool normalize(R)(R range, ElementType!R sum = 1)
Constraints: if (isForwardRange!R);

Нормализует значения в range путем умножения каждого элемента на число, выбранное таким образом, что сумма значений равна sum. Если сумма элементов в range равна нулю, всем элементам присваивается sum / range.length. Нормализация имеет смысл только в том случае, если все элементы в range положительны. normalize предполагает это, не проверяя.

Возвращает:

true если нормализация выполнена успешно, false если все элементы в range были равны нулю или если range пусто.

Примеры:

double[] a = [];
assert(!normalize(a));
a = [ 1.0, 3.0 ];
assert(normalize(a));
writeln(a); // [0.25, 0.75]
assert(normalize!(typeof(a))(a, 50)); // a = [12.5, 37.5]
a = [ 0.0, 0.0 ];
assert(!normalize(a));
writeln(a); // [0.5, 0.5]

ElementType!Range sumOfLog2s(Range)(Range r)
Constraints: if (isInputRange!Range && isFloatingPoint!(ElementType!Range));

Вычисляет сумму двоичных логарифмов входного диапазона r. Погрешность этого метода значительно меньше, чем при простом суммировании log2.

Примеры:

import std.math : isNaN;

writeln(sumOfLog2s(new double[0])); // 0
writeln(sumOfLog2s([0.0L])); // -real.infinity
writeln(sumOfLog2s([-0.0L])); // -real.infinity
writeln(sumOfLog2s([2.0L])); // 1
assert(sumOfLog2s([-2.0L]).isNaN());
assert(sumOfLog2s([real.nan]).isNaN());
assert(sumOfLog2s([-real.nan]).isNaN());
writeln(sumOfLog2s([real.infinity])); // real.infinity
assert(sumOfLog2s([-real.infinity]).isNaN());
writeln(sumOfLog2s([0.25, 0.25, 0.25, 0.125])); // -9

ElementType!Range entropy(Range)(Range r)
Constraints: if (isInputRange!Range);

ElementType!Range entropy(Range, F)(Range r, F max)
Constraints: if (isInputRange!Range && !is(CommonType!(ElementType!Range, F) == void));

Вычисляет энтропию входного диапазона r в битах. Эта функция предполагает (без проверки), что значения в r находятся в [0, 1]. Для того, чтобы энтропия имела смысл, часто необходимо также нормализовать r (т.е., значения должны суммироваться до 1). В версии с двумя параметрами вычисление прекращается, как только промежуточный результат становится больше или равен max.

CommonType!(ElementType!Range1, ElementType!Range2) kullbackLeiblerDivergence(Range1, Range2)(Range1 a, Range2 b)
Constraints: if (isInputRange!Range1 && isInputRange!Range2);

Вычисляет расхождение Кульбака-Лейблера между входными диапазонами a и b, которое является суммой ai * log(ai / bi). Основание логарифма равно 2. Предполагается, что диапазоны содержат элементы в [0, 1]. Обычно диапазоны представляют собой нормализованные распределения вероятностей, но это не является требованием и не проверяется kullbackLeiblerDivergence. Если любой элемент bi равен нулю, а соответствующий элемент ai отличен от нуля, возвращается бесконечность. (В противном случае, если ai == 0 && bi == 0, член ai * log(ai / bi) считается равным нулю.) Если входные данные нормализованы, результат положителен.

Примеры:

import std.math : approxEqual;

double[] p = [ 0.0, 0, 0, 1 ];
writeln(kullbackLeiblerDivergence(p, p)); // 0
double[] p1 = [ 0.25, 0.25, 0.25, 0.25 ];
writeln(kullbackLeiblerDivergence(p1, p1)); // 0
writeln(kullbackLeiblerDivergence(p, p1)); // 2
writeln(kullbackLeiblerDivergence(p1, p)); // double.infinity
double[] p2 = [ 0.2, 0.2, 0.2, 0.4 ];
assert(approxEqual(kullbackLeiblerDivergence(p1, p2), 0.0719281));
assert(approxEqual(kullbackLeiblerDivergence(p2, p1), 0.0780719));

CommonType!(ElementType!Range1, ElementType!Range2) jensenShannonDivergence(Range1, Range2)(Range1 a, Range2 b)
Constraints: if (isInputRange!Range1 && isInputRange!Range2 && is(CommonType!(ElementType!Range1, ElementType!Range2)));

CommonType!(ElementType!Range1, ElementType!Range2) jensenShannonDivergence(Range1, Range2, F)(Range1 a, Range2 b, F limit)
Constraints: if (isInputRange!Range1 && isInputRange!Range2 && is(typeof(CommonType!(ElementType!Range1, ElementType!Range2).init >= F.init) : bool));

Вычисляет расхождение Дженсена-Шеннона между a и b, которое является суммой (ai * log(2 * ai / (ai + bi)) + bi * log(2 * bi / (ai + bi))) / 2. Основание логарифма равно 2. Предполагается, что диапазоны содержат элементы в [0, 1]. Обычно диапазоны представляют собой нормализованные распределения вероятностей, но это не является требованием и не проверяется jensenShannonDivergence. Если входные данные нормализованы, результат ограничен [0, 1]. Версия с тремя параметрами прекращает вычисления, как только промежуточный результат становится больше или равен limit.

Примеры:

import std.math : approxEqual;

double[] p = [ 0.0, 0, 0, 1 ];
writeln(jensenShannonDivergence(p, p)); // 0
double[] p1 = [ 0.25, 0.25, 0.25, 0.25 ];
writeln(jensenShannonDivergence(p1, p1)); // 0
assert(approxEqual(jensenShannonDivergence(p1, p), 0.548795));
double[] p2 = [ 0.2, 0.2, 0.2, 0.4 ];
assert(approxEqual(jensenShannonDivergence(p1, p2), 0.0186218));
assert(approxEqual(jensenShannonDivergence(p2, p1), 0.0186218));
assert(approxEqual(jensenShannonDivergence(p2, p1, 0.005), 0.00602366));

F gapWeightedSimilarity(alias comp = "a == b", R1, R2, F)(R1 s, R2 t, F lambda)
Constraints: if (isRandomAccessRange!R1 && hasLength!R1 && isRandomAccessRange!R2 && hasLength!R2);

Так называемый «ядро строк с взвешенными пропуском всех длин» вычисляет меру сходства между s и t на основе всех их общих подпоследовательностей всех длин. Также включаются подпоследовательности с пропусками.

Чтобы понять, что вычисляет gapWeightedSimilarity(s, t, lambda), сначала рассмотрим случай lambda = 1 и строки s = ["Hello", "brave", "new", "world"] и t = ["Hello", "new", "world"]. В этом случае gapWeightedSimilarity подсчитывает следующие совпадения:

1. три совпадения длины 1, а именно "Hello", "new", и "world";
2. три совпадения длины 2, а именно ("Hello", "new"), ("Hello", "world"), и ("new", "world");
3. одно совпадение длины 3, а именно ("Hello", "new", "world").

Вызов gapWeightedSimilarity(s, t, 1) просто подсчитывает все эти совпадения и складывает их, возвращая 7.

string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
assert(gapWeightedSimilarity(s, t, 1) == 7);

Обратите внимание, как пропуски в совпадениях просто игнорируются, например ("Hello", "new") считается таким же хорошим совпадением, как ("new", "world"). Это может быть слишком либерально для некоторых применений. Чтобы полностью исключить совпадения с пропусками, используйте lambda = 0:

string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
assert(gapWeightedSimilarity(s, t, 0) == 4);

Вышеприведённый вызов исключил совпадения с пропусками ("Hello", "new"), ("Hello", "world"), и ("Hello", "new", "world") из подсчёта. Это оставляет только 4 совпадения.

Наиболее интересный случай — когда совпадения с пропусками всё ещё участвуют в результате, но не так сильно, как совпадения без пропусков. Результатом будет плавная, мелкозернистая мера сходства между входными строками. Здесь вступают в игру значения lambda между 0 и 1: совпадения с пропусками экспоненциально штрафуются по количеству пропусков с основанием lambda. Это означает, что совпадение без пропусков добавляет 1 к возвращаемому значению; совпадение с одним пробелом в одной из строк добавляет lambda к возвращаемому значению; ...; совпадение с общим числом n пробелов в обеих строках добавляет pow(lambda, n) к возвращаемому значению. В примере выше у нас есть 4 совпадения без пропусков, 2 совпадения с одним пробелом и 1 совпадение с тремя пробелами. Последнее совпадение ("Hello", "world") имеет два пробела в первой строке и один пробел во второй строке, в общей сложности три пробела. Суммируя это, получаем 4 + 2 * lambda + pow(lambda, 3).

string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
assert(gapWeightedSimilarity(s, t, 0.5) == 4 + 0.5 * 2 + 0.125);

gapWeightedSimilarity полезно везде, где необходима плавная мера сходства между последовательностями, допускающая приближённые совпадения. Примеры выше приведены со словами, но допускаются любые последовательности с элементами, сравнимыми по равенству, например, символы или числа. gapWeightedSimilarity использует высокооптимизированную реализацию динамического программирования, которая требует 16 * min(s.length, t.length) дополнительных байтов памяти и Ο(s.length * t.length) времени для завершения.

Select!(isFloatingPoint!F, F, double) gapWeightedSimilarityNormalized(alias comp = "a == b", R1, R2, F)(R1 s, R2 t, F lambda, F sSelfSim = F.init, F tSelfSim = F.init)
Constraints: if (isRandomAccessRange!R1 && hasLength!R1 && isRandomAccessRange!R2 && hasLength!R2);

Мера сходства по gapWeightedSimilarity имеет проблему, заключающуюся в том, что она растёт с длиной двух строк, даже если строки на самом деле не очень похожи. Например, диапазон ["Hello", "world"] всё больше похож на диапазон ["Hello", "world", "world", "world",...] по мере добавления большего количества экземпляров "world". Чтобы предотвратить это, gapWeightedSimilarityNormalized вычисляет нормализованную версию сходства, вычисляемую как gapWeightedSimilarity(s, t, lambda) / sqrt(gapWeightedSimilarity(s, t, lambda) * gapWeightedSimilarity(s, t, lambda)). Функция gapWeightedSimilarityNormalized (так называемое нормализованное ядро) ограничена [0, 1], достигает 0 только для диапазонов, не совпадающих ни в одной позиции, и 1 только для идентичных диапазонов.

Дополнительные параметры sSelfSim и tSelfSim предназначены для избежания дублирования вычислений. Многие приложения могут уже вычислить gapWeightedSimilarity(s, s, lambda) и/или gapWeightedSimilarity(t, t, lambda). В этом случае они могут быть переданы как sSelfSim и tSelfSim соответственно.

Примеры:

import std.math : approxEqual, sqrt;

string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
writeln(gapWeightedSimilarity(s, s, 1)); // 15
writeln(gapWeightedSimilarity(t, t, 1)); // 7
writeln(gapWeightedSimilarity(s, t, 1)); // 7
assert(approxEqual(gapWeightedSimilarityNormalized(s, t, 1),
                7.0 / sqrt(15.0 * 7), 0.01));

struct GapWeightedSimilarityIncremental(Range, F = double) if (isRandomAccessRange!Range && hasLength!Range);

GapWeightedSimilarityIncremental!(R, F) gapWeightedSimilarityIncremental(R, F)(R r1, R r2, F penalty);

Аналогично gapWeightedSimilarity, но работает инкрементальным образом, сначала раскрывая совпадения длины 1, затем совпадения с пропусками длины 2 и так далее. Требование к памяти составляет Ο(s.length * t.length). Время выполнения составляет Ο(s.length * t.length) для вычисления каждого шага. Продолжая предыдущий пример:

Реализация основана на псевдокоде на рис. 4 статьи "Efficient Computation of Gapped Substring Kernels on Large Alphabets" Русу и др., с дополнительными алгоритмическими и системными оптимизациями.

Примеры:

string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
auto simIter = gapWeightedSimilarityIncremental(s, t, 1.0);
assert(simIter.front == 3); // three 1-length matches
simIter.popFront();
assert(simIter.front == 3); // three 2-length matches
simIter.popFront();
assert(simIter.front == 1); // one 3-length match
simIter.popFront();
assert(simIter.empty);     // no more match

this(Range s, Range t, F lambda);

Создаёт объект, заданный двумя диапазонами s и t и штрафом lambda. Конструктор выполняется за Ο(s.length * t.length) времени и вычисляет все совпадения длины 1.

ref GapWeightedSimilarityIncremental opSlice();

Возвращает:

this.

void popFront();

Вычисляет совпадение длины popFront. Выполняется за Ο(s.length * t.length) времени.

@property F front();

Возвращает:

Сходство с пропусками на текущей длине совпадения (изначально 1, увеличивается с каждым вызовом popFront).

@property bool empty();

Возвращает:

Является ли список пустым (нет больше совпадений).

T gcd(T)(T a, T b)
Constraints: if (isIntegral!T);

auto gcd(T)(T a, T b)
Constraints: if (!isIntegral!T && is(typeof(T.init % T.init)) && is(typeof(T.init == 0 || T.init > 0)));

Вычисляет наибольший общий делитель a и b с помощью эффективного алгоритма, такого как алгоритм Евклида или алгоритм Штейна.

Параметры:

T	Любой числовой тип, поддерживающий оператор взятия остатка %. Если также поддерживаются сдвиги битов << и >>, будет использован алгоритм Штейна; в противном случае используется алгоритм Евклида как резервный вариант.

Возвращает:

Наибольший общий делитель заданных аргументов.

Примеры:

writeln(gcd(2 * 5 * 7 * 7, 5 * 7 * 11)); // 5 * 7
const int a = 5 * 13 * 23 * 23, b = 13 * 59;
writeln(gcd(a, b)); // 13

class Fft;

Класс для выполнения быстрых преобразований Фурье для размеров, являющихся степенями двойки. Этот класс инкапсулирует большое количество состояния, которое можно повторно использовать при выполнении нескольких БПФ с размерами, меньшими или равными размеру, указанному в конструкторе. Это приводит к значительному ускорению при выполнении нескольких БПФ с известным максимальным размером. Однако для удобства предоставляется API свободной функции, если вам нужно выполнить однократное БПФ.

Ссылки

en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

this(size_t size);

Создает объект Fft для вычисления быстрых преобразований Фурье для размеров, являющихся степенями двойки, размером size или меньше. size должно быть степенью двойки.

const Complex!F[] fft(F = double, R)(R range)
Constraints: if (isFloatingPoint!F && isRandomAccessRange!R);

Вычисляет преобразование Фурье диапазона с использованием алгоритма Кули-Туки Ο(N log N). range должен быть диапазоном произвольного доступа с разбиением и длиной, равной size, как указано при создании этого объекта. Содержимое диапазона может быть числовых типов, которые будут интерпретироваться как чисто вещественные значения, или комплексных типов с свойствами или членами .re и .im, которые могут быть прочитаны.

Примечание

Чисто вещественные БПФ автоматически обнаруживаются, и выполняются соответствующие оптимизации.

Возвращает:

Массив комплексных чисел, представляющих преобразованные данные в частотной области.

Соглашения

Показатель степени отрицательный, а множитель равен единице, т.е., output[j] := sum[ exp(-2 PI i j k / N) input[k] ].

const void fft(Ret, R)(R range, Ret buf)
Constraints: if (isRandomAccessRange!Ret && isComplexLike!(ElementType!Ret) && hasSlicing!Ret);

То же, что и перегрузка, но позволяет хранить результаты в предоставленном пользователем буфере. Буфер должен иметь ту же длину, что и диапазон, должен быть диапазоном произвольного доступа, должен иметь разбиение и должен содержать элементы, которые являются комплексноподобными. Это означает, что они должны иметь член или свойство .re и .im, которые можно как читать, так и записывать, и которые являются числами с плавающей запятой.

const Complex!F[] inverseFft(F = double, R)(R range)
Constraints: if (isRandomAccessRange!R && isComplexLike!(ElementType!R) && isFloatingPoint!F);

Вычисляет обратное преобразование Фурье диапазона. Диапазон должен быть диапазоном произвольного доступа с разбиением, иметь длину, равную размеру, указанному при создании этого объекта, и содержать элементы, которые являются либо типа std.complex.Complex, либо имеют по существу тот же интерфейс времени компиляции.

Возвращает:

Сигнал во временной области.

Соглашения

Показатель степени положительный, а множитель равен 1/N, т.е., output[j] := (1 / N) sum[ exp(+2 PI i j k / N) input[k] ].

const void inverseFft(Ret, R)(R range, Ret buf)
Constraints: if (isRandomAccessRange!Ret && isComplexLike!(ElementType!Ret) && hasSlicing!Ret);

Обратное БПФ, которое позволяет предоставить буфер, указанный пользователем. Буфер должен быть диапазоном произвольного доступа с разбиением, а его элементы должны быть каким-либо комплексноподобным типом.

Complex!F[] fft(F = double, R)(R range);

void fft(Ret, R)(R range, Ret buf);

Complex!F[] inverseFft(F = double, R)(R range);

void inverseFft(Ret, R)(R range, Ret buf);

Функции для удобства создания объекта Fft, выполнения БПФ или обратного БПФ и возврата результата. Полезно для однократных БПФ.

Примечание

В дополнение к удобству эти функции немного эффективнее, чем ручное создание объекта Fft для однократного использования, поскольку объект Fft детерминированно уничтожается до возврата этих функций.

pure nothrow @nogc @safe size_t decimalToFactorial(ulong decimal, ref ubyte[21] fac);

Эта функция преобразует значение decimal в значение в системе счисления факториалов, хранящееся в fac.

Факториальное число строится как: fac[0] * 0! + fac[1] * 1! + ... fac[20] * 20!

Параметры:

ulong decimal	Значение в десятичной системе счисления, которое нужно преобразовать в факториальную систему счисления.
ubyte[21] fac	Массив для хранения факториального числа. Размер массива составляет 21, так как ulong.max требует 21 цифру в факториальной системе счисления.

Возвращает:

Переменная, хранящая количество цифр факториального числа, хранящегося в fac.

Примеры:

ubyte[21] fac;
size_t idx = decimalToFactorial(2982, fac);

writeln(fac[0]); // 4
writeln(fac[1]); // 0
writeln(fac[2]); // 4
writeln(fac[3]); // 1
writeln(fac[4]); // 0
writeln(fac[5]); // 0
writeln(fac[6]); // 0