# Tag Info

## Hot answers tagged numerical-analysis

20

Since this is CS and not Stackoverflow, I'm going to assume that you're asking a question about numeric analysis, and (to keep things simple) IEEE-754 floating point in particular. In that case, the answer to your question partly depends on what you mean by "easier", and partly on the details of the system. No modern CPUs that I'm aware of have an ...

10

The question has been changed since this answer. Another alternative is \begin{align}f(x)&=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\\ &=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\cdot\frac{\sqrt{x+h}+\sqrt{x-h}}{\sqrt{x+h}+\sqrt{x-h}}\\ &=\frac{1}{\sqrt{x+h}+\sqrt{x-h}}\end{align} Now, even if $h$ becomes very small, the value approaches $$\frac{1}{2\sqrt{x}}... 9 What you are experiencing is called 'loss of significant digits'. As h gets smaller, the two square-root terms become closer and closer together, in the sense that their values start with more and more matching digits. Since floating-point cannot represent more than a finite prefix of the infinite-digit actual value for each term, the result of subtracting ... 7 If by 2**x you mean 2^x, then yes. We can use the left-shift operator <<, i.e. we compute 1 << x. This is lightning-fast as it is a primitive machine instruction in every processor I know of. This can not be done with any base other than 2. Moreover, integer exponentiation will always be faster than real exponentiation, as floating point ... 6 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 ... 6 As long as you execute the same machine code on the different machines and as long as the settings for the floating point unit are identical, you will get identical results. However, you cannot execute the same machine code on both Intel and ARM, so this answer is only hypothetic. Even on different Intel processors you have to take special care that exactly ... 6 There's nothing fundamentally hard about computing \sin(10^{99}). You simply compute x = 10^{99} \bmod 2\pi, then compute \sin(x). (Why is this valid? It's because \sin(x)=\sin(y) if x\equiv y \pmod{2\pi}.) It's not too hard to compute x if you use a numerical representation that has enough digits of precision, and then to compute \sin(x) ... 6 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^x}{e^{2x} + 2e^x + 2}\tag{2} = x - \frac{2x}{(1 + e^x)^2 + 1} \tag{3}$$Expression (3) works great when x is negative with very little loss of ... 5 Yes, the difference is constant. It is not really constant, but approximately, yes. With exceptions. With binary floating point numbers, the expression (f(r)−r)/r is constant within a factor of 2. It is between 1 \over 2^m and 1 \over 2^{m-1} where m is the number of bits in the mantissa. For rounding error calculations, you can assume it is ... 4 Taking the sine of large numbers is a numerically unstable operation. Considering an argument like 10^{99}, you can get a completely different value of the sine by adding, say 1 to it. Think that this is a relative change of 10^{-99} ! Indeed,$$|\sin(a+1)-\sin(a)|=|2\sin(\frac12)\cos(a+\frac12)|>0.95|\sin(a+\frac12)|,$$so that you can find ... 4 (1) Yes, the numbers in fixed point arithmetic are just scaled integers. (2) No, by a short counterexample. The floating-point arithmetic represents numbers as r = i \times b^j. Let us pick a random base, e.g. b = 10 and create the smallest positive number r = 1 \times 10^m. Let m < 0 be the minimal possible exponent (its size depends on the ... 4 Continued fractions are an efficient way to enumerate rational numbers that are a good approximation of your number x. In particular, given a real number x, you can generate a sequence of truncated continued fractions a_i/b_i, where each rational number a_i/b_i is a better approximation to x than any other fraction whose denominator is \le b_i. ... 4 First, I want to say that it is not the case in general that an algorithm that minimizes the number of uses of the inputs is more accurate, at least for IEEE 754 floating point. For example, compensated summation. On the other hand, it's certainly the case that interval arithmetic can greatly benefit from knowing when two inputs are identical. As a ... 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 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 log1p(exp(x)) always gives a good approximation unless exp(x) overflows: If exp(x) computes (1 + \delta_1) e^x, and if log1p(y) computes (1 + \delta_2) \log(1 + y), where |\delta_1|, |\delta_2| \... 4 OP points to a particular implementation of the mish activation function for accuracy specifications, so I had to characterize this first. That implementation uses single precision (float), and is stable and accurate in the positive half-plane. In the negative half-plane, because it uses logf instead of log1pf, relative error quickly grows a x\to-\infty. ... 4 Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range. For example, you should be able to tell that x definitely falls into at least one of the ranges A = \left(0,\frac{3}{4}\right], B = \left[\frac{1}{... 3 We can write it as$$f(x) = \dfrac{\sqrt{-x+a} - \sqrt{2x+a}}{ 4a}= \dfrac{\sqrt{-\frac xa+1} - \sqrt{\frac{2x}a+1}}{ 4\sqrt a}$$If x \ll a both of the square roots will be just about 1. When you add the \frac xa terms to 1 you will lose many bits of \frac xa, then when you subtract the square roots the 1s will cancel. If your floats have 53 ... 3 I did not check the code used in Abelson and Sussman's book or wiki. My guess is that the recursive (or iterative) procedure will somehow organize to compute improve(guess,x) only once. In a recursive procedure, you just compare the formal parameter which is the previous guess with the actual value (current guess) that you would pass for a recursive call, in ... 3 A brute force solution is to trace the line ay=bx in integer coordinates from the origin to (a,b). Any pair with a smaller number of bits will be along that line segment. This method allows finding either the minimum distance or the smallest (x,y) within the error bounds. It requires o(a+b) steps, and there's plenty of redundancy possible, since eg both (x,... 3 So the paper's "Numerical infinities and infinitesimals: Methodology, applications, and repercussions on two Hilbert problems", Yaroslav D. Sergeyev (2017), and it's basically a discussion on the author's "grossone" approach that they've been pushing for quite a while now (at least since 2004). The tl;dr on it is that they're proposing a slightly ... 3 Yes, when x\ge355, computing e^{2x} as a double-precision float in IEEE 754-1985 standard, leads to an overflow.$$x + \frac{e^x-x}{e^{2x} + 1}= x + e^{-x} - \frac{x+e^{-x}}{e^{2x} + 1}\approx x+ e^{-x} The difference between the two sides of the approximate sign is smaller than the minimal positive number in IEEE 754-1985 standard, $2^{−1022} \... 3 For$\exp(-10)$, more terms have to be computed since the 30-th term$\dfrac{(-10)^{30}}{30!}\approx 0.00377$is several times bigger than the partial sum so far, 0.0009703416. For$\exp(10)$, all terms are positive. The 30-th term$\dfrac{(10)^{30}}{30!}\approx 0.00377$is already substantially negligible to the partial sum so far, 22026.464. Here is the ... 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 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 There's no need to perform the logarithm. If you let$p = 1+\exp(x)$then we have$f(x) = x\cdot\dfrac{p^2-1}{p^2+1}$or alternatively$f(x) = x - \dfrac{2x}{p^2+1}$. 2 Guess anything at all for the cube root of$a$: call that value$t$.$t′=\tfrac13(a/t^2+2t)$is closer to$\sqrt[3]{a}$than$t$is, so use$t′\$ as your next guess. Keep going.

2

If 2**x is a function on integers, then I agree with Stephen's answer, shift is cheaper. But I typically see that as 2^x and ** to indicate floating point exponentiation. For this case, I would expect similar performance between ** and ^ since both exp and pow (the underlying operation for **) are both transcendental approximation operations.

2

There are lots of methods. I have usually found a 4th order adaptive step size Runge Kutta method to work fairly well. A Leapfrog method might better preserve invariants over the long term. I'm afraid I don't know enough about reaction-diffusion systems to know how that might change my answer. You might look into our sister sites in scientific computing, ...

2

For the game you describe, take a look at binary search. It will find the answer in logarithmically many queries: the logarithm of the search space. In some cases interpolation search can perform even better. For the application you mention at the end, take a look at TCP's congestion avoidance algorithm (additive increase, multiplicative decrease), as ...

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