Tagged Questions

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).

2k views

3k views

Are there dictionaries in math?

Consider the following dictionary in the programming language Python: D = {'A': 1, 'B': 2, 'C': 3} It is saying that the value of A is 1, the value of B is 2, ...
2k views

The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I ...
2k 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?
3k 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 ...
12k 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 ...
13k 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 ...
2k views

How can we turn any number into a prime number by simply adding more digits?

How can we turn any number (where the number is > 2) into a prime number by simply appending more digits? I'm referring to the right side of the number. So 4 is not a prime number But If I append ...
6k views

Efficiently finding two squares which sum to a prime

The web is littered with any number of pages (example) giving an existence and uniqueness proof that a pair of squares can be found summing to primes congruent to 1 mod 4 (and also that there are no ...
4k views

Are some real numbers “uncomputable”?

Is there an algorithm to calculate any real number. I mean given $a \in \mathbb{R}$ is there an algorithm to calculate $a$ at any degree of accuracy ? I read somewhere (I cannot find the paper) that ...