28
$\begingroup$

Edit: I choice the answer with highest score by December 06, 2012.

This is a soft question.

The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?

In this wiki entry, Rabin's algorithm for the closest pair problem in computational geometry was given as the first randomized algorithm (year???). Lipton introduced Rabin's algorithm as the start of the modern era of random algorithms here, but not as the first one. I also know many algorithms for probabilistic finite automata (a very simple computational model) discovered during 1960s.

Do you know any probabilistic/randomized algorithms (or method) even before 1960s?

or

Which finding can be seen as the first probabilistic/randomized algorithm?

Improve this question
$\endgroup$
4
  • 26
    $\begingroup$ The age-old idea of tasting a spoonful of boiling soup to check if it tastes right is essentially random sampling, a probabilistic algorithm with provable guarantees. $\endgroup$
    – arnab
    Commented Sep 11, 2012 at 20:18
  • 3
    $\begingroup$ Rabin's algorithm was published in 1976, long after "modern" computer science was well-established. $\endgroup$
    – Jeffε
    Commented Sep 11, 2012 at 21:53
  • $\begingroup$ Could you perhaps clarify if there are any criteria which you would like to impose on "algorithms", in order to clarify whether you think e.g. that natural phenomena which predate humanity by billions of years represent "algorithms", as suggested by some of the responses below? $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 16:05
  • $\begingroup$ @NieldeBeaudrap: What in my mind was some mathematically well-defined algorithms. (But, personally, I like arnab's answer very much :)) $\endgroup$
    – Abuzer Yakaryilmaz
    Commented Sep 15, 2012 at 15:13

10 Answers 10

Reset to default
34
$\begingroup$

This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers"

In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form. In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of Quadratic Reciprocity, which is a defect in the method. But as for each value of u half the values of t are suitable, there should be no difficulty in finding one."

So this is one of the first explicit mentions of a randomized algorithm.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ This is a really nice reference. Has Pocklington's Algorithm since been derandomized? Tangentially, I love your work - both in and out of CS - in particular your algorithm for Bachet's conjecture (the paper was hard to find a copy of though!) but also your civil liberties work. Have you watched Errol Morris's "Mr. Death?" $\endgroup$
    – Ross Snider
    Commented Sep 12, 2012 at 17:02
  • $\begingroup$ interesting. it's reminiscent of randomized primality testing $\endgroup$
    – Sasho Nikolov
    Commented Sep 13, 2012 at 15:43
  • 3
    $\begingroup$ And a Las Vegas algorithm too! Nice reference. $\endgroup$
    – David Eppstein
    Commented Sep 13, 2012 at 15:43
  • $\begingroup$ Very nice reference. $\endgroup$
    – Jérémie
    Commented Sep 14, 2012 at 13:53
  • $\begingroup$ speaking of factoring before computers, does anyone know what Lehmer knew about the pocklington algorithm, or any other randomized algorithms, or whether Lehmer actually ever implemented it on his sieve factoring computer? the two apparently have some connection with the Pocklington-Lehmer primality test acc to wikipedia $\endgroup$
    – vzn
    Commented Sep 20, 2012 at 18:07
28
$\begingroup$

Buffons needle algorithm for estimating $\pi$, basically a Monte Carlo method, dates to publication in 1777. note that Monte Carlo methods date to the 1940s with the US "Manhattan" atom bomb project & were coinvented by Ulam, Von Neumann, and Metropolis.

Improve this answer
$\endgroup$
2
  • 8
    $\begingroup$ Actually this is related to a question that I asked. Nobody knows exactly who devised the algorithm that many people take to be Buffon's needle nowadays. $\endgroup$
    – Jérémie
    Commented Sep 11, 2012 at 21:33
  • $\begingroup$ stated more exactly— there is a clearcut Buffon needle algorithm which involves dropping needles on stripes, and an apparently much different "random point vs circle" algorithm as you mention in that question which some people seem to incorrectly attribute to Buffon, with different, more modern, but uncertain origins. $\endgroup$
    – vzn
    Commented Sep 15, 2012 at 16:28
19
$\begingroup$

The Metropolis–Hastings algorithm was published in 1953 and dates back earlier to the Manhattan project, long before Rabin. Like many of the early randomized methods given in other answers, it is a Monte Carlo algorithm.

Is it possible that the claim on the Wikipedia page is a garbled form of the claim that Rabin's was the first Las Vegas algorithm?

Improve this answer
$\endgroup$
11
$\begingroup$

In my opinion, natural evolution is a good and rather old probabilistic algorithm :-)

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ +1 although the description of the process as probabilistic us much more recent. ;-) $\endgroup$
    – Konrad Rudolph
    Commented Sep 12, 2012 at 14:41
  • 7
    $\begingroup$ "Algorithm" suggests that there is a problem it is trying to solve; but it isn't. It isn't even "trying" to make animals which are better at surviving; creating animals which are adapted to its environment is just a byproduct (one which is not always achieved, as extinction and mass-extinction events make evident). In this respect, evolution is no more an algorithm than gravity is; it's just this thing which sort of happens. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 15:33
  • $\begingroup$ MDB is dead on! evolution is a genetic algorithm that selects for evolutionary fitness and science is still catching up with all the implications of this.... ie its an active area of research. it hasnt been pointed out much or widely appreciated, but the phenomenal success of GAs in CS is actually strong mathematical/scientific evidence of the reality of biological evolution theory. however, concede it is definitely different than other "algorithms" in some key ways. $\endgroup$
    – vzn
    Commented Sep 13, 2012 at 15:44
  • 2
    $\begingroup$ @vzn: a "genetic algorithm", first of all, selects for a fitness function which we impose for a specific purpose. We use evolution as a tool to do something in that case. But that doesn't mean that biological evolution is an algorithm to do anything. Using the gravity analogy again, is there a meaningful sense in which all waterfalls are algorithms, just because we sometimes use waterfalls to generate electricity? $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 15:56
  • 4
    $\begingroup$ @vzn: I merely assert that "an algorithm" should entail well-defined parameters of probability of success, not to mention that there should be an agent which carries it out. The only 'agent' which could be said to carry out "evolution" would be an entire ecosystem. What should we say that the ecosystem is "trying" to achieve? I would as readily say that you are anthropomorphising nature. I only demand that "applying an algorithm" entail some amount of goal-oriented intentionality, applied by humans or no. In what sense can a process without a goal represent an "algorithm"? $\endgroup$
    – Niel de Beaudrap
    Commented Sep 15, 2012 at 18:08
11
$\begingroup$

The Gaussian normal curve/distribution of statistics can be "computed" by many very simple physical processes. One of the simplest is a board with a pin array in a triangular grid (also known as a "Galton box" dating to the 1800s) where pins are offset 1/2 square distance on alternating rows. Dropping balls repeatedly from the same position, the balls randomly displace left or right with probability 0.5. The cumulative distribution recorded at bottom positions yields the Gaussian curve/normal.

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 just because I’m currently designing a logo for our statistics research group and the Galton Box was our first idea (but turns out to be too complex for a logo). $\endgroup$
    – Konrad Rudolph
    Commented Sep 12, 2012 at 14:40
7
$\begingroup$

There is a paper about randomized algorithms in 'primitive' cultures.

Using oracles (e.g. chicken bones, stones) to decide on where to hunt can be seen as a randomized algorithm. One can argue that randomizing the hunting grounds prevents game adaption and overhunting.

Improve this answer
$\endgroup$
1
$\begingroup$

one of Einsteins 1905 "miracle" papers was on brownian motion, a classic physical example of a random walk and yields a formula (ie, basically an algorithm, if the physical process is the "computer") for estimating/calculating particle (molecule) diameter given other known physical constants and the observation/measurement of the (random) particle displacement over time. this paper also served as early theoretical/experimental/foundational evidence for the atomic theory of matter.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ Again as with evolution: though the motion may be random, and may be modelled by a random walk, what algorithm does this represent? While some algorithms use random walks, this does not mean that all random walks represent algorithms (any more than any string of words in English represents prose just because all English prose consists of words in English). $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 15:53
-4
$\begingroup$

another answer in the vein of JS's number theory direction. one of the earliest analog-digital computers constructed is the Lehmer sieve dating to ~1932, predating electronic computers by about a decade. it basically computes remainder of division mod $n_i$ for a finite number of $n_i$ and applies the chinese remainder thm. for larger numbers it computes probabilistic answers to number theory questions including factoring. although the terminology at the time may not have referred to "probabilistic algorithms" it was possibly used in this way in some cases. (in this way it also has some similarity to the Fermat probabilistic prime test.)

the machine also bears some similarity to the Babbage differential engine (~1830s). its not entirely inconceivable that Babbage or Lovelace may have envisioned something similar to probabilistic algorithms. the machine(s) can certainly be used to implement probabilistic algorithms, borrowing modern theory and superimposing it on the past.

[1] Lehmer factoring machine

[2] Babbage engine


Lehmer mod n & factoring machine

Improve this answer
$\endgroup$
13
  • 1
    $\begingroup$ Can you describe the sense in which it computed probabilistic answers for large numbers? A quick search doesn't I can't seem to find any references to that online. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 15, 2012 at 17:23
  • $\begingroup$ my understanding, it was used [among other purposes] to find smaller factors of large test numbers similar to sieve of eratosthenes. if the large number passed, it is "probably not composite" or "possibly prime" or a "prime candidate". unfortunately the internet is not very good with historical references & origins [even wikipedia], books are better. more details at bottom of this page, "types of problems Lehmer was attempting to solve" by Dr mike williams, head curator of the computer history museum of CA $\endgroup$
    – vzn
    Commented Sep 15, 2012 at 17:41
  • 1
    $\begingroup$ the machine(s) can certainly be used to implement probabilistic algorithms — So? As opposed to other machines that can't? $\endgroup$
    – Jeffε
    Commented Sep 15, 2012 at 18:45
  • 2
    $\begingroup$ although the terminology at the time may not have referred to "probabilistic algorithms" it was possibly used in this way in some cases — [citation needed] If you have evidence that "possibly prime" is a formal statement about probability, and not simply a heuristic description, please cite it. Otherwise, please stop speculating. $\endgroup$
    – Jeffε
    Commented Sep 15, 2012 at 18:48
  • $\begingroup$ dont have the full contents of Lehmers papers available (not even sure what all he published), but the pocklington randomized ref is supported by a single line of one of his papers. what is the criteria? it seems all that is required that Lehmer run the machine on some number greater than $n_1 * n_2 * n_3 * n_x$ for the largest $x$ on the machine, and make some kind of reasonable observation about the result, not necessarily written down.... seems plausible to me.... $\endgroup$
    – vzn
    Commented Sep 16, 2012 at 2:43
-6
$\begingroup$

here are some cases of the early and even ancient/prehistory beginnings of concepts related to randomized algorithms.

  • consider the Sieve of Eratosthenes, approx 2 millenia old. somewhat implicit in the algorithm would be the idea of "stopping early" in marking off the prime intervals, before all intervals up to $n/2$ have been marked off. it is clear that the "later" longer intervals are less likely to mark off a given number under consideration. in other words, its a rough visualization of the basic number theory fact that "most composite numbers have small factors" and that testing a bunch of small factors is enough to rule out many composite numbers. this concept would probably be understood by the Greeks.

  • games of chance and gambling are very ancient. from modern theory, games have strong similarities if not direct connections to algorithms. gambling/gaming dice are known to be at least five millenia old.

  • the Greeks & Romans also had the concept of drawing straws where the person drawing the shortest straw lost. similar to dice, its in a sense the simplest possible algorithm to make a single random choice.

  • full disclosure, there is a tinge of bloody history and connection. in other answer MDB mentions evolution. part of evolution is natural selection which also has parallels to human warfare — apparently an intrinsic part of the evolution of human cities/societies. in a sense a war is a crude semirandom algorithm for "something" which sociologists & historians still argue over exact causes. theft/looting? allocating resources? territory? political power? slaves? (etc.) the Romans also had a grisly practice called decimation (the modern word actually derives in etymology from the ancient one!) in which, as punishment for mutiny or cowardice, every 10th soldier selected at random was executed by remaining soldiers. it might seem a forgotten and atavistic practice, but it seems to have some parallel to modern russian roulette, a "modern" randomized quasi-game for suicide.

Improve this answer
$\endgroup$
14
  • 1
    $\begingroup$ That's not what I'm asking about; I'm asking about whether they reasoned about the relative frequency of composite numbers in the way that you describe. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 16:03
  • 1
    $\begingroup$ I'm afraid I'm not interested in vague generalities, and it seems quite obvious that we disagree fundamentally in what an "algorithm" is. I'm interested in more than just "phenomena". Otherwise, we may as well cite all quantum mechanical events after the Big Bang as examples of "randomized algorithms", which makes the whole subject trivial. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 16:17
  • 1
    $\begingroup$ "soft question" doesn't mean a question with infinitely flexible boundaries; "historical overview" is not the same as historical revisionism. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 16:25
  • 2
    $\begingroup$ Your 'hint' to me about evolution, nor your casting me as wasting time on a question I don't like, nor your evasion of my earlier question, were respectful. And in fact, your speculating that the Greeks probably knew about what you're talking about but didn't bother to write about it is exactly one of the things which "historical revisionism" can refer to. (Maybe Archimedes invented decimal notation, but didn't bother to make any record; after all, the Sand Reckoner is quite close to place notation, and the Greeks did use a base-10-like system. But should we take the idea seriously? No.) $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 16:36
  • 1
    $\begingroup$ I agree that it's concievable, and that it isn't even very far-fetched -- aside, of course, from the fact that we don't seem to have any record of the Greeks talking about probability per se. But if there's an actual record of it, you should be able to actually point it out. Otherwise, it's speculation, not history. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 16:48
-7
$\begingroup$

JS mentions number theory. Fermat is credited with the Fermat primality test, a probabilistic algorithm which dates to the 1600s and serves as a precursor to more modern primality tests such as Solovay-Strassen and Miller-Rabin. [it would take a historian specializing in math & number theory to try to pinpoint exactly what Fermat knew about it versus modern knowledge which is much more complete about the structure of its pseudoprimes (false positives) etc.]

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Can you cite Fermat as having used his test as a way of filtering out randomly selected integers as non-primes (as opposed to just an interesting property that primes have)? Or perhaps cite an early author who suggests doing so? $\endgroup$
    – Niel de Beaudrap
    Commented Sep 13, 2012 at 15:35
  • $\begingroup$ as stated the exact details are better left to a professional historian. however note [addendum; should have mentioned this] the simple historical fact that fermat is credited as the founding coinventor of probability theory along with pascal, laying the groundwork in a series of letters in the mid 1600s. $\endgroup$
    – vzn
    Commented Sep 15, 2012 at 5:12
  • 2
    $\begingroup$ it's not really appropriate to propose answers based on what you believe someone else might be able to show. Again, that is speculation. $\endgroup$
    – Niel de Beaudrap
    Commented Sep 15, 2012 at 11:13
  • 3
    $\begingroup$ @vzn: If Fermat had realized that Fermat's Little Theorem was a good primality test, he would have calculated that the 5th Fermat number was not prime. This was not done until Euler factored it more than 60 years after Fermat's death. $\endgroup$
    – Peter Shor
    Commented Sep 15, 2012 at 15:43
  • 2
    $\begingroup$ @vzn: [citation needed] $\endgroup$
    – Jeffε
    Commented Sep 15, 2012 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.