# Tag Info

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 "...
• 75.3k
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 ...
• 75.3k
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 ...
• 75.3k
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. ...
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 ...
• 75.3k
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 ...
• 75.3k

### 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 ...
• 5,322
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 ...
• 2,157

### 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 ...
• 10.3k
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: ...
• 56
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 ...
• 75.3k
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), ...
• 75.3k

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

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

### 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 ...
• 254