5

Let me illustrate one problem which could happen, and one way to solve it. You want to distribute a given amount of cents $N$ into $k$ piles, in proportions $p_1,\ldots,p_k$, where $p_1,\ldots,p_k \geq 0$ and $p_1 + \cdots + p_k = 1$. The problem is that $Np_i$ need not be an integer. As a simple example, you might want to divide $20$ cents into $1/3:2/3$ ...


4

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 and denominators. This leads to an $O(n)$ algorithm, where $n$ is the number of iterations. Yours is $O(n^2)$ if you compute factorial and power literally (...


4

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 x can be quite large. Trying to calculate log (1 + x) will calculate log (1 + x') which can have a large relative error. Instead the better formula calculates ...


4

Pulled from: http://www2.math.uu.se/~svante/papers/sjN6.pdf (definition D5). A probabilistic version of $\mathcal{O}$ that is frequently used is the following: $X_n = O_\text{P}(\alpha_n)$ if for every $\epsilon > 0$ there exists constants $C_{\epsilon}$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n) > 1 − \epsilon$ ...


3

I'm not 100% sure of everything, but here are some elements that are implicit in the proof. Note that I reuse the notations and common knowledge of the paper, therefore this answer isn't self-contained. First, let's assume that $x \gt y \ge 0$. It's a safe assumption to make because the sign of the variables doesn't matter and swapping $x$ and $y$ only ...


3

Suppose $y = x + \Delta$. Then $(x^2 - y^2) = x^2 - (x^2 + 2\Delta x + \Delta^2) = - (2\Delta x + \Delta^2)$ with leading term on the order of $2 \Delta x$. Multiply by $1 + \delta_1$ and that's still the leading term. Compare to $(\delta_1 - \delta_2) y^2$ with leading term $(\delta_1 - \delta_2) x^2$.


3

Once a single-bit error is introduced into a file, the file is corrupt. File systems, disk drivers, and hardware on the disk itself have checksums, error correction codes, and facilities to detect bad sectors to limit the probability of write (or read) errors, but it's not 100% (but it better be close to 100%, otherwise my disk isn't reliable). In general, ...


3

No. Consider the case of an isolated component with a central vertex v that is pointed to by vertices x_1, ...., x_k. The initial value at v is 1/n, and the final value should be roughly k * the restart probability/n. But the value at v in the second round is roughly k/n. If the restart probability is significantly less than 1/k, then the value got further ...


3

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 know what the correct answer should be: it should be $1$. However, when $x$ and $y$ are represented as floating-point numbers, you don't get $1$ as the answer. ...


2

The problem can be solved in polynomial time using linear programming. Write $p(x) = c_k x^k + \dots + c_1 x + c_0$, and think of $c_0,\dots,c_k$ as unknowns. Also introduce an unknown $d$, which will represent the $L_\infty$ norm. We will minimize $d$, subject to the following inequality: $$-d \le f(i) - (c_k i^k + \dots + c_0) \le d.$$ Notice that, ...


2

The Taylor series for the exponential function converges (mathematically) for any input value to the correct result. The problem is that with this particular series, the terms that you add will be huge compared to the final result. Rounding errors for addition are roughly proportional to the magnitude of each the result, so adding the Taylor series even for ...


2

It might suffice to ask the solver to give you both the eigenvalue $\lambda$ and the corresponding eigenvector $v$. Then you can verify for yourself how much error there is. Note that if $\lambda$ is the eigenvalue corresponding to eigenvector $v$, for matrix $M$, then we have $Mv=\lambda v$. So if you know $M$ and $v$ exactly, and you have a claim that $\...


2

It depends on context; often, saying $f(n) \in \tilde{O}(g(n))$ means $f(n) \in O(g(n) n^{\epsilon})$ for all $\epsilon>0$. For example, $n^2 \log n \in \tilde{O}(n^2)$.


2

Yes, there are differences in accuracy since with machine numbers the usual properties of arithmetics don't hold. Machine numbers are defined as $$ F(\beta,t,m,M)= \{ 0 \} \cup \{ x \in \mathbb{R} : x = sign(x)\beta^{p} \sum_{i=1}^{t}d_i\beta^{-i},\ 0 \leq d_i \lt \beta\ ,\ d_1\ne 0\ , -m \le p \le M \} $$ and represent the subset of $\mathbb{R}$ that ...


1

The $2\times 2$ matrix has determinant close to zero, and so its condition number is very large, causing numerical instability. The explicit solution of your system is $$ x=\frac{a}{a^2-b^2}, y=-\frac{b}{a^2-b^2}. $$ Therefore $$ x+y = \frac{a-b}{a^2-b^2} = \frac{1}{a+b}, $$ thus avoiding the numerical issues.


1

The notation $\tilde{O}(f(n))$ is not completely standard and is usually defined as $\tilde{O}(f(n)) = O( f(n) \cdot \text{poly} \log f(n))$. The intuition is that it drops factors that are asymptotically not larger than a polylogarithm of the argument. For example, you can write $\tilde{O}(n^2)$ in place of $O(n^2 \frac{\log^3 n}{\log \log n})$. That said, ...


1

I'll post some elements of answer to my own question from what I understand. Anyone feel free to make a better, less sloppy answer. First, there are several versions of this document online. They all have some typographic defects at some point. So when in doubt, better check those 3 versions first. https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf ...


1

Printing out the IEEE754 format of the two numbers, I get: $\space\space\space0[11100010]10111100010010010101011=+1.10111100010010010101011\times2^{99}$ $+0[11100001]01000011000111100001000=+1.01000011000111100001000\times2^{98}$ Compare the exact values: $$ 1.1011110001001001010101011000111111010110011111001110000010110110100111 \times 2^{99} \\ 1....


1

Yes! Various languages and APIs often specify the precision you are guaranteed. If the underlying hardware doesn't offer that precision, they must emulate it with extra work. For instance, some machine instructions that compute transcendental function (sin, cos, exp, log, ...) only offer a limited accuracy. Library implementations that guarantee a certain ...


1

There's no rule of thumb. There is analysis, and that analysis can be more or less elaborate, depending on what you want. Assume IEEE 754 double precision arithmetic in default rounding mode (round to nearest even). If the highest bit of the mantissa has a value of $2^k$, that is if $2^k ≤ |x| < 2^{k+1}$ then the lowest bit of the mantissa has a value ...


1

Assuming that you're rounding from the thousandths place, the code in your example will always be accurate. Floating point numbers remain useful because they keep their imprecisions quite small relative to the most significant digit. For instance, using the 8-byte IEEE754 standard (doubles in Java), 10.0/3.0 becomes3.3333333333333335. You also asked for ...


1

The main problem with the iterative approach is that the terms of the series get smaller and smaller with increasing index, so if you sum terms from 1 up, you eventually end up adding values of very small magnitude to accumulated sums of much larger magnitude. When done using floating-point arithmetic, that's pretty much the same as simply discarding terms ...


1

Here's my current idea. It's oriented towards a faster implementation - i.e., for me, $\Omega(n^2)$ is much too much. It also assumes a lower threshold value for distance (which is relevant for me, since the functions' domain in practice is values stored in O(1) space, e.g. 4-byte integers or floating point values). Well, the idea is only a sketch, but in ...


1

The probability of read error is bigger than write error, so there is a chance for bitflip on either of $1$ which might occur anywhere. I can offer description of JVM attack which is not exactly the answer, but shows how much effort is needed to induce bitflips, tells about softerrors and a very successful attack on JVM, given good heat ;). The probability ...


1

Your problem is that of multivariate linear regression. Finding each row of $A$ corresponds to a classical linear regression problem, which can be solved using the method of least squares, which is optimal here since the noise is Gaussian. Once you have an estimate for $A$, you can estimate the parameters of $N$ by isolating $N = Y-AX$. (This is not ...


1

Error analysis of floating point programs is a complex fields that far extends the scope of financial calculations. In general it is a quite complex field, which takes a bit of experience to get comfortable with. Some starter papers: What Every Computer Scientist Should Know About Floating-Point Arithmetic. A classic, but just brushes the surface. Error ...


1

The potential error is the same in absolute terms for the same exponent. But since the smaller numbers are about half the size of the larger numbers, the relative error is about twice as high for the smaller numbers.


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