Skip to main content

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

Filter by
Sorted by
Tagged with
87 votes
5 answers
35k 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?
Andrew's user avatar
  • 2,307
29 votes
5 answers
21k views

Split $n$ into nontrivial factors via a nontrivial square-root of $1\!\pmod{\!n}$

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 ...
Smashery's user avatar
  • 465
44 votes
7 answers
17k 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 ...
timday's user avatar
  • 704
29 votes
3 answers
23k views

How to integrate $ \int \frac{x}{\sqrt{x^4+10x^2-96x-71}}dx$?

I read about $ \int \dfrac{x}{\sqrt{x^4+10x^2-96x-71}}dx$ on the Wikipedia Risch algorithm page. They gave an answer but I don't understand how they got it.
Hashir Omer's user avatar
  • 1,748
51 votes
2 answers
9k 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 I ...
Priyank Bhatnagar's user avatar
7 votes
2 answers
2k views

How does Mathematica solve $f(x)\equiv 0\pmod p$?

I input ...
lsr314's user avatar
  • 15.9k
6 votes
4 answers
2k views

How to solve Kepler's equation $M=E-\varepsilon \sin E$ for $E$?

I'm trying to create a program to solve a set of Kepler's Equation and I cannot isolate the single variable to use the expression in my program. The Kepler Equation is $$M = E - \varepsilon \sin(E)...
hawaii's user avatar
  • 163
62 votes
8 answers
248k views

Is there a way to get trig functions without a calculator?

In school, we just started learning about trigonometry, and I was wondering: is there a way to find the sine, cosine, tangent, cosecant, secant, and cotangent of a single angle without using a ...
Jonathan Lam's user avatar
87 votes
4 answers
14k views

Fastest way to check if $x^y > y^x$?

What is the fastest way to check if $x^y > y^x$ if I were writing a computer program to do that? The issue is that $x$ and $y$ can be very large.
learner's user avatar
  • 925
6 votes
5 answers
56k 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 value.....
Pushpak Dagade's user avatar
85 votes
3 answers
72k views

What algorithm is used by computers to calculate logarithms?

I would like to know how logarithms are calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
zar's user avatar
  • 4,602
36 votes
3 answers
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 ...
Chris Brooks's user avatar
  • 7,484
11 votes
3 answers
1k views

What does $\!\bmod(n,x^r-1)$ mean? [in AKS primality test]

Where does a layman go to get a basic understanding of AKS primality testing. I am not talking about the optimal choice of $r$ (which I am told is the hardcore number-theoretic part of the algorithm). ...
Gary's user avatar
  • 111
29 votes
6 answers
24k 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?
Pushpak Dagade's user avatar
28 votes
7 answers
24k 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 ...
houbysoft's user avatar
  • 553
3 votes
3 answers
3k views

How is this possible to convert a long string to a number with less characters?

I'm going to write a program (function) that can convert a long string to a number. For this, first I convert each character (letter) to a number; like ...
Mohammad Kermani's user avatar
38 votes
3 answers
9k views

Quickest way to determine a polynomial with positive integer coefficients

Suppose that you are given a polynomial $p(x)$ as a black box (i.e. some oracle, to which you feed $x$ and it returns $p(x)$). It is known that the coefficients of $p(x)$ are all positive integers. ...
gt6989b's user avatar
  • 54.5k
18 votes
6 answers
3k 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 ...
Peter Smit's user avatar
9 votes
3 answers
9k 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 ...
dimo414's user avatar
  • 557
36 votes
4 answers
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 ...
John Smith's user avatar
  • 2,280
34 votes
12 answers
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?
user avatar
29 votes
8 answers
54k views

Fastest Square Root Algorithm

(edit, 9 years later... hello smart contract developers, I know that's why you're here lol) What is the fastest algorithm for finding the square root of a number? I created one that can find the ...
Albert Renshaw's user avatar
22 votes
6 answers
27k views

How to accurately calculate the error function $\operatorname{erf}(x)$ with a computer?

I am looking for an accurate algorithm to calculate the error function $$\operatorname{erf}(x)=\frac{2}{\sqrt{\pi}}\int_0^x e^{-t^2}\ dt$$ I have tried using the following formula, (Handbook of ...
badp's user avatar
  • 1,266
22 votes
5 answers
5k views

Algorithm(s) for computing an elementary symmetric polynomial

I've run into an application where I need to compute a bunch of elementary symmetric polynomials. It is trivial to compute a sum or product of quantities, of course, so my concern is with computing ...
Juan Joder's user avatar
16 votes
2 answers
25k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
Severyn Kozak's user avatar
12 votes
4 answers
10k views

How to find the 3 fastest horses?

There are $25$ horses. You can take $5$ 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 ...
Matt Matic's user avatar
7 votes
4 answers
569 views

Coefficient extraction,show: $[z^n]\frac{1}{(1-z)^{\alpha + 1}} \log \frac{1}{1-z} = \binom{n + \alpha }{n} (H_{n+\alpha} - H_{\alpha})$

I want to show: \begin{equation*} [z^n]\frac{1}{(1-z)^{\alpha + 1}} \log \frac{1}{1-z} = \binom{n + \alpha }{n} (H_{n+\alpha} - H_{\alpha}). \end{equation*} where $[z^n]$ means the $n$-th ...
Orb's user avatar
  • 1,060
2 votes
3 answers
1k 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$. ...
Rushil Paul's user avatar
27 votes
6 answers
9k 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 ...
MJD's user avatar
  • 65.7k
24 votes
8 answers
61k views

Determining if an arbitrary point lies inside a triangle defined by three points?

Is there an algorithm available to determine if a point P lies inside a triangle ABC defined as three points A, B, and C? (The three line segments of the triangle can be determined as well as the ...
Casey's user avatar
  • 409
16 votes
5 answers
7k views

Algorithms for approximating $\sqrt{2}$

Well, "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 part $1$ of my question... what is the correct word ...
Albert Renshaw's user avatar
12 votes
3 answers
5k views

Optimal algorithm for finding the odd sphere with a balance scale

Say we have $N$ spheres indexed as $1,2,3,\dotsc, N$ such that all of them have identical weight apart from one, and we don't know if that one is heavier or lighter. We have to determine which sphere ...
Quixotic's user avatar
  • 22.5k
12 votes
2 answers
13k views

Efficient computation of the minimum distance of a binary linear code

I need to find parameters $n$, $k$ and $d$ of a binary linear code from its Generator Matrix. How can I find parameter $d$ efficiently? I know the method that compute all the codewords and take ...
geek_guy's user avatar
  • 303
38 votes
2 answers
129k views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...
Stephen Clark's user avatar
31 votes
3 answers
42k views

Algorithm to get the maximum size of n squares that fit into a rectangle with a given width and height

I am looking for an algorithm that can return the number of size of n squares that fit into a a rectangle of a given width and height, maximizing the use of space (thus, leaving the least amount of ...
Anton's user avatar
  • 413
27 votes
2 answers
3k 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 ...
sigma.z.1980's user avatar
  • 1,727
22 votes
2 answers
143k 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.
cody's user avatar
  • 753
11 votes
4 answers
14k views

Finding location of a point on 2D plane, given the distances to three other know points

I need to find location of the point $s_0$; the locations of other three points ($s_1$, $s_2$, $s_3$) are known. $d_i$ are known distances. Given: $x_1$, $x_2$, $x_3$, $y_1$, $y_2$, $y_3$, $d_1$, $...
hkBattousai's user avatar
  • 4,583
11 votes
3 answers
10k 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 manipulations/...
Kabumbus's user avatar
  • 438
9 votes
1 answer
4k views

maximum eigenvalue of a diagonal plus rank-one matrix

I want to compute the maximum eigenvalue of a diagonal plus rank-one matrix. Are there fast algorithms for the computation of the largest eigenvalue? What is the computational complexity of those ...
lbla's user avatar
  • 93
5 votes
3 answers
12k views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
Eric's user avatar
  • 175
35 votes
7 answers
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 ...
Shiplu Mokaddim's user avatar
29 votes
5 answers
6k 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 ...
Ricky Bobby's user avatar
22 votes
6 answers
4k views

Fast exponentiation algorithm - How to arrive at it?

I've been learning about fast exponentiation when I found this algorithm: ...
jayno's user avatar
  • 231
19 votes
5 answers
11k views

Find the inverse of a submatrix of a given matrix

I have a $A$ matrix $4 \times 4$. By delete the first row and first column of $A$, we have a matrix $B$ with sizes $3 \times 3$. Assume that I have the result of invertible A that denote $A^{-1}$ ...
John's user avatar
  • 802
18 votes
4 answers
9k views

Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time. Given a set of ...
Michael's user avatar
  • 283
14 votes
1 answer
14k 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 ...
czerasz's user avatar
  • 241
9 votes
2 answers
2k views

How do Gap generate the elements in permutation groups?

I understand that permutationgroups in Gap are represented by generators, which seems to be far more efficient than groups represented by all it's elements, but how could then for example ...
Lehs's user avatar
  • 13.9k
7 votes
2 answers
4k views

Transforming $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? If ...
Groky's user avatar
  • 201
4 votes
2 answers
968 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$, ...
David Stone's user avatar

1
2 3 4 5
20