Questions tagged [algorithm]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
1 answer
104 views

First use of ~ and ≍ (\sym and \asymp)

The relations ~ and ≍ are frequently used in math and computer science, at least within number theory and analysis of algorithms. What is their origin? Definitions Suppose $g(x)$ is an eventually-...
Charles's user avatar
  • 131
1 vote
1 answer
215 views

What are some examples of galactic algorithms that have become practical?

On the Wikipedia article for galactic algorithm (an algorithm that only becomes efficient when the inputs are so large that the algorithm is not used in practice), one of the use cases is that ...
David Lui's user avatar
  • 111
3 votes
0 answers
216 views

Who came up with the proof of "Bézout's identity" that uses the well-ordering principle?

Let $a$ and $b$ be two integers not both of which are equal to zero. It is an important and well-known fact that $\text{gcd}(a,b)=ax_{0}+by_{0}$ for some integers $x_{0}$ and $y_{0}$. Even though this ...
José Hdz. Stgo.'s user avatar
2 votes
1 answer
165 views

History of primality testing

Consider a uniform random variable $n$ which is an integer in the interval $2^{1023} < n < 2^{1024}$. What is the oldest algorithm capable of determining whether or not $p$ is a probable prime ...
forest's user avatar
  • 181
1 vote
1 answer
160 views

Did the 1800 Gregorian Lunar Correction Motivate Gauss' Computus Algorithm?

When the Gregorian calendar was implemented in 1582, one of its adjustments was the lunar correction---to increase the epact by 1 eight times within a span of 2500 years; specifically, seven times ...
DDS's user avatar
  • 277
5 votes
2 answers
2k views

How did von Neumann come up with his merge sort algorithm?

Since merge sort is the first $O(n \log n)$ time general purpose sorting algorithm I find it rather surprising that it was discovered without having any obvious conceptual predecessors. Are there any ...
GEP's user avatar
  • 1,516
2 votes
1 answer
124 views

Where does the term "pivot" come from in the quicksort algorithm?

The quicksort algorithm is based on recursively choosing an element to partition the array. In every modern exposition that I've seen, this element is called the "pivot". However, as far as ...
Matt Hancock's user avatar
17 votes
1 answer
4k views

Was Kolmogorov enraged after learning about the Karatsuba multiplication algorithm?

Some years ago, I read that Kolmogorov was so enraged that Karatsuba disproved one of his conjectures that he terminated his seminar shortly thereafter. This Wikipedia page claims that Kolmogorov was ...
GEP's user avatar
  • 1,516
4 votes
2 answers
586 views

How did Yao come up with his minimum spanning tree algorithm?

I recently stumbled upon this text about Yao's algorithm for the minimum spanning tree (MST) and I was wondering if there are some preceding algorithms (other than Sollin's algorithm) that were ...
GEP's user avatar
  • 1,516
3 votes
1 answer
128 views

When was the problem of factoring integers explicitly considered, what was the oldest factoring algorithm?

I know Gauss made it clear that he wanted an efficient solution to the problem in 1801. In his Disquisitiones Arithmeticae he calls all factoring algorithms "laborious and prolix", surely a 19th-...
user724963's user avatar
3 votes
1 answer
297 views

When is the first use of Newton's method for root finding?

I saw this from Wikipedia. The name "Newton's method" is derived from Isaac Newton's description of a special case of the method in De analysi per aequationes numero terminorum infinitas (written in ...
Mathrix's user avatar
  • 111
2 votes
1 answer
101 views

When was the Laguerre's method first used to approximate roots?

Is there a specific date when Laguerre published his root finding method? I found his 1880 note Résolution des équations numériques, but I am not sure if this is the source because I can not read ...
Mathrix's user avatar
  • 111
4 votes
1 answer
131 views

When was the inverse quadratic interpolation method first used?

Do you know anything about it? I couldn't really find something useful on web.
Mathrix's user avatar
  • 111
6 votes
1 answer
588 views

What was the motive for inventing Gröbner bases?

How did professor Buchberger discover Gröbner (Groebner) bases for polynomial ideals? What was the problem(s) that lead to such a discovery?
Tedebbur's user avatar
  • 203
6 votes
1 answer
467 views

Did Jacobi invent the Hungarian algorithm for the assignment problem over a century before Kőnig and Egerváry?

Wikipedia says: In 2006, it was discovered that Carl Gustav Jacobi had solved the assignment problem in the 19th century, and the solution had been published posthumously in 1890 in Latin. The ...
Anton Petrunin's user avatar
7 votes
1 answer
1k views

Were ancient Romans so bad at computations before Arab numerals?

It is often said that Romans (see below) had a terrible number system, which made computations a mess. I do believe this, but I'm suspicious of the claim that nobody had better ways to do computations ...
seldon's user avatar
  • 165
6 votes
1 answer
285 views

What is the earliest instance of the use of an algorithm to solve problems?

In reading a description on Usenet of a NIST competition for selecting a standard cipher, I read: Consider that the best currently known methods for factoring use randomization: Construct enough ...
forest's user avatar
  • 181
0 votes
0 answers
54 views

Frege alluded to a logic algorithm?

Somewhere (I wish I remember where) I read that Gottlob Frege, although he didn't invent a logic algorithm, alluded to one (the Quine–McCluskey algorithm? something else? converting truth tables to ...
Geremia's user avatar
  • 5,239
14 votes
1 answer
15k views

Who invented short and long division?

I am curious who came up with algorithms that we use today to manually solve mathematical division problems, such as short or long division; how were they established or standardized that way and why?...
Rok's user avatar
  • 243