6

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 cases at random, and eventually you can paste them together into a set of factors. This notion of an algorithm is very new - at best, 40-50 years old, though in terms of actual practice, perhaps no more than 25 years old. Mathematics in the past has dealt with proofs, which may be constructive or non-constructive. Constructive proofs have historically been given as deterministic algorithms.

Emphasis mine. I know for a fact that the concept is much older than that, as there are numerous algorithms named after people from classical antiquity. This makes me wonder how old the concept of the algorithm really is. Wikipedia merely says that it has existed for centuries, and cites the Sieve of Eratosthenes as an early example. Here I define algorithm as an unambiguous series of steps and procedures to solve a specific problem, particularly a mathematical problem. Note that I am not asking about the terminology, but about the earliest known instance of a well-defined algorithm.

Rodrigo de Azevedo
  • 1
  • 9
  • 15
forest
  • 181
  • 6
  • 2
    The Babylonian method of computing square roots dates back to 60 AD, but I'd expect some stuff to be older still – John Dvorak Feb 23 '19 at 08:08
  • 5
    @JohnDvorak The Euclidean algorithm was described in 300 BCE. –  Feb 23 '19 at 08:09
  • 2
    Egyptians seem to have figured out the multiplication algorithm c 1700-2000 BCE ago. https://en.wikipedia.org/wiki/Timeline_of_algorithms – Denis de Bernardy Feb 23 '19 at 09:04
  • The concept of algorithm is as old as mathematics itself. Ancient Babylonian mathematics consisted mainly of algorithms. This was even before the discovery of proofs. – Alexandre Eremenko Feb 23 '19 at 14:29
  • 4
    If you don't limit it to mathematics, algorithms are as old as life. The algorithm for drinking water (approach pool, open mouth, apply suction, swallow) for example. You might want to use a stricter definition of algorithm. –  Feb 23 '19 at 14:52
  • I think the quote "this notion of an algorithm" refers to an algorithm using randomization as mentioned just before. This is what is at best 40-50 years old. Not algorithms in general. – Gerald Edgar Feb 23 '19 at 22:34
  • 1
    @terdon If someone has written explicit and deterministic step-by-step instructions for solving the problem of drinking water such that a person who does not know how to drink water could follow it and succeed in drinking, I would consider that a legitimate (if silly) instance of an algorithm. – forest Feb 24 '19 at 03:35
  • 1
    @terdon: "The algorithm for drinking water" --- I was thinking (before reading your similar comment) of things like directions (obviously given verbally a long time ago) for travelling from one place to another several-days-journey place, where one needs to avoid dangerous predator watering spots and known human enemy dwellings, and having places where creeks and berry bushes are (i.e. water and food sources), etc. – Dave L Renfro Feb 24 '19 at 08:58
  • I agree with the camp that says any defined series of steps qualifies as an algorithm. So at least as far back as agriculture (plant seed, water field, harvest food), there were algorithms. – Carl Witthoft Feb 25 '19 at 12:34
  • @CarlWitthoft Have those ever been formally defined in a series of unambiguous steps such that a person with absolutely no knowledge of what seeds, water, or harvesting are could perform it identically to a farmer? Simply giving instructions is not sufficient to warrant using the term algorithm. – forest Feb 25 '19 at 22:34
  • 1
    I would be willing to bet that someone with absolutely no knowledge of our use of written symbols and other modern methods of conveying "unambiguous steps" would not even perform it approximately to a farmer. I think a significant problem is asking such a question in a way that isn't highly biased to recent times. Useful reading: Historiographic vices I. Logical attribution and Historiographic vices II. Priority chasing (especially "II"), both from 1975 by Kenneth O. May. – Dave L Renfro Feb 26 '19 at 10:59
  • I remember small Carl Friedrich Gauss story calculating huge sums by a smart trick/algorithm and would suppose the first kind of algorithm was related to addition, as all other kind of mathematical operations can be based on addition. And mathematics started with counting and we know some animals can also count, so humans are the only ones that develop and apply mathematical algorithms to my knowledge. (Maybe interesting to ask on biology.se, but I would be surprised if problem solving strategies applied by sma – user48953094 Feb 23 '19 at 22:01
  • This really depends on how you define "well-defined". Modern mathematicians would say that the concept of an algorithm was formalized in the 1930s, so no well-defined algorithm could have existed before then. – Mark Oct 31 '22 at 22:22

1 Answers1

4

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 problems/solutions, the algorithm is supposed to be clear, and the student can solve similar problems in the same way.

Gerald Edgar
  • 10,307
  • 1
  • 25
  • 42
  • That seems to contain just examples of mathematical problems and their solutions. It may have allowed people to come up with algorithms, but I don't see any explicitly mentioned in it. – forest Feb 24 '19 at 03:40