26 votes
Accepted

Was Kolmogorov enraged after learning about the Karatsuba multiplication algorithm?

Karatsuba's own report can be found in his 1995 paper Сложность вычислений (Complexity of computations). The phrasing he uses is "сильно взволновалo", which Google does translate as "...
Conifold's user avatar
  • 75.7k
11 votes
Accepted

What was the motive for inventing Gröbner bases?

Fortunately, Buchberger himself described the context of his discovery, see Historical background to Gröbner's paper by Abramson. The method, in general outline, was known to Gröbner long before the ...
Conifold's user avatar
  • 75.7k
8 votes
Accepted

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

It is true. Wikipedia links to the website of Ollivier, which hosts both the original posthumous publication in Latin, De investigando ordine systematis aequationum differentialum vulgarium ...
Conifold's user avatar
  • 75.7k
7 votes
Accepted

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

Donald Knuth's The Art of Computer Programming (TAOCP) Vol. 3 "Sorting and Searching" gives a detailed account on the history of ideas, including the sorting by merging, in Chapter 5.5. ...
Hermann Gruber's user avatar
6 votes
Accepted

When was the inverse quadratic interpolation method first used?

According to Maley's Higher Order Approximations to Solutions of Transcendental Systems (1960), the earliest occurrence of the inverse quadratic interpolation for finding roots is in Dandelin's ...
Conifold's user avatar
  • 75.7k
4 votes
Accepted

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

Wegner writes of "pivot element" that partitions the array in Sorting a linked list with equal keys (1982), while none of his references (Sedgewick, Rivest, Loeser, Motzkin) does, as far as ...
Conifold's user avatar
  • 75.7k
4 votes

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

The notation $\sim$ does not mean that ratio $f(x)/g(x)$ has some positive limit $k$, but that it has limit $1$, e.g., $2x + \sqrt{x} \sim 2x$. What math books do you know that define $\sim$ in the ...
KCd's user avatar
  • 5,507
4 votes
Accepted

Were ancient Romans so bad at computations before Arab numerals?

No, Romans were not at all bad at computations before Arab numerals were introduced to them. In fact, Romans had a perfectly fine way of doing computations that was every bit as good as Arabic ...
Big Brother's user avatar
  • 2,157
4 votes

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

Surely the Rhind Papyrus (around 1500 BC) contains many algorithms. At that time, such things were presented this way: State a specific problem, then show how to solve it. After several such ...
Gerald Edgar's user avatar
  • 10.3k
4 votes
Accepted

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

I don't have a fully satisfactory answer, but maybe this helps. First one should note that Tarjan came up with an $O(m \log \log n)$-algorithm roughly at the same time. It's in this technical report: ...
Flowi's user avatar
  • 56
3 votes
Accepted

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

Trial division was used even before Pythagoreans, Euclid's number theory allowed restricting trials to primes, with the sieve of Eratosthenes identifying the primes. Al-Banna explicitly limited the ...
Conifold's user avatar
  • 75.7k
3 votes
Accepted

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

TL; DR. This is one of those cases where "first use" very much depends on what is meant. Depending on that, it can be ascribed to Babylonians (c. 1600 BC), al-Tusi (c. 1250), Briggs (1633), ...
Conifold's user avatar
  • 75.7k
2 votes

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

One example would be Strassen’s matrix multiplication algorithm which can be more efficient than the conventional $O(n^{3})$ algorithm for large enough matrices. Unfortunately, there are numerical ...
Brian Borchers's user avatar
2 votes

History of primality testing

According to this link for the paper "A Brief History of Factoring and Primality Testing B. C. (Before Computers)", Cataldi created a method for primality testing which was verified by ...
Nachiket Kulkarni's user avatar
2 votes

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

The motivation for producing the algorithm was for a convenient way of calculating Easter by arithmetical methods, without requiring reference to extensive tables which was the established method at ...
Steve's user avatar
  • 254
2 votes

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

Adding to Flowi's excellent answer, it seems that the main new ingredient in Yao's algorithm is a linear-time selection algorithm, which was new at the time. I think Yao's algorithm is natural once a ...
Hermann Gruber's user avatar
1 vote

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

The scanned pages might be more readily available here. Indeed the method is presented as a novel; it is only compared to Newton's method. It is first introduced as a method for finding root ...
Lutz Lehmann's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible