Questions tagged [numerical-algorithms]
Questions related to algorithms that use numerical approximations for the problems of mathematical analysis.
150
questions
0
votes
0
answers
17
views
Minimizing a sum of trigonometric functions
I would like to minimize the term where J_l and h_l are random numbers and L=10. Can somebody help me to solve the problem?
0
votes
0
answers
13
views
Help with Boundary Integral Equation Method with laplace equation (Given NURBS curve)
I am trying to use a boundary integral equation method to solve for laplace equation given the control points of a NURBS curve. But my BIEM is giving me very large error for numerical functions.
I ...
0
votes
3
answers
130
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 ...
- 187
0
votes
0
answers
20
views
How to optimize an approximated matrix multiplication?
Suppose the objective I try to maximize is
$$\max_{X} \|(I - \alpha X)^{-1}XA\|_F$$
where $X$ is the matrix needs to be pinned down, $\alpha$ is a scalar, and $\|\cdot\|_F$ is the Frobenius norm. Note ...
1
vote
1
answer
51
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,393
0
votes
1
answer
30
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
49
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
38
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 ...
- 10.3k
3
votes
0
answers
278
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 ...
- 71
0
votes
0
answers
41
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 ...
- 101
1
vote
1
answer
86
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
241
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
84
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 ...
- 2,960
3
votes
1
answer
80
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 ...
- 133
0
votes
0
answers
37
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 ...
- 201
3
votes
0
answers
48
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
633
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
22
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
100
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
121
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 ...
- 65
1
vote
0
answers
57
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,790
1
vote
1
answer
139
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
15
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 ...
- 171
0
votes
1
answer
174
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 ...
- 125
2
votes
1
answer
432
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
0
votes
5
answers
2k
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 ...
- 119
0
votes
0
answers
117
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
149
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
142
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:
...
- 313
1
vote
1
answer
91
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
367
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
60
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
77
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
47
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
256
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 ...
- 139
2
votes
1
answer
69
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
149
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
469
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
1
vote
1
answer
2k
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 ...
- 349
1
vote
1
answer
215
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
285
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,045
3
votes
1
answer
747
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
52
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
7
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
21
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
74
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. ...
- 349
5
votes
4
answers
770
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
0
votes
2
answers
101
views
How to find i-th root of n whose remainder is the smallest?
Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ...
- 1
3
votes
1
answer
470
views
numerically stable log1pexp calculation
What are good approximations for computing log1pexp for single precision and double precision floating point numbers?
Note: ...
- 275
3
votes
2
answers
67
views
Search for numerical solutions of underdetermined systems of quadratic equations
I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a ...
- 31