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)

323
votes
7answers
12k 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)$ ...
102
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 ...
73
votes
24answers
13k 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 ...
47
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 ...
42
votes
10answers
2k 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 ...
31
votes
1answer
715 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 ...
30
votes
1answer
628 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 ...
28
votes
3answers
12k 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 ...
24
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?$
24
votes
7answers
13k 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 ...
24
votes
2answers
777 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 ...
23
votes
5answers
4k 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? ...
23
votes
1answer
476 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
513 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
559 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 ...
20
votes
8answers
4k 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 ...
18
votes
4answers
371 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. ...
17
votes
4answers
515 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 ...
17
votes
2answers
609 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 ...
16
votes
4answers
7k 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 ...
15
votes
3answers
1k 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 ...
15
votes
5answers
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 ...
14
votes
2answers
383 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
5answers
7k 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
1answer
267 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
8k 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 ...
12
votes
7answers
3k 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
4answers
6k 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 ...
12
votes
4answers
16k 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?
12
votes
2answers
644 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 ...
12
votes
1answer
334 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 ...
11
votes
2answers
3k 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.
11
votes
2answers
727 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
262 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
5answers
473 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 ...
11
votes
2answers
2k 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
4answers
307 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
1answer
266 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
1k 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 ...
10
votes
4answers
282 views

A numerical evaluation of $\sum_{n=1}^{\infty}(-1)^{\frac{n(n+1)}{2}}\frac1{n!}\int_0^1x^{(n)} dx$

I would like to obtain a numerical evaluation of the series $$S=\sum_{n=1}^{\infty}(-1)^{\frac{n(n+1)}{2}}\frac1{n!}\int_0^1x(x+1)\cdots(x+n-1)\: dx$$ to five significant digits. I've used ...
10
votes
5answers
786 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 ...
10
votes
1answer
782 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 ...
10
votes
1answer
639 views

Incremental calculation of inverse of a matrix

Does there exist a fast way to calculate the inverse of an $N \times N$ matrix, if we know the inverse of the $(N-1) \times (N-1)$ sub-matrix? For example, if $A$ is a $1000 \times 1000$ invertible ...
10
votes
3answers
2k views

Computing the largest Eigenvalue of a very large sparse matrix?

I am trying to compute the asymptotic growth-rate in a specific combinatorial problem depending on a parameter w, using the Transfer-Matrix method. This amounts to computing the largest eigenvalue of ...
10
votes
2answers
939 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 ...
10
votes
1answer
699 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" ...
10
votes
1answer
123 views

Is anyone talking about “ball bundles” of metric spaces?

In differential geometry: Each smooth manifold $M$ is equipped with a tangent bundle $TM,$ which is a manifold equipped with a projection back to $M$ Given a smooth map $f : M \rightarrow N$ between ...
10
votes
1answer
283 views

How can I intuit the role of the central limit theorem in breaking the curse of dimensionality for Monte Carlo integration

I would like to more intuitively understand where the power of Monte Carlo integration comes from for large-dimensional domains of integration. Other questions on this site have referenced the proof ...
10
votes
1answer
2k views

Using the Arnoldi Iteration to find the k largest eigenvalues of a matrix

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it: power iteration: take random ...
9
votes
4answers
602 views

Solve for $x$: $2^x = x^3$

What category of equation is this? What methods are available to solve it? $2^x -x^3 = 0$ where $x\in\Bbb R$