Skip to main content
The 2024 Developer Survey results are live! See the results

Questions tagged [error-estimation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
19 views

Algorithm for finding relative estimate from absolute estimate

I am trying to find a textbook reference for an algorithm that gives you a relative estimate of a quantity $a$ (i.e. $|a-\overline{a}|\leq \epsilon_{rel} a$) from an algorithm that gives you an ...
asdf's user avatar
  • 237
0 votes
1 answer
108 views

How to calculate error bounds for the function behind the following algorithm?

D.E. Knuth, in his infamous The Art of Computer Programming, section 1.2.2, presents the following algorithm to efficiently calculate logarithms based on the method used by Henry Briggs: Suppose that ...
Rusurano's user avatar
8 votes
13 answers
6k views

Why do we rely on computers in critical fields?

I assume that computers make many mistakes (like errors, bugs, glitches, etc.), which can be observed from the amount of questions asked everyday on different communities (like Stack Overflow) showing ...
AZeed's user avatar
  • 217
4 votes
1 answer
584 views

Is there some kind of expected error margin for my Monte Carlo algorithm?

My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
J. Schmidt's user avatar
1 vote
1 answer
75 views

Regula falsi with error in x-axis

I want the regula falsi to get x +- .0001 so that f(x) = 0. But all the implemetations I see get x so that f(x) +- .0001 = 0 which doesn't make much sense. (f(x) = x^3). How do I stop the regula ...
EmmanuelMess's user avatar
1 vote
1 answer
176 views

Adaptive step size constrained to a limited number of iterations

I'm solving a differential equation on the form $\ddot x = f( \dot x, x)$ on a microchip within a limited (real world) time frame, hence I want to use an adaptive step size to get as good of a result ...
Beacon of Wierd's user avatar
0 votes
1 answer
493 views

$f(x) = \sqrt{x^{2}+1}-1$ (Loss of Significance)

Let us say that I want to compute $f(x) = \sqrt{x^{2}+1}-1$ for small values of $x$ in a Marc-32 architecture. I can avoid loss of significance by rewriting the function $$f(x)=\left(\sqrt{x^{2}+1}-1\...
Xenusi's user avatar
  • 124
2 votes
4 answers
131 views

How do compilers assure stability?

Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
user avatar
1 vote
1 answer
50 views

Help comparing relative error for different parenthesizations of addition

I am given two functions: $ fl(fl(x+y)+z) $ and $ fl(x+fl(y+z)) $ and asked to derive their relative error. Then, given a set of conditions: a) $ x < y < x $ b) $ x > 0, y < 0, z > 0 $...
Alex Launi's user avatar
0 votes
0 answers
49 views

minimal distance of a self correcting code

i wonder: how can i find minimal distance of a self correcting code in following situation: if we know that a code can fix every 3 errors(if not more than 3 errors, the word is recovered) and can ...
alberto123's user avatar
2 votes
1 answer
341 views

Numerical issues in solving linear systems

There was an exam in the class. The course is "High Performance Scientific Computing". One of the question in the exam is as follows: Consider the linear system $$ \begin{bmatrix} a & b ...
tahasozgen's user avatar
5 votes
4 answers
894 views

Is order of matrix multiplication affecting numerical accuracy of the result?

I have to multiply three matrices of floats: A (100x8000), B (8000x27) and C (27x1). Is ...
abukaj's user avatar
  • 151
1 vote
1 answer
72 views

What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"?

What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"? (it appears on the top of page 12 of this paper)
luw's user avatar
  • 155
4 votes
2 answers
760 views

What does $\tilde{O}_P(N^\alpha)$ mean?

What does $\tilde{O}_P(N^\alpha)$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3. What does big O subscript P mean in a probability context?
luw's user avatar
  • 155
4 votes
2 answers
674 views

Proof that (x-y)(x+y) is more accurate than x²-y²

I was carrying on my reading of What Every Computer Scientist Should Know About Floating-Point Arithmetic but got stuck on the proof of Theorem 2 (page 34). At some point it says: \begin{align} (x \...
Celelibi's user avatar
  • 453
3 votes
1 answer
134 views

Proof that a guard digit bound the error of subtraction

I was reading What Every Computer Scientist Should Know About Floating-Point Arithmetic, which is extremely interesting. But I have some troubles understanding the proof of Theorem 9 (page 33). First ...
Celelibi's user avatar
  • 453
3 votes
1 answer
60 views

Rigorous error bounds for eigenvalue solvers

I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them. I need a validation that ...
BGJ's user avatar
  • 131
6 votes
0 answers
361 views

What is the state of the algorithmic art for floating point arithmetic on complex numbers?

Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
Aaron Rotenberg's user avatar
1 vote
2 answers
589 views

Addition errors in IEEE754 floating point representation

So in class, we were talking about the idea of floating point precision in IEEE754 format, and how, when some numbers are added, precision is lost. My professor then gave the following example of a ...
BeepBoop's user avatar
  • 135
4 votes
0 answers
57 views

Compile-time error control vs. interval arithmetic?

I use interval arithmetic for reliable computing. Now, a procedure coded in a good implementation of interval arithmetic takes perhaps about eight times as much as the same procedure carried out ...
H A Helfgott's user avatar
0 votes
0 answers
53 views

Q-Learning Error Bounds

I have searched a lot for this, but apparently there is no result on calculating any bound on the error $||Q-Q^*||$ when I stop Q-learning after say $N$ iterations ($Q$ is the vector of Q-values at ...
Perissiane's user avatar
1 vote
2 answers
299 views

Computing the error bound of floating-point expression

How should I compute the maximum absolute and relative error of the following IEEE-754 floating-point expression? a.y + (x - a.x) * ((b.y - a.y) / (b.x - a.x)) ...
plasmacel's user avatar
  • 188
2 votes
1 answer
726 views

What happens to a file after too many copy-pasting?

Let's say we're talking about a 1 GB video file. It's copy-pasted from hard disk D1 to the hard disk D2, then from D2 to D3, and so on, all using Windows. If we continue this process for like 1 ...
asmani's user avatar
  • 71
1 vote
1 answer
108 views

Machine error in computer arithmetic

I'm wondering if if is possible to have a function $f$ such that there exists $x,y$ such that we have $f_t(x) > f_t(y)$ where $f_t$ denotes the true value of $f$ and $f_a(x)<f_a(y)$ where $f_a$ ...
Robert S's user avatar
  • 121
2 votes
2 answers
2k views

How to estimate floating-point precision of function?

Let's say I have a function that consists solely of floating-point operations where the last operation rounds the computed value to a predefined number of digits. And I feed this function with a range ...
Thorsten's user avatar
1 vote
1 answer
96 views

Which implementation for the Maclaurin Series for the cosine function is better?

First, sorry if this post is off-topic. I consider it too analytic for stack overflow. In Numerical Analysis subject I must explain which one is better (has less error). The recursive ...
Gustavo Alejandro Castellanos 's user avatar
2 votes
1 answer
1k views

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

I'm coding a program to calculate the value of $e^x$ by using the Taylor expansion, that is: $$ e^x =\sum_{k=0}^\infty \frac{x^k}{k!} $$ ...
Aristu's user avatar
  • 1,483
3 votes
1 answer
1k views

The stability of log(1+x)

I am trying to understand why the formula $$ \frac{\log(1+x)}{(1+x)-1} \times x,$$ which simply reduces down to $\log(1+x)$, is considered as more stable to compute than $\log(1+x)$. In my head it ...
Aesir's user avatar
  • 143
4 votes
2 answers
72 views

Fitting a low-degree polynomial to a function on a finite 1d grid - a combinatorial problem?

I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 ...
einpoklum's user avatar
  • 995
3 votes
2 answers
2k views

Floating Point Systems - Rounding Error in Taylor series

I have a question about rounding error. I have created a function to approximate exp(x) by summing the terms of its taylor series until the sum stops changing. (That is, 1 + x + x^2/2! ...). This ...
myriagon's user avatar
3 votes
0 answers
32 views

Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

tl;dr? See last paragraph. If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form $ x_{k+1} = \frac{x_k\Big[A\...
deamentiaemundi's user avatar
3 votes
2 answers
171 views

How likely is it that a computer miscalculates 1+1? [closed]

Of course, normally a fully-functional computer will calculate 1+1=2. However, the physics governing the behavior of a chip is quantum mechanical. So in principle there is a certain probability that ...
Ethunxxx's user avatar
  • 131
2 votes
2 answers
81 views

Learning parameters of noise and filter coefficients from data where data and noise both have Gaussian distributions

Assume $X$ and $N$ are two sets of vectors (observations) from a normal distribution, where $X$ represents clean data and $N$ represents noise; and $A$ a projection matrix of a filter. The scenario is ...
PickleRick's user avatar
3 votes
0 answers
164 views

Representing Computations on Transcendental Numbers

Consider the set of transcendental numbers that are not compressible to a finite base-2 representation. How can I compute multiples (more generally, any algebraic computation) of one of these numbers,...
geofflittle's user avatar
3 votes
2 answers
272 views

Monetary computations theory (manual/textbook)

My problem is due to the fact that I am manipulating a set of amounts that span over some intervals of time (start date/end date) and that are rounded to cents. I have to multiply each of them by some ...
Igor Deruga's user avatar
1 vote
1 answer
86 views

Why is the precision of floating point numbers worse for smaller numbers?

Why is the machine error/epsilon higher between a pair of two lower numbers than a pair of two high numbers? For example, between the two smallest numbers possible in 5 bit mantissa and the two ...
Rain's user avatar
  • 11
1 vote
1 answer
91 views

Error estimates of piecewise-linear curve approximations

In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about ...
Omicron_Persei_11's user avatar
8 votes
1 answer
137 views

Is the per-vertex error over a PageRank iteration monotonically decreasing?

It seems to me that taken over the entire graph, the norm of the error vector must be monotonically decreasing, otherwise we couldn't guarantee that PageRank would ever converge. However, is the same ...
sooniln's user avatar
  • 265