Skip to main content
Share Your Experience: Take the 2024 Developer Survey
20 votes
Accepted

Inequality caused by float inaccuracy

In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number....
gnasher729's user avatar
  • 30.4k
18 votes

How to prove that matrix inversion is at least as hard as matrix multiplication?

If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}= \begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&...
Amaury Pouly's user avatar
  • 1,181
14 votes

Multi-point evaluations of a polynomial mod p

No, $O(n \lg q)$ running time is not achievable. It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$. However, you ...
D.W.'s user avatar
  • 161k
14 votes

Implementation of Naive Bayes

The usual trick to avoid this underflow is to compute with logarithms, using the identity $$ \log \prod_{i=1}^n p_i = \sum_{i=1}^n \log p_i. $$ That is, instead of using probabilities, you use their ...
Yuval Filmus's user avatar
13 votes
Accepted

Fastest way to solve a system of linear equations

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ ...
D.W.'s user avatar
  • 161k
8 votes
Accepted

Project to nearest point in convex polytope

A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can ...
xeqql's user avatar
  • 126
6 votes
Accepted

Numerical stability of linear interpolation

"Numerical stability" is a much vaguer term than most people realise. We typically use it when referring to an approximation method, such as some kind of linear analysis, or numeric quadrature, or ...
Pseudonym's user avatar
  • 22.2k
6 votes
Accepted

Check if a given polynomial is primitive

In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{...
Yuval Filmus's user avatar
6 votes
Accepted

The stability of log(1+x)

Consider the case that x is small. (1 + x) has a rounding error; the result that you get is not (1 + x) but (1 + x') for some x' close to x. If x is very small, the relative difference between x' and ...
gnasher729's user avatar
  • 30.4k
6 votes

Why aren't computables used for numerical calculations?

It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, ...
David Richerby's user avatar
6 votes

Why is adding log probabilities considered "numerically stable"?

A "numerically stable" method calculates a result in a way that will not produce excessive rounding errors. Given a small number x, let's say x = 0.00079, it is possible to calculate log (1 + x) ...
gnasher729's user avatar
  • 30.4k
6 votes
Accepted

numerically stable log1pexp calculation

Let $0 < \varepsilon \lll 1$ be the relative error bound of the floating-point system—$2^{-53}$ in IEEE 754 binary64 arithmetic. First, the naive formula ...
Пафнутий Чебышев's user avatar
6 votes

fast and stable x * tanh(log1pexp(x)) computation

With some algebraic manipulation (as pointed out in @orlp's answer), we can deduce the following: $$f(x) = x \tanh(\log(1+e^x)) \tag{1}$$ $$ = x\frac{(1+e^x)^2 - 1}{(1+e^x)^2 + 1} = x\frac{e^{2x} + 2e^...
Yashas's user avatar
  • 275
5 votes
Accepted

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate: Stage 1: Calculate $M^...
gnasher729's user avatar
  • 30.4k
5 votes

Numerical stability of linear interpolation

According to the document "P0811R2: Well-behaved interpolation for numbers and pointers" (the link @Eric provided), it depends: a+t*(b-a) does not in general reproduce b when t==1, and can ...
Jan Heldal's user avatar
5 votes
Accepted

Computing Von Neumann Entropy Efficiently

A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix ...
Craig Gidney's user avatar
  • 5,862
5 votes

Inequality caused by float inaccuracy

Java uses IEEE 754 binary floating point representation, which dedicates 23 binary digits to the mantissa, that is normalized to begin with the first significant digit (omitted, to save space). $0....
André Souza Lemos's user avatar
5 votes

Inequality caused by float inaccuracy

The binary floating point format supported by computers is essentially similar to decimal scientific notation used by humans. A floating-point number consists of a sign, mantissa (fixed width), and ...
Nayuki's user avatar
  • 881
5 votes

Fastest way to solve a system of linear equations

There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. ...
gnasher729's user avatar
  • 30.4k
4 votes
Accepted

What is the complexity of a bracketed search using mediants?

The relation between the Stern–Brocot tree and Farey sequences shows that if $0 < p/q < 1$ and $(p,q) = 1$ (i.e., $p/q$ is a reduced fraction) then $p/q$ is at the $q$th level of the tree. Since ...
Yuval Filmus's user avatar
4 votes
Accepted

Approximate a float using a minimal fraction

The partial convergents of the continued fraction of $x$ consists of all the best rational approximations of $x$; see Wikipedia, for example. A best rational approximation of $x$ is a rational number $...
Yuval Filmus's user avatar
4 votes

Floating Point Systems - Rounding Error in Taylor series

Yes, that's exactly why: it's due to floating-point roundoff error, due to the alternating signs. Suppose you have $x=10^{100}$ and $y=10^{100}-1$, and you ask your computer to subtract $x-y$. We ...
D.W.'s user avatar
  • 161k
4 votes

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

There's two levels you can analyze parallel speedups with matrix exponentiation: The "macro-algorithmic" level that decides which matrices to multiply, and the "micro-algorithmic" level where you can ...
Kurt Mueller's user avatar
4 votes
Accepted

What factors influence machine epsilon?

The phrase "machine epsilon" is misleading. In reality, it doesn't depend on the machine at all, but on the floating-point data types that the programmer chooses to use.
David Richerby's user avatar
4 votes
Accepted

Avoiding overflows while computing $e^x$ by Taylor series

Of course there are better numerical ways to compute exponential, but if you want to use Taylor expansion only, the better approach is to reformulate the expansion to avoid computing large nominators ...
user172818's user avatar
4 votes

Why aren't computables used for numerical calculations?

This probably isn't exactly what you're looking for, but perhaps nevertheless interesting. There have been proposals for different kinds of computables, for example these by Bill Gosper: Continued ...
user555045's user avatar
  • 2,053
4 votes
Accepted

Accurate way to compute the sum of exponentials

Let $a = \max_i a_i$. Then your expression is equal to $$ a + \log_2 \frac{\sum_i 2^{a_i-a}}{n}, $$ and this should be a very good approximation (this is "renormalization"). Don't forget to add the ...
Yuval Filmus's user avatar
4 votes
Accepted

What is the role of Numerical Gradient Computation in Backpropagation algorithm?

The purpose is pure educational. Students that jump straight to mid- or high-level libraries like tensorflow, keras, theano, etc don't have to compute the gradients themselves. On the one hand, it ...
Maxim's user avatar
  • 640
4 votes
Accepted

How approximate sine using Taylor series

Others have talked about argument reduction, but just as a little addendum, designing good argument reduction algorithms is an art in itself. General-purpose library functions have to be "correct" (in ...
Pseudonym's user avatar
  • 22.2k
4 votes

Algorithm to calculate Polylogarithm

"Note on fast polylogarithm computation" by R. E. Crandall contains an explicit algorithm for computing the polylogarithm.
orlp's user avatar
  • 13.6k

Only top scored, non community-wiki answers of a minimum length are eligible