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
118 votes
5 answers
11k views

A multiplication algorithm found in a book by Paul Erdős: how does it work?

I am trying to understand the following problem from Erdős and Surányi's Topics in the theory of numbers (Springer), chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"): We ...
iadvd's user avatar
  • 8,913
96 votes
3 answers
6k views

Complexity class of comparison of power towers

Consider the following decision problem: given two lists of positive integers $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_m$ the task is to decide if $a_1^{a_2^{\cdot^{\cdot^{\cdot^{a_n}}}}} < ...
Vladimir Reshetnikov's user avatar
87 votes
3 answers
167k views

Meaning of “arg min”

Would someone be so kind to explain this to me: $$\pi_nk=\left\{\begin{array}{cl}1&\textrm{if }k=\arg\min_j\left\Vert\mathbf x_n-\mu_j\right\Vert^2\\0&\textrm{otherwise}\end{array}\right..$$ ...
Olivier_s_j's user avatar
  • 1,035
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
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
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
80 votes
8 answers
46k views

incremental computation of standard deviation

How can I compute the standard deviation in an incremental way (using the new value and the last computed mean and/or std deviation) ? for the non incremental way, I just do something like: $$S_N=\...
shn's user avatar
  • 1,062
70 votes
4 answers
23k views

Why does multiplying a number on a clock face by 10 and then halving, give the minutes? ${}{}$

My daughter in grade 3 is learning about telling time at her school. She eagerly showed me this method she has discovered on her own to tell the minutes part of the time on an analogue clock. I wasn't ...
Sabeen Malik's user avatar
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
57 votes
2 answers
5k views

How do the Catalan numbers turn up here?

The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an ...
ShreevatsaR's user avatar
  • 41.6k
52 votes
6 answers
4k views

Finding the largest equilateral triangle inside a given triangle

My wife came up with the following problem while we were making some decorations for our baby: given a triangle, what is the largest equilateral triangle that can be inscribed in it? (In other words: ...
ShreevatsaR's user avatar
  • 41.6k
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
51 votes
5 answers
9k 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, ...
user356363's user avatar
51 votes
7 answers
34k views

How does one compute the sign of a permutation?

The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula $${\rm sgn}(\sigma) =...
Chris Taylor's user avatar
  • 29.1k
47 votes
22 answers
14k views

What does Big O actually tell you?

Two days ago I felt very uncomfortable with Big O notation. I've already asked two questions: Why to calculate "Big O" if we can just calculate number of steps? The main idea behind Big O ...
mathgeek's user avatar
  • 930
47 votes
1 answer
3k views

Sums of prime powers

You are given positive integers N, m, and k. Is there a way to check if $$\sum_{\stackrel{p\le N}{p\text{ prime}}}p^k\equiv0\pmod m$$ faster than computing the (modular) sum? For concreteness, you ...
Charles's user avatar
  • 32.2k
45 votes
3 answers
177k views

How do I calculate Euclidean and Manhattan distance by hand?

I have a practice problem that I am working on (artificial intelligence), but am unable to calculate the Euclidean and Manhattan distances by hand using the following values: ...
SnookerFan's user avatar
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
43 votes
3 answers
43k 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 ...
user541686's user avatar
  • 13.9k
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
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
38 votes
1 answer
3k views

Is War necessarily finite?

War is an cardgame played by children and drunk college students which involves no strategic choices on either side. The outcome is determined by the dealing of the cards. These are the rules. A ...
Alexander Gruber's user avatar
  • 27.2k
37 votes
10 answers
55k views

Efficient way to determine if a number is Perfect Square

Is there an efficient method to determine if a very large number (300 - 600 digits) is a perfect square without finding its square root. I tried finding the square root but I realized that even for ...
Obinna Okechukwu's user avatar
37 votes
3 answers
43k views

Computational complexity of least square regression operation

In a least square regression algorithm, I have to do the following operations to compute regression coefficients: Matrix multiplication, complexity: $O(C^2N)$ Matrix inversion, complexity: $O(C^3)...
Andree's user avatar
  • 473
37 votes
0 answers
1k views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
Rodrigo's user avatar
  • 1,031
36 votes
3 answers
6k views

Is there (or can there be) a general algorithm to solve Rubik's cubes of any dimension?

I love solving Rubik's cube (the usual 3D one). But, a lecture by Matt Parker at the Royal Institute (YouTube Link) led me to an app that can simulate a four dimensional rubik's cube. But ...
Martin Medro's user avatar
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
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
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
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
34 votes
2 answers
24k views

Calculate variance from a stream of sample values

I'd like to calculate a standard deviation for a very large (but known) number of sample values, with the highest accuracy possible. The number of samples is larger than can be efficiently stored in ...
user6677's user avatar
  • 443
34 votes
2 answers
1k views

Can every number be written as a small sum of sums of squares?

In a practice for a programming competition, one problem asked us to find the smallest number of pyramids which can be built using exactly $n$ blocks, where pyramids have either $k\times k, (k-1)\...
Alex Becker's user avatar
  • 60.8k
33 votes
6 answers
3k 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 ...
Haha's user avatar
  • 5,658
32 votes
1 answer
5k 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 ...
CoffeDeveloper'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
31 votes
1 answer
59k views

When does a Square Matrix have an LU Decomposition?

When can we split a square matrix (rows = columns) into it’s LU decomposition? The LUP (LU Decomposition with pivoting) always exists; however, a true LU decomposition does not always exist. How do ...
Highrule's user avatar
  • 411
31 votes
1 answer
1k views

Are these fast convergent series for the lemniscate constant and $\Gamma(\frac{1}{3})$ already known?

[Updated on Nov.10, Dec.05.2023 and Feb.18.2024] Applying a similar approach followed in these MO questions, for Catalan's and Apery's Constants, i.e. Wilf-Zeilberger proofs starting from Dougall's ...
Jorge Zuniga's user avatar
30 votes
4 answers
5k views

Is there a branch of Mathematics which connects Calculus and Discrete Math / Number Theory?

I am asking this question out of both curiosity and frustration. There are many problems in computer science which require you to perform operations on a finite set of numbers. It always bothers me ...
Silver's user avatar
  • 1,486
30 votes
2 answers
33k views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
alh's user avatar
  • 471
30 votes
2 answers
633 views

Can algebraic numbers be compared using only rational arithmetic?

I was working on a program to carry out some computations, and ran into an issue of needing to compare some algebraic numbers, but not having enough precision to do it without exact arithmetic, and ...
Milo Brandt's user avatar
  • 61.1k
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
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
29 votes
4 answers
4k views

Each person has at most 3 enemies in a group. Show that we can separate them into two groups where a person will have at most one enemy in the group.

The question that I saw is as follows: In the Parliament of Sikinia, each member has at most three enemies. Prove that the house can be separated into two houses, so that each member has at most ...
user 6663629's 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
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
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
29 votes
2 answers
40k views

What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?

I looked it up online in many sites but none give a clear answer. They all give a lot of complicated mathematical stuff which is not only hard for me to grasp but also irrelevant as I simply want to ...
Ivy Mike's user avatar
  • 1,177
29 votes
2 answers
3k views

A constrained topological sort?

Suppose that one has a directed, acyclic graph G, and each vertex $v$ contains a (positive) value $a_v$. Additionally, let $r$ be a constant. For my purposes, $r>1$, but this might not matter. ...
Aaron's user avatar
  • 24.5k
28 votes
5 answers
8k 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$, and $a,b,c,d$ are distinct positive integers. Find all taxicab numbers $k$ such that $a,b,c,d &...
Chao Xu's user avatar
  • 5,828
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

1
2 3 4 5
231