Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

10
votes
4answers
5k 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?
15
votes
4answers
8k 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 ...
26
votes
2answers
1k 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 ...
2
votes
3answers
614 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$. ...
1
vote
5answers
8k 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 ...
19
votes
6answers
4k 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 ...
21
votes
2answers
1k 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 ...
23
votes
4answers
6k 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 ...
4
votes
2answers
678 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? ...
4
votes
2answers
2k 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 ...
22
votes
5answers
2k 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 ...
2
votes
2answers
283 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$, ...
25
votes
3answers
7k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
22
votes
4answers
3k 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 < ...
12
votes
4answers
6k views

Non-power-of-2 FFT's?

If I have a program that can compute FFT's for sizes that are powers of 2, how can I use it to compute FFT's for other sizes? I have read that I can supposedly zero-pad the original points, but I'm ...
10
votes
6answers
3k views

Fastest way to calculate $e^x$ upto arbitrary number of decimals?

What are other faster methods of calculating e^x upto any number of decimals other than using the taylor series formula?
5
votes
3answers
2k views

How to accurately calculate the error function erf(x) with a computer?

I am looking for an accurate algorithm to calculate the error function I have tried using [this formula] (http://stackoverflow.com/a/457805) (Handbook of Mathematical Functions, formula ...
0
votes
3answers
93 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 ...
4
votes
3answers
690 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 ...
1
vote
2answers
454 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 \\ ...
12
votes
3answers
914 views

Is there a possibility to choose fairly from three items when every choice can only have 2 options

Me and my wife are often not knowing which DVD to watch. If we have two options we have a simple solution, I put one DVD in one hand behind my back and the other DVD in the other hand. She will ...
10
votes
4answers
2k views

Looking to understand the rationale for money denomination

Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills: $$ s = \sum_{i=1}^k n_i ...
7
votes
1answer
2k views

easy to implement method to fit a power function (regression)

I want to fit to a dataset a power function ($y=Ax^B$). What is the best and easiest method to do this. I need the $A$ and $B$ parameters too. I'm using in general financial data in my project, which ...
6
votes
5answers
4k views

Algorithm to compute Gamma function

The question is simple. I would like to implement the Gamma function in my calculator written in C; however, I have not been able to find an easy way to programmatically compute an approximation to ...
6
votes
3answers
379 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 ...
9
votes
5answers
601 views

Algorithms for “solving” $\sqrt{2}$

The very first words out of my mouth need to be this... "Solving" is the wrong term since I am speaking about irrational numbers. I just don't know which word is the correct word... So that can be ...
1
vote
2answers
872 views

Finding a minimal number of charging stops along the route

The question is: Your electric car needs to be charged every X kilometres. You are doing a road trip from Toronto to Vancouver and have a list of every charging station on the highway between Toronto ...
0
votes
2answers
79 views

Explanation needed on this rather basic recurrence solution

We are studying about recurrences in our analysis of algorithms class. As an example of the substitution method (with induction) we are given the following: $$T(n) = \lbrace 2T\left(\frac{n}{2}\right) ...
20
votes
2answers
747 views

Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$

More precisely, $$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$ This is Theorem 4 ...
9
votes
4answers
3k views

Solving very large matrices in “pieces”

Say you have a very dense matrix that is 30000x30000 elements. The very dense matrix comes from the radiosity equation, which I discussed here. Say you have Ax = B. You have B, and A is 30000x30000 ...
12
votes
6answers
11k views

Determine whether a number is prime

How do I determine if a number is prime? I'm writing a program where a user inputs any integer and from that the program determines whether the number is prime, but how do I go about that?
3
votes
3answers
231 views

Solving inhomogenous ODE

I have an inhomogenous ODE. The main issue here is variables are matrices. It is bit of matrix calculus. A solution would be highly appreciated interms of x . I guess we can use same methods for ...
6
votes
2answers
833 views

Proof of clockwise towers of Hanoi variant recursive solution

This is from one of the exercises in "Concrete Mathematics", and is something I'm doing privately, not homework. This is a variant on the classic towers of Hanoi, where all moves must be made ...
6
votes
2answers
399 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
3
votes
1answer
182 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
3
votes
2answers
2k views

Implementation of Monotone Cubic Interpolation

I'm in need to implement Monotone Cubic Interpolation for interpolate a sequence of points. The information I have about the points are x,y and timestamp. I'm much more an IT guy rather than a ...
5
votes
2answers
332 views

How can I reduce a number?

I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
2
votes
2answers
248 views

Solving recurrences with boundary conditions

I'm trying to follow CLRS ("Introduction to Algorithms") and I just hit a question in a practice assignment I found online that I just can't make any sense of. Consider this problem: Show that ...
1
vote
0answers
242 views

Finding the number of arrangement of N people of different height such that K of them are visible from front

Moderator Note: This is a current contest question on codechef.com. [Initially, I had asked this question in stackoverflow, but someone suggested to post it here, and hence this question is ...
1
vote
2answers
929 views

Need some help with this recurrence equation

I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is ...
1
vote
1answer
77 views

Does this sequence of operators in Hilbert space, given by an algorithm, terminate

Let $H$ be an infinitedimensional Hilbert space and $T$ a compact selfadjoint operator in it. Consider the following Algorithm: Let $$ H_{1}=H,\ T_{1}=T $$ and let $\lambda_{1}$ be that ...
0
votes
1answer
26 views

Any problem computable in $k$ memory slots can be computed with polynomials.

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, ...
0
votes
1answer
625 views

Dominant term and Big Omega

For the given expression, determine the dominant term and then use the dominant term to classify the algorithm in big-O terms and also in $\Omega$-notation. $$n^3+n^2\log_2(n)+n^3\log_2(n)$$ So, I ...
16
votes
1answer
379 views

Books to understand the construction of all groups of a specific order

The algorithms introduced by Besche–Eick (1999) were used to construct (or count) the groups of order up to 2000 in Besche–Eick–O'Brien (2002), yet I find the algorithms somewhat inaccessible. How ...
8
votes
4answers
682 views

How to determine in polynomial time if a number is a product of two consecutive primes?

How to determine in polynomial time if a number is a product of two consecutive primes? All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find ...
11
votes
1answer
1k views

Iterative refinement algorithm for computing exp(x) with arbitrary precision

I'm working on a multiple-precision library. I'd like to make it possible for users to ask for higher precision answers for results already computed at a fixed precision. My $\mathrm{sqrt}(x)$ can ...
11
votes
4answers
1k views

Detecting perfect squares faster than by extracting square root

Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which ...
7
votes
2answers
4k views

Finding irreducible polynomials over GF(2) with the fewest terms

I'm investigating an idea in cryptography that requires irreducible polynomials with coefficients of either 0 or 1 (e.g. over GF[2]). Essentially I am mapping bytes to polynomials. For this reason, ...
7
votes
5answers
1k views

The least prime greater than 2000

I'm a bit curious as to how "real" mathematicians would solve this problem. "Find the least prime number greater than 2000." Of course, I can always go brute force: ...
4
votes
8answers
4k views

Fastest Square Root Algorithm

What is the fastest algorithm for finding the square root of a number? I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release ...