Questions on numerical analysis/numerical methods; methods for approximately solving various problems that often do not admit exact solutions.

learn more… | top users | synonyms (2)

351
votes
7answers
13k views

“The Egg:” Bizarre behavior of the roots of a family of polynomials.

In this MO post, I ran into the following family of polynomials: $$f_n(x)=\sum_{m=0}^{n}\prod_{k=0}^{m-1}\frac{x^n-x^k}{x^m-x^k}.$$ In the context of the post, $x$ was a prime number, and $f_n(x)$ ...
109
votes
1answer
11k views

Proof that ${\left(\pi^\pi\right)}^{\pi^\pi}$ (and now $\pi^{\left(\pi^{\pi^\pi}\right)}$) is a noninteger

Conor McBride asks for a fast proof that $$x = {\left(\pi^\pi\right)}^{\pi^\pi}$$ is not an integer. It would be sufficient to calculate a very rough approximation, to a precision of less than 1, and ...
77
votes
24answers
14k views

Why do we still do symbolic math?

I just read that most practical problems (algebraic equations, differential equations) do not have a symbolic solution, but only a numerical one. Numerical computations, to my understanding, never ...
52
votes
3answers
1k views

How much does symbolic integration mean to mathematics?

(Before reading, I apologize for my poor English ability.) I have enjoyed calculating some symbolic integrals as a hobby, and this has been one of the main source of my interest towards the vast ...
47
votes
11answers
3k views

What is the fastest/most efficient algorithm for estimating Euler's Constant $\gamma$?

What is the fastest algorithm for estimating Euler's Constant $\gamma \approx0.57721$? Using the definition: $$\lim_{n\to\infty} \sum_{x=1}^{n}\frac{1}{x}-\log n=\gamma$$ I finally get $2$ decimal ...
39
votes
4answers
17k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
32
votes
1answer
689 views

How do I calculate the 2nd term of continued fraction for the power tower ${^5}e=e^{e^{e^{e^{e}}}}$

I need to find the 2nd term of continued fraction for the power tower ${^5}e=e^{e^{e^{e^{e}}}}$ ( i.e. $\lfloor\{e^{e^{e^{e^{e}}}}\}^{-1}\rfloor$), or even higher towers. The number is too big to ...
30
votes
1answer
816 views

What's the most efficient way to mow a lawn?

For $S\subseteq\Bbb R^2$ and $x\in\Bbb R$, define $E_x(S)=\{y\in\Bbb R^2:d(y,S)<x\}$. ($E_x(S)$ represents the expansion of $S$ by $x$.) Given a path $\gamma:[0,1]\to\Bbb R^2$, denote its length as ...
26
votes
5answers
5k views

How do you calculate the decimal expansion of an irrational number?

Just curious, how do you calculate an irrational number? Take $\pi$ for example. Computers have calculated $\pi$ to the millionth digit and beyond. What formula/method do they use to figure this out? ...
25
votes
6answers
2k views

Why does my calculator show $2^{-329} = 0?$

On my calculator, I usually get a $0$ when I divide something by $2$, a lot of times if that makes sense, but I was just wondering why does $2^{-329} = 0?$
25
votes
7answers
16k views

Simple numerical methods for calculating the digits of $\pi$

Are there any simple methods for calculating the digits of $\pi$? Computers are able to calculate billions of digits, so there must be an algorithm for computing them. Is there a simple algorithm that ...
25
votes
2answers
903 views

Calculating $\lim_{n\to\infty}\sqrt{n}\sin(\sin…(\sin(x)..)$

I was asked today by a friend to calculate a limit and I am having trouble with the question. Denote $\sin_{1}:=\sin$ and for $n>1$ define $\sin_{n}=\sin(\sin_{n-1})$. Calculate ...
24
votes
1answer
520 views

Approximate value of a slowly-converging sum of $\sum|\sin n|^n/n$

In this question on Math.SE there appears this sum: $$ S = \sum_{n\geq1}s_n, \qquad s_n = \frac{|\sin n|^n}{n}, $$ which converges very slowly. What methods would you suggest for evaluating it ...
23
votes
1answer
534 views

Computing (on a computer) the first few (non-trivial) zeros of the zeta function of a number field

If $K$ is a number field, whose Galois closure over the rationals has degree 24 or so, and whose discriminant is around $163^4$, then what is a numerically efficient way of computing the first few ...
22
votes
2answers
600 views

How to show that a root of the equation $x (x+1)(x+2) … (x+2009) = c $ can have multiplicity at most 2?

How to show that a root of the equation $$x (x+1)(x+2) ....... (x+2009) = c $$ can have multiplicity at most 2 , and to find the value of $ c $ for which this is possible. I proceeded by using the ...
21
votes
8answers
5k views

Rapid approximation of $\tanh(x)$

This is kind of a signal processing/programming/mathematics crossover question. At the moment it seems more math-related to me, but if the moderators feel it belongs elsewhere please feel free to ...
19
votes
4answers
2k views

Why does Monte-Carlo integration work better than naive numerical integration in high dimensions?

Can anyone explain simply why Monte-Carlo works better than naive Riemann integration in high dimensions? I do not understand how chosing randomly the points on which you evaluate the function can ...
19
votes
4answers
457 views

How could I improve this approximation?

In a computer application, I need to solve trillions of times an equation which can be reduced to $$f(x)=\sin(x)-a x=0$$ Newton methods (quadratic and higher orders) are used for the solution. ...
18
votes
4answers
547 views

For which $L^p$ is $\pi=3.2$?

This is a silly question that came to mind after watching numberphile video on How Pi was nearly changed to 3.2. For which $p\in(1,+\infty)$ is the ratio of the perimeter of the $L^p$ disc in $\Bbb ...
18
votes
2answers
671 views

Wiggly polynomials

I'd like to be able to construct polynomials $p$ whose graphs look like this: We can assume that the interval of interest is $[-1, 1]$. The requirements on $p$ are: (1) Equi-oscillation (or ...
17
votes
6answers
2k views

Detecting perfect squares faster than by extracting square root

Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which ...
16
votes
4answers
8k views

Determining whether a symmetric matrix is positive-definite (algorithm)

I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition. The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky ...
16
votes
2answers
860 views

In what sense is the derivative the “best” linear approximation?

I am familiar with the definition of the Frechet derivative and it's uniqueness if it exists. I would however like to know, how the derivative is the "best" linear approximation. What does this mean ...
15
votes
3answers
223 views

Plotting $\left(1+\frac{1}{x^n}\right)^{x^n}$.

When I plot the following function, the graph behaves strangely: $$f(x) = \left(1+\frac{1}{x^{16}}\right)^{x^{16}}$$ While $\lim_{x\to +\infty} f(x) = e$ the graph starts to fade at $x \approx 6$. ...
15
votes
6answers
9k views

Calculate logarithms by hand

I'm thinking of making a table of logarithms ranging from 100-999 with 5 significant digits. By pen and paper that is. I'm doing this old school. What first came to mind was to use $\log(ab) = ...
14
votes
2answers
410 views

how to compare $\sin(19^{2013}) $ and $\cos(19^{2013})$

how to compare $ \sin(19^{2013})$ and $\cos (19^{2013})$ or even find their value range with normal calculator? I can take $2\pi k= 19^{2013} \to \ln(k)= 2013 \ln(19)- \ln(2 \pi)=5925.32 \to k= ...
14
votes
4answers
25k views

What is difference between Finite Different Method, Finite Element Method and Finite Volume Method for PDE?

Can you help me explain the basic difference between FDM, FEM and FVM? What is the best and why? Advantage and disadvantage of them?
14
votes
1answer
281 views

Fastest curve from $p_0$ to $p_1$

I'm trying to solve a problem in path planning: Given points $p_0$ and $p_1$ and vectors $v_0$ and $v_1$, find a function $p(t)$ st. $p(0) = p_0$, $p(T) = p_1$, $p'(0) = v_0$ and $p'(T) = ...
13
votes
9answers
13k views

How to calculate $e^x$ with a standard calculator

Is there a simple method for calculating the $e^x$ ($x\in\mathbb{R}$) with a basic add/subtract/multiply/divide calculator that converges in reasonable time, preferably without having to memorize ...
13
votes
2answers
4k views

Why does Newton's method work?

I find many sites explaining how to use Newton's method, but none explaining why it works. Could someone give me the intuition behind it? Thanks.
13
votes
4answers
8k views

Gradient Descent with constraints

In order to find the local minima of a scalar function $p(x), x\in \mathbb{R}^3$, I know we can use the gradient descent method: $$x_{k+1}=x_k-\alpha_k \nabla_xp(x)$$ where $\alpha_k$ is the step size ...
13
votes
2answers
233 views

Did Feynman mentally compute $\sqrt[3]{1729.03}$ by linear approximation?

In the biopic ``infinity'' about Feynman. (11:48~15:50) Feynman compute $\sqrt[3]{1729.03}$ by a mental calculation. I guess that he use the linear approximation. That is, he observe that ...
13
votes
3answers
1k views

What's the intuition behind “stiff systems”?

One of the mysteries that my numerics class left me with are "stiff systems". Our prof didn't really manage to explain what they are. Now that the class (and the test) are over, I'm still curious. ...
13
votes
1answer
136 views

Why is this approximation of polynomial root so accurate?

I have an engineering problem where I have to find the smallest positive real root of a polynomial in $x$: $$Ax^5+Bx^3 - C = 0$$ Instead of solving numerically, I want simple approximative formulas ...
13
votes
1answer
351 views

Krylov-like method for solving systems of polynomials?

To iteratively solve large linear systems, many current state-of-the-art methods work by finding approximate solutions in successively larger (Krylov) subspaces. Are there similar iterative methods ...
12
votes
7answers
4k views

How to derive a function to approximate $\sqrt{3}$?

The problem is to used fixed-point iteration method to find an approximation to $\sqrt{3}$. The equation from the book is $f(x) = \dfrac{1}{2}\left(x + \dfrac{3}{x}\right)$. It make senses to me ...
12
votes
1answer
1k views

Fast inverse square root trick

I found what appears to be an intriguing method for calculating $$\frac{1}{\sqrt x}$$ extremely fast on this website, with more explanation here. However, the computer-science lingo and ...
12
votes
5answers
514 views

How to calculate $2^{\sqrt{2}}$ by hand efficiently?

I've been trying to calculate $2^{\sqrt{2}}$ by hand efficiently, but whatever I've tried to do so far fails at some point because I need to use many decimals of $\sqrt{2}$ or $\log(2)$ to get a ...
12
votes
2answers
1k views

Minimum of the Gamma Function $\Gamma (x)$ for $x>0$. How to find $x_{\min}$?

The $\Gamma (x)$ function has just one minimum for $x>0$ . This result uses some properties of the gamma function: $\Gamma ^{\prime \prime }(x)>0$ and $\Gamma (x)>0$ for all $x>0$ $\Gamma (1)=\Gamma ...
12
votes
4answers
311 views

Distributions of point charges

Problem $N$ point charges are distributed in the unit ball in $\mathbb{R}^k$, $k=2,3$. Given locations of the particles $x_1,\ldots,x_N$ the potential energy is $E=\sum_{j=1}^{N-1}\sum_{k=j+1}^N ...
11
votes
2answers
594 views

Why is the numerical solution of this equation unstable? Is this equation stiff?

I am trying to solve the following equation with an explicit fourth-order using the Runge-Kutta method: $$y' = t(y - t \sin t)$$ with initial conditions $y(0) = 1$ over the interval $[0, 10]$. The ...
11
votes
4answers
34k views

What’s the difference between Analytical and Numerical approaches to problems?

I don’t have much (good) math education beyond some basic university level calculus. What does “Analytical” and “Numerical” mean and how are they different?
11
votes
2answers
15k views

Explanation and Proof of the fourth order Runge-Kutta method

Runge-Kutte 4th order method is a numerical technique used to solve ordinary differential equation of the form $dy/dx=f(x,y), y(0)=y_0$ It gives $y_{i+1}$ in the form $y_{i+1} = ...
11
votes
5answers
1k views

Can this function be rewritten to improve numerical stability?

I'm writing a program that needs to evaluate the function $$f(x) = \frac{1 - e^{-ux}}{u}$$ often with small values of $u$ (i.e. $u \ll x$). In the limit $u \to 0$ we have $f(x) = x$ using L'Hôpital's ...
11
votes
2answers
781 views

Relation of Brownian Motion to Helmholtz Equation

one can obtain solutions to the Laplace equation $$\Delta\psi(x) = 0$$ or even for the Poisson equation $\Delta\psi(x)=\varphi(x)$ in a Dirichlet boundary value problem using a random-walk approach, ...
11
votes
4answers
291 views

How to compare products of prime factors efficiently?

Let's say that $n$ and $m$ are two very large natural numbers, both expressed as product of prime factors, for example: $n = 3×5×43×367×4931×629281$ $m = 8219×138107×647099$ Now I'd like to know ...
11
votes
2answers
3k views

arc-arc intersection, arcs specified by endpoints and height

I need to compute the intersection(s) between two circular arcs. Each arc is specified by its endpoints and their height. The height is the perpendicular distance from the chord connecting the ...
11
votes
1answer
809 views

Bounding the basins of attraction of Newton's method

In general, Newton's method for root finding has a "bubbly" boundary between basins of convergence for different roots. This is where fractals are usually created from. But outside these "bubbly" ...
11
votes
1answer
275 views

Is there an efficient method for the calculation of $e^{1/e}$?

(I wonder whether this is appropriate for the Math StackExchange or whether it'd be better on Stack Overflow as it deals with computing, but I'm asking about mathematical details, not about ...
11
votes
1answer
2k views

Iterative refinement algorithm for computing exp(x) with arbitrary precision

I'm working on a multiple-precision library. I'd like to make it possible for users to ask for higher precision answers for results already computed at a fixed precision. My $\mathrm{sqrt}(x)$ can ...