Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with algorithms
Search options answers only
not deleted
user 11142
Informally, an algorithm is a set of explicit instructions used to solve a problem (e.g. Euclid's algorithm for computing the greatest common divisor of two integers). For more specific questions on algorithms, this tag may be used in conjunction with the approximation-algorithms, algorithmic-randomness and algorithmic-topology tags.
3
votes
Accepted
Is there a closed form for tan(q*pi) with q rational?
$$\tan x = \frac{\exp(i x) - \exp(-i x)}{\exp(i x) + \exp(- i x)}.$$
In your case,
$$\tan (p \pi/q) = \tan (p 2\pi / (2 q).$$
Which equals
$$\frac{\omega^{2p} - 1}{\omega^{2p} + 1},$$
where $\omega …
- 96.4k
3
votes
Groups where word problem is solvable, but not quickly?
A likely example is given by Cremona groups, as in this paper by Serge Cantat (I suspect Yves Cornuiller will comment...)
- 96.4k
6
votes
Determine if an $n$-dimensional mesh of simplices is a non-manifold
In all dimensions, something is a manifold if the link of every cell is a sphere. This, sadly, is undecidable if the dimension of your complex is at least five. It is decidable (but not quickly) for c …
- 96.4k
3
votes
Accepted
Minimum number of unit fractions to sum up a given positive rational
In fact, this is listed as an open problem in the Wikipedia page on Egyptian Fractions, presumably because they do use the output size as a parameter.
- 96.4k
0
votes
Accepted
1
vote
1
vote
Accepted
Computing the ratio of two large integers modulo m
As pointed out in the comments, the problem cannot be solved in the generality you state it in, but the magic words are "chinese remainder theorem". If you have an estimate on the sizes of $P$ and $Q$ …
- 96.4k
6
votes
Accepted
Point in Polygon algorithm from the viewpoint of a robot
Yes, this is correct, the distance you will traverse will be 6.28 meters greater (if you are outside) and 6.28 meters shorter if you are inside, so you better have a very accurate instrument. The rele …
- 96.4k
1
vote
Accepted
SVD complexity for structured sparse matrices
It depends on how small $k$ is. If $k^2 \ll n,$ the simple method of computing $M^t M$ (sparsely), then the Cholesky decomposition, then the eigenvalues, works very well. Perhaps less work is using
h …
- 96.4k
3
votes
partitioning a number into two sets based on sum of digits
Actually, this is a research level question, and here is what's known about it:
http://en.wikipedia.org/wiki/Partition_problem
EDIT If you read the wikipedia article, and follow the links, you will …
- 96.4k
-1
votes
Fast algorithm for counting the number of acyclic paths on a directed graph
I believe the magical words are "topological sort".
- 96.4k
5
votes
Find the maximum set whose subset sum is unique for every of its subset.
This has been studied, see
http://www.mathnet.or.kr/mathnet/kms_tex/978590.pdf
and the somewhat more interesting:
NEWMAN POLYNOMIALS
WITH PRESCRIBED VANISHING AND INTEGER SETS WITH DISTINCT SUBSET …
- 96.4k
5
votes
Fastest algorithm to compute (a^(2^N))%m?
I am not sure I understand the question, but if $m \ll 2^N,$ the obvious thing to do is to compute $x = 2^N \mod \phi(m)$ [by repeated squaring], and then compute $a^x \mod m.$ If $2^N$ is not huge co …
- 96.4k
1
vote
An algorithm for checking if a nonlinear function f is always positive
The non negativity of polynomials can also be related to the Fejer-Riesz theorem (which deals with trigonometric polynomials on the unit circle), there are fast approximate algorithms based on signal processing …
- 96.4k
0
votes
For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very hug...
The wikipedia article is quite enlightening on the Pisano period, but from the algorithmic viewpoint, it shows that you only need to compute the period for $n$ a prime power $p^k,$, and in that case i …
- 96.4k