Questions tagged [numerical-algorithms]

Questions related to algorithms that use numerical approximations for the problems of mathematical analysis.

Filter by
Sorted by
Tagged with
-1 votes
0 answers
39 views

Implementing multidimensional integral for a custom function in C++ [closed]

I am not an expert with C++, but I am trying to implement a 4-dimensional integral using GSL numerical integration approach. The code below shows the whole algorithm. Although it seems correct what I ...
user avatar
1 vote
1 answer
41 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 ...
user avatar
  • 131
2 votes
2 answers
79 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 ...
user avatar
  • 121
1 vote
1 answer
27 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 ...
user avatar
3 votes
1 answer
56 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 ...
user avatar
0 votes
0 answers
34 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 ...
user avatar
  • 191
3 votes
0 answers
47 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 ...
user avatar
  • 31
1 vote
2 answers
52 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?
user avatar
  • 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 ...
user avatar
2 votes
2 answers
69 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$ ...
user avatar
  • 123
2 votes
2 answers
82 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 ...
user avatar
  • 35
1 vote
0 answers
33 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 ...
user avatar
  • 3,728
1 vote
1 answer
47 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, ...
user avatar
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 ...
user avatar
  • 171
0 votes
1 answer
53 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 ...
user avatar
  • 125
2 votes
1 answer
193 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 ...
user avatar
  • 21
0 votes
6 answers
730 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 ...
user avatar
  • 119
0 votes
0 answers
54 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 ...
user avatar
1 vote
1 answer
104 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 ...
user avatar
3 votes
2 answers
121 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: ...
user avatar
1 vote
1 answer
78 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 ...
user avatar
0 votes
1 answer
122 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\...
user avatar
  • 124
0 votes
2 answers
53 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 ...
user avatar
1 vote
2 answers
61 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 ...
user avatar
1 vote
1 answer
44 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 ...
user avatar
  • 111
1 vote
3 answers
179 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 ...
user avatar
2 votes
1 answer
56 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 ...
user avatar
1 vote
1 answer
60 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 ...
user avatar
  • 113
5 votes
5 answers
399 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 ...
user avatar
  • 265
1 vote
1 answer
692 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 ...
user avatar
  • 329
1 vote
1 answer
101 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 ...
user avatar
  • 111
2 votes
1 answer
170 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\...
user avatar
  • 1,016
3 votes
1 answer
480 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 ...
user avatar
1 vote
0 answers
30 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 ...
user avatar
  • 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 ...
user avatar
  • 1
1 vote
0 answers
20 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-...
user avatar
0 votes
1 answer
71 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. ...
user avatar
  • 329
5 votes
4 answers
553 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 ...
user avatar
  • 151
0 votes
2 answers
98 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 ...
user avatar
  • 1
2 votes
1 answer
282 views

numerically stable log1pexp calculation

What are good approximations for computing log1pexp for single precision and double precision floating point numbers? Note: ...
user avatar
  • 265
2 votes
2 answers
60 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 ...
user avatar
  • 21
3 votes
0 answers
53 views

Efficient algorithm for numerical estimation of 3D rotation matrix

I am writing a computer vision related program and stuck on a problem. I have a system of quadratic equations where M is a constant 3x3 matrix, is the 3x3 identity matrix, and we are solving for the ...
user avatar
  • 176
2 votes
1 answer
47 views

When an algorithm says Summation this, and Integral that, what does it mean in coding terms?

I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me. I'm currently reading GPU Gems by nvidia and I have a question....
user avatar
3 votes
1 answer
39 views

Rigorous error bounds for eigenvalue solvers

I computed the first four eigenvalues of a quite large ($2^{24}\times 2^{24}$) but very sparse matrix. I used pythons in-build function sparse.linalg.eigsh to compute them. I need a validation that ...
user avatar
  • 131
0 votes
0 answers
36 views

Application of iterative algorithm $(\theta_n,w_n)$ converging to $\{(\theta,\theta):\theta \in \Bbb R\}$

I have a iterative algorithm $(\theta_n,w_n)$ which I am showing converges to $\{(\theta,\theta):\theta \in \Bbb R\}$. The iterative algorithm is of the form : $\theta_{n+1} = \theta_n + a(n)[h(\...
user avatar
0 votes
2 answers
1k views

How to test for overflow when multiplying floats

I am trying to implement a 3-term recurrence relation: $$ p_{n+1} = ap_n + bp_{n-1} $$ This can be implemented as ...
user avatar
  • 208
6 votes
0 answers
302 views

What is the state of the algorithmic art for floating point arithmetic on complex numbers?

Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
user avatar
1 vote
1 answer
74 views

How can I minimize floating point error when multiplying normal distribution PDFs?

If you multiply two normal distribution PDFs with means $\mu_1$ and $\mu_2$ and variances $v_1$ and $v_2$, then according to this page, the new mean is $$\mu = \frac{\mu_1 v_2 + \mu_2 v_1}{v_1 + v_2}$...
user avatar
  • 111
3 votes
1 answer
111 views

Could a Van Emde Boas tree be used for storing matrices?

I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix. I was wondering if ...
user avatar
3 votes
0 answers
62 views

How to compute the loss and backprop of word2vec skip-gram using hierarchical softmax?

So we are calculating the loss $$J(\theta) = -\frac{1}{T}\sum_{t=1}^T\sum_{-m \leq j \leq m} \log P(w_{t+j}|w_t;\theta)$$ and to do this we need to calculate $$P(o|c) = \frac{\exp(u_o^Tv_c)}{\sum \...
user avatar
  • 139