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

learn more… | top users | synonyms (1)

33
votes
4answers
8k 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?
17
votes
4answers
10k 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 ...
22
votes
6answers
5k 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 ...
28
votes
2answers
2k views

A natural number multiplied by some integer results in a number with only ones and zeros

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 ...
24
votes
2answers
2k 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 ...
2
votes
3answers
721 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
13k 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 ...
26
votes
4answers
9k 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 ...
5
votes
2answers
1k 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? ...
7
votes
3answers
3k 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
571 views

Horse Race question: how to find the 3 fastest horses?

There are 25 horses. You can take 5 of the horses at a time and race them. Each horse always finishes the race in the same amount of time, and there are no ties. The only information you get from each ...
25
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 < ...
24
votes
5answers
3k 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 ...
8
votes
4answers
4k 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 ...
6
votes
3answers
522 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 ...
5
votes
2answers
8k views

How to solve this recurrence $T(n) = 2T(n/2) + n\log n$

How can I solve the recurrence relation $T(n) = 2T(n/2) + n\log n$? It almost matches the Master Theorem except for the $n\log n$ part.
9
votes
5answers
708 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 ...
3
votes
2answers
342 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$, ...
18
votes
4answers
10k 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 ...
28
votes
3answers
12k 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 ...
10
votes
6answers
5k views

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

What are other faster methods of calculating $e^x$ up to any number of decimals other than using the Taylor series formula?
15
votes
5answers
2k 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
6answers
6k 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 ...
0
votes
3answers
116 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
1k 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
566 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
1k 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 ...
3
votes
3answers
357 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 ...
11
votes
4answers
3k 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 ...
9
votes
1answer
3k 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 ...
3
votes
2answers
168 views
0
votes
2answers
123 views

To fast invert a real symmetric positive definite matrix that is almost similar to Toeplitz

It is well known how to solve a Toeplitz system Ax = b, of a matrix A, n x n elements, ...
5
votes
1answer
114 views

filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
3
votes
2answers
273 views

Algorithm for creating binary rational numbers

I read here an algorithm to convert a decimal rational number to binary by multiplications by 2, but although it's very simple to carry on, I still haven't managed to explain myself why it works. ...
2
votes
2answers
1k views

Expressing a Non Negative Integer as Sums of Two Squares

I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ...
1
vote
3answers
1k 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 ...
1
vote
2answers
261 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
0
votes
2answers
98 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) ...
21
votes
2answers
807 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 ...
11
votes
4answers
5k 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
16k 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?
7
votes
2answers
1k 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
3answers
3k views

gradient descent optimal step size

Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
4
votes
2answers
4k 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 ...
7
votes
1answer
5k views

Efficiently find the generators of a cyclic group

Is there any efficient method to find the generators of a cyclic group? Edit: The (cyclic)group here refers to a general multiplicative group of prime modulo. Is there any efficient algorithm to find ...
6
votes
2answers
478 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 ...
6
votes
3answers
2k views

What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$. Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of ...
3
votes
1answer
227 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 ...
2
votes
1answer
260 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
6
votes
3answers
385 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...