4 ms·

Some people feel at home with APL (A Programming Language) or its descendants. It was first developed by Ken Iverson as a notation to be used on paper for commu

Some people feel at home with APL (A Programming Language) or its descendants. It was first developed by Ken Iverson as a notation to be used on paper for communicating procedures and algorithms. It was the subject of a book published in 1962, then became a programming language running on IBM mainframes in 1966. The following line of code produces all the prime numbers below the value R. (~T∊T∘.×T)/T←1↓⍳R More history and a full explanation of this code can be found at https://www.computerhistory.org/atchm/the-apl-programming-language-source-code/ https://www.computerhistory.org/atchm/the-apl-programming-la...

kragen 7y ago
A fairly precise raw Python translation for the interested: T = range(1, R)[1:] # T←1↓ιR u = [[t*u for u in T] for t in T] # T∘.×T v = [t for ei, t in zip([any(t in ui for ui in u) for t in T], T) if not ei] # (~T∈u)/T As the standard poem on the subject by Dave Touretzky and Don Libes says: I wrote some hacks in APL, each on a single line. They're mutually recursive, and run in n-squared time! In this case, of course, it runs in R-cubed time, not n-squared time. There's a perhaps more common, but slightly longer, APL one-liner for finding primes that does run in O(R²) time instead; from https://aplwiki.com/SieveOfEratosthenes https://aplwiki.com/SieveOfEratosthenes †: (2=+⌿0=(⍳X)∘.|⍳X)/⍳X Or, eliminating the inessential variations from the above version: (2=+⌿0=T∘.|T)/T←⍳R If you want APL and are stuck with Python, you can probably get most of the APL you want in Numpy. A slightly looser translation of the first algorithm into Numpy: import numpy T = numpy.arange(2, R) print T[~numpy.equal.outer(T, numpy.multiply.outer(T, T) ).any(axis=1).any(axis=1)] Recent versions of Numpy have numpy.isin, which works like APL ∈, which would save you the .outer.any.any nonsense. A much more compelling demonstration of APL is, in my mind, the interactive development process leading up the the one-liner Game of Life in this livecoding video: https://www.youtube.com/watch?v=a9xAKttWgP4 https://www.youtube.com/watch?v=a9xAKttWgP4 † This is not the Sieve of Eratosthenes, despite the article title; the Sieve is an immensely more efficient algorithm than trial division, producing the same results in near-linear time.
- kragen 7y ago
  I realize now that the first line should say range(1, R+1)[1:]. We regret the error.

kragen 7y ago

A fairly precise raw Python translation for the interested: T = range(1, R)[1:] # T←1↓ιR u = [[t*u for u in T] for t in T] # T∘.×T v = [t for ei, t in zip([any(t in ui for ui in u) for t in T], T) if not ei] # (~T∈u)/T As the standard poem on the subject by Dave Touretzky and Don Libes says: I wrote some hacks in APL, each on a single line. They're mutually recursive, and run in n-squared time! In this case, of course, it runs in R-cubed time, not n-squared time. There's a perhaps more common, but slightly longer, APL one-liner for finding primes that does run in O(R²) time instead; from https://aplwiki.com/SieveOfEratosthenes https://aplwiki.com/SieveOfEratosthenes †: (2=+⌿0=(⍳X)∘.|⍳X)/⍳X Or, eliminating the inessential variations from the above version: (2=+⌿0=T∘.|T)/T←⍳R If you want APL and are stuck with Python, you can probably get most of the APL you want in Numpy. A slightly looser translation of the first algorithm into Numpy: import numpy T = numpy.arange(2, R) print T[~numpy.equal.outer(T, numpy.multiply.outer(T, T) ).any(axis=1).any(axis=1)] Recent versions of Numpy have numpy.isin, which works like APL ∈, which would save you the .outer.any.any nonsense. A much more compelling demonstration of APL is, in my mind, the interactive development process leading up the the one-liner Game of Life in this livecoding video: https://www.youtube.com/watch?v=a9xAKttWgP4 https://www.youtube.com/watch?v=a9xAKttWgP4 † This is not the Sieve of Eratosthenes, despite the article title; the Sieve is an immensely more efficient algorithm than trial division, producing the same results in near-linear time.

kragen 7y ago
I realize now that the first line should say range(1, R+1)[1:]. We regret the error.