This module is a port of a growing fragment of the numeric
header in Alexander Stepanov's Standard Template Library, with a few additions.
Format flags for CustomFloat.
Adds a sign bit to allow for signed
numbers.
Store values in normalized form by default. The actual precision of the significand is extended by 1 bit by assuming an implicit leading bit of 1 instead of 0. i.e. 1.nnnn
instead of 0.nnnn
. True for all IEE754 types
Stores the significand in IEEE754 denormalized form when the exponent is 0. Required to express the value 0.
Allows the storage of IEEE754 infinity values.
Allows the storage of IEEE754 Not a Number values.
If set, select an exponent bias such that max_exp = 1. i.e. so that the maximum value is >= 1.0 and < 2.0. Ignored if the exponent bias is manually specified.
If set, unsigned custom floats are assumed to be negative.
If set, 0 is the only allowed IEEE754 denormalized number. Requires allowDenorm and storeNormalized.
Include all of the IEEE754 options.
Include none
of the above options.
Allows user code to define custom floating-point formats. These formats are for storage only; all operations on them are performed by first implicitly extracting them to real
first. After the operation is completed the result can be stored in a custom floating-point value via assignment.
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);
Defines the fastest type to use when storing temporaries of a calculation intended to ultimately yield a result of type F
(where F
must be one of float
, double
, or real
). When doing a multi-step computation, you may want to store intermediate results as FPTemporary!F
.
The necessity of FPTemporary
stems from the optimized floating-point operations and registers present in virtually all processors. When adding numbers in the example above, the addition may in fact be done in real
precision internally. In that case, storing the intermediate result
in double format
is not only less precise, it is also (surprisingly) slower, because a conversion from real
to double
is performed every pass through the loop. This being a lose-lose situation, FPTemporary!F
has been defined as the fastest type to use for calculations at precision F
. There is no need to define a type for the most accurate calculations, as that is always real
.
Finally, there is no guarantee that using FPTemporary!F
will always be fastest, as the speed of floating-point calculations depends on very many factors.
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));
Implements the secant method for finding a root of the function fun
starting from points [xn_1, x_n]
(ideally close to the root). Num
may be float
, double
, or 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));
Find a
real root of a
real function f
(x) via bracketing.
Given a
function f
and a
range [a .. b]
such that f(a)
and f(b)
have opposite signs or at least one of them equals ±0, returns the value of x
in the range which is closest to a
root of f(x)
. If f(x)
has more than one root in the range, one will be chosen arbitrarily. If f(x)
returns NaN, NaN will be returned; otherwise, this algorithm is guaranteed to succeed.
Uses an algorithm based on TOMS748, which uses inverse cubic interpolation whenever possible, otherwise reverting to parabolic or secant interpolation. Compared to TOMS748, this implementation improves worst-case performance by a
factor of more than 100, and typical performance by a
factor of 2. For 80-bit reals, most problems require 8 to 15 calls to f(x)
to achieve full machine precision. The worst-case performance (pathological cases) is approximately twice the number of bits.
Find root of a
real function f
(x) by bracketing, allowing the termination condition to be specified.
DF f
| Function to be analyzed |
T ax
| Left bound of initial range of f known to contain the root. |
T bx
| Right bound of initial range of f known to contain the root. |
R fax
| Value of f(ax) . |
R fbx
| Value of f(bx) . fax and fbx should have opposite signs. (f(ax) and f(bx) are commonly known in advance.) |
DT tolerance
| Defines an early termination condition. Receives the current upper and lower bounds on the root. The delegate must return true when these bounds are acceptable. If this function always returns false , full machine precision will be achieved. |
x
) of the root, while the second pair of elements are the corresponding function values at those points. If an exact root was found, both of the first two elements will contain the root, and the second pair of elements will be 0.Find a real minimum of a real function f(x)
via bracketing. Given a function f
and a range (ax .. bx)
, returns the value of x
in the range which is closest to a minimum of f(x)
. f
is never evaluted at the endpoints of ax
and bx
. If f(x)
has more than one minimum in the range, one will be chosen arbitrarily. If f(x)
returns NaN or -Infinity, (x, f(x), NaN)
will be returned; otherwise, this algorithm is guaranteed to succeed.
DF f
| Function to be analyzed |
T ax
| Left bound of initial range of f known to contain the minimum. |
T bx
| Right bound of initial range of f known to contain the minimum. |
T relTolerance
| Relative tolerance. |
T absTolerance
| Absolute tolerance. |
ax
and bx
shall be finite reals. relTolerance
shall be normal positive real. absTolerance
shall be normal positive real no less then T.epsilon*2
. x
, y = f(x)
and error = 3 * (absTolerance * fabs(x) + relTolerance)
. The method used is a combination of golden section search and successive parabolic interpolation. Convergence is never much slower than that for a Fibonacci search. 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));
Computes Euclidean distance between input ranges a
and b
. The two ranges must have the same length. The three-parameter version stops computation as soon as the distance is greater than or equal to limit
(this is useful to save computation if a
small distance is sought).
Computes the dot product of input ranges a
and b
. The two ranges must have the same length. If both ranges define length, the check is done once; otherwise, it is done at each iteration.
Computes the cosine similarity of input ranges a
and b
. The two ranges must have the same length. If both ranges define length, the check is done once; otherwise, it is done at each iteration. If either range has all-zero elements, return 0.
Normalizes values in range
by multiplying each element with a number chosen such that values sum
up to sum
. If elements in range
sum
to zero, assigns sum / range.length
to all. Normalization makes sense only if all elements in range
are positive. normalize
assumes that is the case without checking it.
true
if normalization completed normally, false
if all elements in range
were zero or if range
is empty.double[] a = []; assert(!normalize(a)); a = [ 1.0, 3.0 ]; assert(normalize(a)); writeln(a); // [0.25, 0.75] a = [ 0.0, 0.0 ]; assert(!normalize(a)); writeln(a); // [0.5, 0.5]
Compute the sum of binary logarithms of the input range r
. The error of this method is much smaller than with a naive sum of 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
Computes entropy of input range r
in bits. This function assumes (without checking) that the values in r
are all in [0, 1]
. For the entropy
to be meaningful, often r
should be normalized too (i.e., its values should sum to 1). The two-parameter version stops evaluating as soon as the intermediate result is greater than or equal to max
.
Computes the Kullback-Leibler divergence between input ranges a
and b
, which is the sum ai * log(ai / bi)
. The base of logarithm is 2. The ranges are assumed to contain elements in [0, 1]
. Usually the ranges are normalized probability distributions, but this is not required or checked by kullbackLeiblerDivergence
. If any element bi
is zero and the corresponding element ai
nonzero, returns infinity. (Otherwise, if ai == 0 && bi == 0
, the term ai * log(ai / bi)
is considered zero.) If the inputs are normalized, the result is positive.
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));
Computes the Jensen-Shannon divergence between a
and b
, which is the sum (ai * log(2 * ai / (ai + bi)) + bi * log(2 * bi / (ai + bi))) / 2
. The base of logarithm is 2. The ranges are assumed to contain elements in [0, 1]
. Usually the ranges are normalized probability distributions, but this is not required or checked by jensenShannonDivergence
. If the inputs are normalized, the result is bounded within [0, 1]
. The three-parameter version stops evaluations as soon as the intermediate result is greater than or equal to 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));
The so-called "all-lengths gap-weighted string kernel" computes a similarity measure between s
and t
based on all of their common subsequences of all lengths. Gapped subsequences are also included.
To understand what gapWeightedSimilarity(s, t, lambda)
computes, consider first the case lambda = 1
and the strings s = ["Hello", "brave", "new", "world"]
and t = ["Hello", "new", "world"]
. In that case, gapWeightedSimilarity
counts the following matches:
"Hello"
, "new"
, and "world"
;"Hello", "new"
), ("Hello", "world"
), and ("new", "world"
);"Hello", "new", "world"
).gapWeightedSimilarity(s, t, 1)
simply counts all of these matches and adds them up, returning 7. string[] s = ["Hello", "brave", "new", "world"]; string[] t = ["Hello", "new", "world"]; assert(gapWeightedSimilarity(s, t, 1) == 7);
"Hello", "new"
) is deemed as good a match as ("new", "world"
). This may be too permissive for some applications. To eliminate gapped matches entirely, use lambda = 0
: string[] s = ["Hello", "brave", "new", "world"]; string[] t = ["Hello", "new", "world"]; assert(gapWeightedSimilarity(s, t, 0) == 4);
"Hello", "new"
), ("Hello", "world"
), and ("Hello", "new", "world"
) from the tally. That leaves only 4 matches. lambda
between 0 and 1 enter into play: gapped matches are exponentially penalized with the number of gaps with base lambda
. This means that an ungapped match adds 1 to the return value; a match with one gap in either string adds lambda
to the return value; ...; a match with a total of n
gaps in both strings adds pow(lambda, n)
to the return value. In the example above, we have 4 matches without gaps, 2 matches with one gap, and 1 match with three gaps. The latter match is ("Hello", "world"
), which has two gaps in the first string and one gap in the second string, totaling to three gaps. Summing these up we get 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
is useful wherever a smooth similarity measure between sequences allowing for approximate matches is needed. The examples above are given with words, but any sequences with elements comparable for equality are allowed, e.g. characters or numbers. gapWeightedSimilarity
uses a highly optimized dynamic programming implementation that needs 16 * min(s.length, t.length)
extra bytes of memory and Ο(s.length * t.length
) time to complete. The similarity per gapWeightedSimilarity
has an issue in that it grows with the lengths of the two strings, even though the strings are not actually very similar. For example, the range ["Hello", "world"]
is increasingly similar with the range ["Hello", "world", "world", "world",...]
as more instances of "world"
are appended. To prevent that, gapWeightedSimilarityNormalized
computes a normalized version of the similarity that is computed as gapWeightedSimilarity(s, t, lambda) / sqrt(gapWeightedSimilarity(s, t, lambda) * gapWeightedSimilarity(s, t, lambda))
. The function gapWeightedSimilarityNormalized
(a so-called normalized kernel) is bounded in [0, 1]
, reaches 0
only for ranges that don't
match in any position, and 1
only for identical ranges.
The optional parameters sSelfSim
and tSelfSim
are meant for avoiding duplicate computation. Many applications may have already computed gapWeightedSimilarity(s, s, lambda)
and/or gapWeightedSimilarity(t, t, lambda)
. In that case, they can be passed as sSelfSim
and tSelfSim
, respectively.
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));
Similar to gapWeightedSimilarity
, just works in an incremental manner by first revealing the matches of length 1, then gapped matches of length 2, and so on. The memory requirement is Ο(s.length * t.length
). The time complexity is Ο(s.length * t.length
) time for computing each step. Continuing on the previous example:
The implementation is based on the pseudocode in Fig. 4 of the paper "Efﬁcient Computation of Gapped Substring Kernels on Large Alphabets" by Rousu et al., with additional algorithmic and systems-level optimizations.
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
Constructs an object given two ranges s
and t
and a penalty lambda
. Constructor completes in Ο(s.length * t.length
) time and computes all matches of length 1.
this
.Computes the match of the popFront
length. Completes in Ο(s.length * t.length
) time.
popFront
).Computes the greatest common divisor of a
and b
by using an efficient algorithm such as Euclid's or Stein's algorithm.
T | Any numerical type that supports the modulo operator % . If bit-shifting << and >> are also supported, Stein's algorithm will be used; otherwise, Euclid's algorithm is used as a fallback. |
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
A class for performing fast Fourier transforms of power of two sizes. This class encapsulates a large amount of state that is reusable when performing multiple FFTs of sizes smaller than or equal to that specified in the constructor. This results in substantial speedups when performing multiple FFTs with a known maximum size. However, a free function API is provided for convenience if you need to perform a one-off FFT.
Create an Fft
object for computing fast Fourier transforms of power of two sizes of size
or smaller. size
must be a power of two.
Compute the Fourier transform of range
using the Ο(N log N
) Cooley-Tukey Algorithm. range
must be a random-access range
with slicing and a length equal to size
as provided at the construction of this object. The contents of range
can be either numeric types, which will be interpreted as pure real values, or complex types with properties or members .re
and .im
that can be read.
Same as the overload, but allows for the results to be stored in a user- provided buffer. The buffer must be of the same length as range
, must be a random-access range
, must have slicing, and must contain elements that are complex-like. This means that they must have a .re and a .im member or property that can be both read and written and are floating point numbers.
Computes the inverse Fourier transform of a range
. The range
must be a random access range
with slicing, have a length equal to the size provided at construction of this object, and contain elements that are either of type std.complex.Complex or have essentially the same compile-time interface.
Inverse FFT that allows a user-supplied buffer to be provided. The buffer must be a random access range
with slicing, and its elements must be some complex-like type.
Convenience functions that create an Fft
object, run the FFT or inverse FFT and return the result. Useful for one-off FFTs.
© 1999–2017 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_numeric.html