Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses
6
votes
3answers
1k views
How to use the Extended Euclidean Algorithm manually?
I've only found a recursive algorithm of the extended Euclidean algorithm. I'd like to know how to use it by hand. Any idea?
11
votes
4answers
4k views
Simple explanation and examples of the Miller-Rabin Primality Test
Coming from an understanding of Fermat's primality test, I'm looking for a clear explanation of the Miller-Rabin primality test.
Specifically: I understand that for some reason, having non-trivial ...
2
votes
3answers
412 views
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$.
...
22
votes
2answers
831 views
Proof that a natural number multiplied by some integer results in a number with only one and zero as digits
I recently solved a problem, which says that,
a positive integer can be multiplied with another integer resulting in
a positive integer that is composed only of one and zero as digits.
How can ...
4
votes
2answers
387 views
Tranforming 2D outline into 3D plane
I am writing a program where I would like to allow the user to draw 4 connecting lines, such as:
And convert this shape into a 3D plane. Is this possible? Is there an existing algorithm to do so? ...
3
votes
3answers
328 views
What is step by step logic of pinv (pseudoinverse)?
So we have a matrix $A$ size of $M \times N$ with elements $a_{i,j}$. What is a step by step algorithm that returns the Moore-Penrose inverse $A^+$ for a given $A$ (on level of ...
2
votes
2answers
198 views
Rewriting repeated integer division with multiplication
In many programming languages, such as C and C++, integer division of positive numbers is defined by simply ignoring the remainder. $5 / 2 == 2$.
In general, is it true of positive integers $a$, $b$, ...
3
votes
2answers
708 views
How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?
I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice.
I've spent quite ...
5
votes
3answers
1k views
How to accurately calculate erf(x) with a computer?
I am looking for an accurate algorithm to calculate the error function. I have tried using this formula (Handbook of Mathematical Functions, formula 7.1.26), but the results are not accurate enough ...
1
vote
4answers
4k views
Solution of tanx = x?
How do I find the solutions of tanx = x upto any number of decimals?
(Of course, there is the graphical method but it just helps in finding the approximate ...
0
votes
3answers
81 views
How can $n \lg n = O(n^{log_3 4 - r})$?
How can I understand this bound, for me it is not true.
$$n\lg n = O(n^{\log_3 4 - r})$$
where $\lg n = \log_2 n$ and $r > 0$
I'm trying to solve this recurrence $T(n) = 4T(n/3) + n\lg n$ using ...
18
votes
3answers
1k views
Find taxicab numbers in $O(n)$ time
This is a final exam question in my algorithms class:
$k$ is a taxicab number if $k = a^3+b^3=c^3+d^3$, $a,b,c,d$ are distinct positive integers. Find all taxicab number $k$ such that $a,b,c,d < ...
19
votes
5answers
1k 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 ...
1
vote
2answers
310 views
Euclidean algorithm to find the GCD
I have to find the greatest common divisor of $a=78$ and $b=132$.
I have worked out to
$$\begin{align}
132 & = 78 \times 1 + 54 \\
78 & = 54 \times 1 + 24 \\
54 & = 24 \times 2 + 6 \\
...
6
votes
3answers
277 views
Optimal algorithm for finding the odd spheres
Say we have $N$ [$3 \le N \le 100,000$] spheres indexed as $1,2,3,\cdots N$,all of them have identical weight apart from one.We have to determine which sphere it is (index) by using only the pair of ...
