Questions tagged [numerical-algorithms]
Questions related to algorithms that use numerical approximations for the problems of mathematical analysis.
153 questions
3
votes
1
answer
405
views
Finding the solution to an equation closest to an arbitrary state
There are a number of numerical methods for finding a solution to an equation that is usually close to the initial guess, but not always the closest. Is there an algorithm that will always find the ...
4
votes
2
answers
134
views
Theory behind scaled floating-point summation algorithm
In the "jacobi.c" code implementing Jacobi's method for computing eigenvalues and eigenvectors of a given matrix, from the gsl-2.8 library, one of the functions is for summing the squares of ...
- 350
7
votes
2
answers
3k
views
Numerical methods: why doesn't this python code return 1.0?
I typed the following into the python console:
...
- 71
0
votes
1
answer
165
views
How to check if a real number, in a decimal form, has an accurate IEEE 754 representation?
Perhaps the answer is simple, but I am looking for ideas. I need to generate a set of a minimum of 100-200 real numbers, all having an accurate computer representation (according to the IEEE 754 ...
- 1
3
votes
0
answers
49
views
Is this approach to generating points for the graph of a function that attempts to avoid discontinuities appropriate?
I'm not sure where to ask this question, I'd appreciate being redirected accordingly if need be.
Context
Let's say I have a program that might plot the graph of functions supplied by a user, for ...
- 300
0
votes
0
answers
176
views
What is SRT division algorithm?
I have been studying the IEEE-754 standard and came across the information that floating-point division uses the SRT algorithm, ...
0
votes
3
answers
622
views
Details of sqrt.c library source code
Have seen library code for finding square-root, using the Newton Raphson method.
It uses a table of 256 entries, whose significance is unclear, as the initial guess should be dependent on the quantity ...
- 201
1
vote
1
answer
199
views
FFT of logarithmic input data
Is there a reasonably accurate method of computing an FFT of logarithmically-represented input data (with a sign bit, that is $±2^{\text{double-precision value}}$)?
The naive method (convert to linear ...
- 1,500
0
votes
1
answer
60
views
Hill climbing method searching special polynomial equations
I have system of two polynomial two variables, second order; monomials are {${1,x,y,x^2,xy,y^2}$}
I want find special systems of polynomials: two or more roots in specified range, two root close to ...
- 141
2
votes
0
answers
74
views
Best way to constrain a complex number to being within the unit circle?
What is the best way of implementing the following function,
$$f(x) = \frac{x}{\max(1, |x|)},$$
where $x$ is complex, using a Cartesian representation of $x$ with IEEE 754 floating point ...
- 121
2
votes
0
answers
62
views
Alternative parameterizations of the circle
When solving numerical problems with circles, one often has to sample these at numerous points, not necessarily in a uniform way. Evaluating the $(\cos\theta,\sin\theta)$ values can represent a ...
user16034
3
votes
0
answers
683
views
What are the use cases for the IEEE 754 inexact flag?
The IEEE 754 standard for floating point numbers defines a flag that is set when a result from floating point calculation isn't exact, i.e. has to be rounded. What algorithms are there that utilize ...
- 196
0
votes
0
answers
64
views
What is the quickest algorithm to numerically integrate this function?
Motivation & Question
So I can theoretically build a "computer" to calculate the exact anti-derivative of a particular function.
Using classical calculations and the Robin boundary ...
- 109
1
vote
1
answer
227
views
Algorithm to calculate lower incomplete gamma function
I'm trying to understand the implementation of the algoritm here. Please see GammaLowerRegularized(a, x) function.
I understand 1st part of the function for ...
- 131
3
votes
4
answers
386
views
Factor a number in the longest possible product of distinct numbers
I got stuck with quite a simple problem:
Given a positive number $X$ find the largest number $k$, for which exists the positive distinct integers $Y_1,…,Y_k$ such that $(Y_1+1)(Y_2+1)⋯(Y_k+1)=X$
Any ...
- 131
1
vote
1
answer
252
views
What does it mean unambiguously that a number is value 0 up to numerical precision?
I was reading that a quantity $x$ is $0$ upt to numerical precision. What does this statement formally mean -- especially in the context of numerical methods or real computers.
I looked up in google ...
- 3,130
4
votes
1
answer
146
views
Bisecting Intervals of floating point numbers containing 0 and infinity fairly
It is seldom considered that floating points are not evenly distributed in the real number line. I've been working with interval arithmetic and noticed when bisecting $[a,b]$ on the real number line ...
- 225
0
votes
0
answers
75
views
What is the most performant and reliable algorithm to find all roots of a nonlinear function within a range?
Following this question on MATLAB's Discord channel, I did a bit of search and found this interesting answer using circshift() function to detect zero-crossings. I ...
- 221
3
votes
0
answers
82
views
Computing a series of matrix power - matrix products
Assuming we have two dense matrices $A \in \mathbb{R}^{m\times m}, B \in \mathbb{R}^{m\times n}$, is there a smart way to compute all entries of the series $A^1 B, A^2 B, A^3 B, \dots, A^k B$ up to ...
- 71
1
vote
2
answers
1k
views
How many Integers can be represent in Double-Precision floating-point form
How to calculate the number of Integers that can be represent in Double-Precision floating-point form?
- 15
1
vote
0
answers
34
views
Given constants $c_i$ and $K$, find $b$ numerically such that $b^{c_1} + b^{c_2} + ... + b^{c_n} = K$
Given constants $c_i > 0$ and $K > 0$, find $b > 0$ numerically such that $b^{c_1} + b^{c_2} + \dots + b^{c_n} = K$. I'd like to solve this with a non-iterative method if possible.
My attempt ...
2
votes
2
answers
243
views
Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value
The Problem
I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form:
$$x = A\times\frac{N}{D}$$
Where $A$ is a 32-bit integer, and $N$ ...
- 123
4
votes
2
answers
400
views
Precise algorithm for finding higher order derivatives
I'm trying to make an algorithm that finds the first 10 or so terms of a function's Taylor series, which requires finding the nth derivative of the function for the nth term. It's easy to implement ...
- 175
1
vote
0
answers
90
views
Finding points of local maximum error in Remez algorithm
So the Remez algorithm is an algorithm for finding optimal polynomial approximations or at the very least for converging towards them. To find an approximation of $f$ by an $N$th degree polynomial the ...
- 3,810
1
vote
1
answer
186
views
How to use Runge–Kutta methods in a second order ODE
Consider a second order equation $F=ma=m\ddot{x}$.
In the language of Euler's method
$\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$
$\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$
$x(t+dt)=x(t)+\dot x(t)dt$
Basically, ...
1
vote
0
answers
27
views
Numerically solving an ode with infinitely many variables of which only finitely many are significant in magnitude
Suppose I have an ode that involves infinitely many variables, with the property that at any given time, only finitely many of them are large enough to be of interest (say $>10^{-10}$). However, at ...
- 230
1
vote
1
answer
585
views
fastest way to identify "singular row" of a matrix
Suppose I have a matrix that I know to be singular. This means that there is at least one row in the matrix which is a linear combination of the other rows. What is the fastest way to identify which ...
- 135
2
votes
1
answer
781
views
Complexity of inverting a diagonal matrix
What is the complexity of inverting a $n \times n$ diagonal matrix?
From what I learn in algebra, the inverse of a diagonal matrix is obtained by replacing each element in the diagonal with its ...
- 21
1
vote
5
answers
5k
views
What algorithm do computers use to compute the square root of a number?
What algorithm do computers use to compute the square root of a number ?
EDIT
It seems there is a similar question here:
Finding square root without division and initial guess
But I like the answers ...
- 139
0
votes
0
answers
205
views
How to express a parabola as a Bezier curve
I need to create a parabolic shape with a given starting point, maximum point, and end point. I thought the most efficient way to do this is to use a bezier curve. However there is no major ...
1
vote
1
answer
214
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 ...
3
votes
2
answers
182
views
How can I compute logarithm when comparison is undecidable?
In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively:
...
- 391
1
vote
1
answer
190
views
Cancellation in C++
I am trying to figure out what the problem with the following expression in C++ is:
y=std::log(std::cosh(x));
My first intention was that there might occure a ...
- 58
0
votes
1
answer
628
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\...
- 124
0
votes
2
answers
120
views
convergence rate of newton's method
So, I'm currently studying Newton method used for finding the 0's of a function, however my professor has only announced that the speed of this algorithm can be more than quadratic, however I'm ...
anon
2
votes
2
answers
148
views
Validity of Algorithm for Testing Two Floating Point Numbers
This question is related to the epsilon- (or delta- if you prefer) test for floating point equality. But my question is not how to do it. Instead I have a related algorithm for testing equality, and I ...
- 121
1
vote
1
answer
83
views
foresightful acceleration and decelerations
I am programming a CNC machine (using matlab). In order to generate a surface with a "high" shape accuracy (order of $1\mu m$) and "small" micro roughness (order of few nm) I need ...
- 111
1
vote
3
answers
363
views
Algorithm to compute power function on interval [0, 1]
I am looking for an efficient algorithm to compute $$f(x) = x^a, x\in[0, 1] \land a\,\text{constant}$$
If it helps, $a$ is either $2.2$, or $1/2.2$. Knowing valid values for $x$ and $a$ could make it ...
- 149
2
votes
1
answer
115
views
O(m+n) Algorithm for Linear Interpolation
Problem
Given data consisting of $n$ coordinates $\left((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\right)$ sorted by their $x$-values, and $m$ sorted query points $(q_1, q_2, \ldots, q_m)$, find the ...
1
vote
1
answer
291
views
Complexity of numerical derivation for general nonlinear functions
In classical optimization literature numerical derivation of functions is often mentioned to be a computationally expensive step. For example Quasi-Newton methods are presented as a method to avoid ...
- 113
5
votes
5
answers
746
views
fast and stable x * tanh(log1pexp(x)) computation
$$f(x) = x \tanh(\log(1 + e^x))$$
The function (mish activation) can be easily implemented using a stable log1pexp without any significant loss of precision. Unfortunately, this is computationally ...
- 275
2
votes
1
answer
6k
views
Converting a number to 16-bit Floating Point Format
I want to convert the number -29.375 to IEEE 745 16-bit floating point format. Here is my solution:
The format of the floating point number is:
1 sign bit
unbiased exponent in 4 bits plus a ...
- 379
1
vote
1
answer
460
views
Algorithm to calculate Polylogarithm
In my code i want to solve the Fermi-Dirac-Integral numerically. This can be achieved with a Polylogarithm.
Actually I'm coding in C#, so my function to calculate ...
- 111
2
votes
1
answer
473
views
How were weights chosen in Runge-Kutta (4) method?
Consider an ODE $\dot y = f(t, y)$. We will approximate the value of $y$ using the 4th-Order Runge-Kutta method. Let $\Delta$ be the step size, then in step $i+1$ we have $~y_{i+1} = y_i + deriv\cdot\...
- 1,135
3
votes
1
answer
1k
views
Robust two lines/segments intersection point in 2D
Given two line segments the problem is to find an intersection point of corresponding lines (assuming that they are not parallel or coincide).
There is a Wikipedia article which gives us exact ...
- 161
1
vote
0
answers
76
views
Algorithm to position samples minimizing error
We have a 1D function f(x). We would like to approximate this function with a polyline of n points. How can we find the ...
- 111
0
votes
0
answers
24
views
Efficiently populate a look-up table for a function over a range of arguments
I am minimizing a scalar function $f$ which takes a $n$-dimensional vector input and outputs a scalar value. I have code that given an input $x$ will compute the output of $f(x)$ (a scalar), its ...
- 1
1
vote
0
answers
32
views
Are there practical usage of determinants in numerical simulation?
I know the historical importance of the link between linear systems and determinants. I also know that determinants have a beautiful connection with non-singular matrices, i.e., if a matrix is non-...
0
votes
1
answer
109
views
Computing an Expression
I am writing code to evaluate the following expression:
$$ \frac{(a+b+c)!}{a! b! c!} $$
where $a$, $b$ and $c$ are on the range of $10$ to $500$. The result is going
to be a floating point number. ...
- 379
5
votes
4
answers
1k
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 ...
- 151