# Questions tagged [algorithms]

Mathematical questions about Algorithms, including the analysis of algorithms, combinatorial algorithms, proofs of correctness, invariants, and semantic analyses. See also (computational-mathematics) and (computational-complexity).

11,547 questions
Filter by
Sorted by
Tagged with
11k views

### A multiplication algorithm found in a book by Paul Erdős: how does it work?

I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"): We ...
• 8,913
6k views

• 473
1k views

### Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
• 1,031
6k views

### Is there (or can there be) a general algorithm to solve Rubik's cubes of any dimension?

I love solving Rubik's cube (the usual 3D one). But, a lecture by Matt Parker at the Royal Institute (YouTube Link) led me to an app that can simulate a four dimensional rubik's cube. But ...
• 785
9k views

### Is factoring polynomials as hard as factoring integers?

There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard? One thing I ...
• 7,484
28k views

### Calculator algorithms

Does there exist a good reference on the algorithms used by calculators, especially on the trigonometric and transcendental functions? I would still like to know how Casio generates its random ...
• 2,280
22k views

### How can I find the square root using pen and paper?

Okay, I know this is very basic question. I learned 2 methods in school. But now, I forget one. Here is a simple method that I know. Find the prime divisors of the number Omit the half of numbers ...
5k views

### Computing irrational numbers

I am genuinely curious, how do people compute decimal digits of irrational numbers in general, and $\pi$ or nth roots of integers in particular? How do they reach arbitrary accuracy?
24k views

### Calculate variance from a stream of sample values

I'd like to calculate a standard deviation for a very large (but known) number of sample values, with the highest accuracy possible. The number of samples is larger than can be efficiently stored in ...
• 443
1k views

• 5,828