New answers tagged algorithms
2
votes
Accepted
Metropolis-Hastings kernel in measure theory
You asked another question that seems somewhat likely to be closed for not being research-level mathematics. I will include my posted answer to that here because that one may get closed.
One does not ...
- 11.4k
1
vote
Accepted
Slicing bivariate exponential generating functions on x and y
Assuming $D(0) = 0$, we can restate the problem as $F(x, y) = A(x)^y$ for $A(x) = e^{D(x)}$.
It means that we can find $G_n(k)$ for any number $k$ as
$$
G_n(k) = \left[\frac{x^n}{n!}\right] A(x)^k.
$$
...
- 1,121
2
votes
Recover unknown vector through shifted argmax queries
The following argument suggests that the factor $O(n)$ cannot be improved. Suppose for a contradiction that $x\in\{0,1\}^n$ and after queries with $v_1,\dots,v_{n-1}\in\mathbb R^n$ we determined that $...
- 3,937
2
votes
Efficiently computing $\sum_k x^{k^2}$ modulo $p$
Not exactly an answer, but should provide a strong hint on where to look.
This is closely related to Gauss quadratic sums, expressions of the form
$$
g(a;p) = \sum\limits_{k=0}^{p-1} \omega_p^{ak^2},
$...
- 1,121
2
votes
Accepted
Approximating a fraction with a given denominator
Using continued fraction expansion of the number $M/N$ you can find all best approximations of the first or the second kind. Probably you ask about best approximations of the first kind: a rational ...
- 11.5k
3
votes
Accepted
Can we integrate arbitrary rational functions of Jacobian elliptic functions?
The answer is positive. Rational function of Jacobi elliptic function is elliptic, and for every elliptic function $f$,
$f(z)dz$ is an Abelian differential, and integral of it is an Abelian integral. ...
- 87.2k
3
votes
Approximating a fraction with a given denominator
This can be modelled as two variable integer linear programming, which can be solved in polynomial time. You want to minimize $M r - N k$, subject to $L \leq r \leq (1+\delta)L$ and $M r - N k \geq 0$....
- 1,555
2
votes
Algorithm for grouping tetrahedra from Voronoi diagram
Chapter 27 of The Handbook of Discrete and Computational Geometry
enumerates the complexity of known Delaunay triangulation algorithms of any dimension (see Table 27.2.1 there).
For 3D Delaunay the ...
- 686
1
vote
Accepted
Implementing the $\pi$ BBP algorithm
Bounding this sum is not hard, it is majorized by a geometric progression.
If you forget about the summands starting from $n + p$ (in your terms this means $s = n + p - 1$)
$$\sum_{k = n + p}^{\infty} ...
- 331
Top 50 recent answers are included