The article is a story, about how Roger Hui (who with Kenneth E. Iverson developed the programming language J), set about finding the 10 billionth prime: by the Prime Number Theorem it should be about 10^10*log(10^10) which is less than 270 billion, so he split the range into 270 parts, and had each of several machines pick up one part and sieve that billion-number range (to count the number of primes), a million integers at a time. After 20 hours (on 60-70 workstations) he had the counts, so knew the exact million-integer range in which the prime occurred, from which the 10 billionth prime turns out to be either 252,097,800,629 (with 2 as the 0th prime) or 252,097,800,623 (with 2 as the 1st prime).
After doing this, he was able to correct an off-by-one count in a table in a printed book, but the real moral of the story is that this is of course a poor way to compute the nth prime for large n: it has been known since the 1800s how to quickly compute pi(x) (the number of primes not greater than x), and using a published algorithm known at the time would have let him find the ten billionth prime in less than 3 minutes instead of thousands of hours of computer time.
That's the article (though I've focused more on the algorithm while it says “this column is not so much an article about programming as it is about computer logistics”), but these days we can just hit up https://www.wolframalpha.com/input/?i=the+ten+billionth+prim... or https://primes.utm.edu/nthprime/index.php#nth or enter "prime(10000000000)" into https://live.sympy.org/ (this times out for some reason, though primepi(22801763489) takes less than a minute so you could binary-search manually), or enter "nth_prime(10^10)" into Sage (https://www.sagemath.org/) to get the result pretty much instantly (after it starts up, which takes a while), or....
The stated moral of the story (last line of the article): "Brains win again over brawn: a well-designed, mathematically knowledgeable algorithm beats brute force!"
This reminds me of a claim I heard from a numerical analysis colleague: "Algorithms of today running on hardware from the 1950's would beat algorithms of the 1950's running on hardware of today."
It was a thought-provoking comment. It would be less hyperbolic if prefaced with "There exist some problems of practical significance for which.."
The question is, what might be some examples? What are some problems for which the time or space complexity of the best known solution has decreased over the last several decades to the point that the above statement would be true of them?
The Fast Fourier Transform (1965) is one very important algorithm that comes to mind, speeding up Fourier Transforms from O(N^2) to O(N log N). Quicksort (published 1961) might be another example, but since sorts in the 1950s usually ran on tape drives, it's hard to compare.
On the whole, computers of the 1950s were extremely memory-limited, so many modern algorithms aren't entirely relevant. For example, the IBM 7090 (1959) was a large-scale scientific computer and had an address space of 32K words. As for performance, it did 39,500 multiplications per second. A modern supercomputer is trillions of times faster; that makes up for a lot of bad algorithms.
Most modern problems are going to have a hard time fitting in a 1950s computer, regardless of the algorithm. On the whole, I think you'd be better off with 1950s algorithms on a modern computer than vice versa. On the other hand, modern cryptographic algorithms on old hardware would be infinitely better than old algorithms on modern hardware.
I just want to add, because some people might find it interesting, that a version of the fast Fourier transform was already known to Gauss (though not published in his lifetime). More info can be found in the article "Gauss and the history of the fast Fourier transform" by T. Michael.
Merge sorts are typically used when sorting data on magnetic tapes. Polyphase merge was popular. All merge sorts are O(N log(N)). They were ideal for tapes as they read and write data sequentially.
As you point out, the sorting of arrays and sequential access files (tapes) have different algorithms.
the cost of access to a tape record is not negligible and it is the main cost. But for arrays/memory it's almost 0, the weight of memory access.
Niklaus Wirth describes this in the classic book "(Algorithms + Data Structures = Programs)". There is a full chapter comparing the best/normal/worst case for each approach.
Those were "Elegant weapons for a more civilized Age.".
> The question is, what might be some examples? What are some problems for which the time or space complexity of the best known solution has decreased over the last several decades to the point that the above statement would be true of them?
All trigonometric functions.
It is a common source of confusion that none of the modern SIMD instruction sets for x86 contain instructions for sine or cosine. The only instructions for them in the CPU are the FCOS and FSIN ones for the obsolete x87 FP mode. These should never be used, because the software implementations provided by your C library are both faster and more precise.
The reason the CPU instructions are worse than what you can write is that back when they were added to the CPU, the fastest known way of computing full-precision trigonometric functions in hardware was not fast enough for practical use. So instead, the instructions were implemented as approximations. Then, after some improvements in known algorithms, these approximations were improved to be somewhat better and faster. However, this caused compatibility issues because FSIN on a Pentium (or a 486? not sure) does not actually return same results as it does on a 386. Learning from this, the trigonometric functions in x87 are now forever frozen to their old, slow to compute and imprecise approximations.
However, since then a much more accurate and faster way to compute sine and cosine in software has been discovered, and every halfway decent language and math library now uses it.
See e.g. https://www.johndcook.com/blog/2015/12/08/algorithms-vs-moor... — “a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988 […] in 2003 this same model could be solved in roughly 1 minute […] a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algorithms”
To me, that "moral of the story" is a bit backward. He most likely achieved his goal in the most efficient way, i.e. shortest possible time, by throwing hardware at the problem. Going looking for a better algorithm and implementing it might have taken longer and would have been riskier, given that he didn't know if such an algorithm existed.
> Brains win again over brawn: a well-designed, mathematically knowledgeable algorithm beats brute force!
But it didn't, though, did it. Brute force got an answer before brains found the smarter way.
It's great that the well-designed, math knowledgeable algorithm beats brute force, but it takes time to design something well, and to gain the knowledge, if it even exists, which is not a guaranteed prior. In the meantime, your quickly written brute force approach can be making progress.
IMO always try brute force first if there isn't a fairly obvious alternative. Surprisingly often, brute force is enough.
As they say, “A couple of months in the laboratory can frequently save a couple of hours in the library.” Or in this case, a thousand-plus hours of computer time saved a few minutes of looking it up (https://en.wikipedia.org/w/index.php?title=Prime_number&oldi...) or asking a mathematician.
Curiously, all the material out there today can cause a sort of paralysis.
Similar to how we used to argue and banter and have fun about factual disagreements at the bar, while today we can take our phones and look it up (upsides are obvious of course) sucking out part of the fun.
Now if you have some faily simple question today and Google it, you'll find tons of adjacent advice, articles, perhaps even a community dedicated to that sort of thing, libraries etc. Now you either deliberately shut it all out and go ahead with your project, explicitly ignoring all the above, or you start learning it, standing on the shoulders of giants etc.
It can be kind of discouraging to see how much you don't know but is out there, while in the 80s and 90s people had no choice but to rediscover lots of stuff on their own and feel as if they had actually invented the thing, simply due to a lack of Google and Wikipedia.
But overall it's no reason to give up, there is always stuff at the edges to look into, we just have to climb the tree a bit more because the low hanging fruit is gone. Or just pretend we live pre-Google and program away, without checking the answer first. Your boss may not like this latter strategy though.
Obviously Wikipedia didn't exist in 1994; I only gave the link for someone who is actually interested in looking it up today. A paper clearly explaining how to compute π(x) (I was just reading it) had come out in 1985: https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-198...
Where would the average bloke in the street go to find that in 1994? And where would they get that knowledge?
(I mean, these days, the first thing you'd do is Google, the second thing is ask on SO or similar. You'd do this before even thinking about coding something yourself. So the bar to jumping to brute force has shifted somewhat.)
(I'd love to live in a town where the average bloke in the street was interested in fast algorithms for computing π(x), that would be a neat place!)
You'd seek out a mathematician, or visit a university library and ask for the maths librarian. If you didn't know about those resources, you'd go to your public library, and hopefully a librarian would point you in the right direction. All of these search algorithms still work today. :)
As someone who had to write letters for information or ask experts over the phone in the 70s, 80s, and part of the 90s (BBSs in the late 80s to 90s for me), you'd have to have good luck finding the person with the bit of specialized knowledge you sought, and hope they had it. A nostalgic note: Our sixth grade teacher made us pick four big companies and write letters to them asking for information about them and their products. I remember being ecstatic getting letters, pamphlets and even items from them. Toothpaste from Colgate. The pamphlets were so much more informative than the marketing material today. They were pitched to a smarter audience possibly purchasing agents, etc. hTe fastest response was almost three weeks. The rest came a month and later.
I was just a fledgling in the late days of the BBSs, so I didn't spend too much time there!
Fair points about the trouble of finding the right expert. I also wasn't on any of the math-related Usenet groups back in the day (I was more of a comp.lang.* lurker), but I wonder if there was a good mingling of experts and novices in those groups. These days, you can (e.g.) visit /r/math or /r/mathematics on Reddit, and you'll occasionally see interesting novice questions being picked up by PhDs across various math fields -- sometimes with surprisingly deep responses. It's rare that a novice question merits such attention, but the fact that it can can happen -- that such a forum exists -- is delightful.
You've also reminded me of something, vaguely -- one of the major US universities used to have a phone number that you could call and ask them about nearly anything. They would research the question and get back to you with an answer if they could. I wish I could remember which university it was, maybe the number still exists?
That seems highly questionable. Given the complexity of his brute force algorithm, it was probably significantly more complex, and required more development time than the more elegant solution. The only reason the brute force got its answer first, was because it was the first thing he tried. That’s hardly an advantage of the approach.
Hui's immediate response was, "Do you start counting from 0 or 1?"
Counting numbers are defined as the integers starting from one. I'm probably lacking a bit of rigour there. err ... Define 1 = S or is that S = 1 or S is a thing or 1 is a thing or something and then put more S (s) in until you run out of S (essessses) then you have reached infinity. If it's not a really big infinity then keep adding S (sssssss) or remove a few and add some more. You'll get there eventually - lots of Ss or infinity, or not, who knows? If you run out of S then try adding some T. Everything is better with T.
He would have better off with: "Do you prefer green trees or brown trees?" That would have simply sounded silly, rather than +1 insightful.
Because “not prime” isn’t the same as “composite” (1 is neither prime nor composite in the modern view) it isn’t that simple.
Some ancient mathematicians such as Aristotle and Plato solved that problem by saying 2 is the first number. Others stated 3 to be the first prime
That isn’t holdable once you accept 0 and negative integers to be numbers.
https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.h... states that, for example, Goldbach thought 1 to be prime at some time (in a letter to Euler), as did Legendre, Lebesgue (sometimes), Cayley, Kronecker, Hardy, Lehmer (as the article discussed also says), and the aliens in Carl Sagan’s “Contact”.
It also gives fairly recent publications that state 1 is a prime.
In the end, whether we consider 1 to be prime is more a choice (just as mathematicians commonly chose to pick 0⁰ = 1) than that it necessarily the case. It just is the better choice (https://en.wikipedia.org/wiki/Prime_number#Primality_of_one)
Well, technically, rigorously defined counting starts at 0, not at 1.
You can define counting as defining an injective function from your set to the natural numbers, and then you need to have some element going to 0 - as per the definition of a countable set[0].
Also, both the cardinal[1] and the ordinal[2] numbers are defined as starting from 0, just like the cardinal numbers.
"Countable" is not the same as the "countable numbers" nor is it the same as the process of "counting".
The process of counting might be defined as what starts to happen when you stick up one finger and say something to emphasise what that finger means. That something will not be zero. Ever.
When you count your sheep into your pen, you will of course start: "Yan, tan, tither, toe" Trust me that yan does not mean zero.
Also note that if you search those terms, you will get a valid result and conclude I've misspelt some of those Cumbric words. I haven't, according to living relos of mine. Speling is a bit odd anyway when you go back a few centuries and I'll wager that tither is more likely than tethera because it is very slightly more easy to say. Tethera is three syllables but tether is two, bordering on one. However tethera could be pronounced "tethra", ie drop the extra e when spoken.
The counting numbers are fairly rigorously defined and are the numbers we use when we don't have access to more than the usual four dimensions, imaginary thingies, quaternions, etc etc.
> You can define counting as defining an injective function from your set to the natural numbers, and then you need to have some element going to 0 - as per the definition of a countable set[0].
You can define counting as an injection into other (equivalent) sets just as rigorously.
Context matters. Hui likely used APL to code up the problem and APL let's one choose between 0- and 1-indexing. Reading APL papers from around the time, it looks common to have explicitly declared your indexing convention up front, so my suspicion is that Hui essentially was responding "I'll code up a bit of APL and get you the answer. What are your conventions?"
As John Conway said (see sibling comment, or e.g., [1]):
> Every nonzero rational number has a unique factorization into powers of distinct primes.
As you note, (-1)^2 = 1. But if you read carefully, you'll see that the factorization of -100/3 is uniquely:
-1 * 4 * 1/3 * 5 * 1 ...
whereas the factorization of 100/3 is uniquely:
1 * 4 * 1/3 * 5 * 1 ...
Where it's true that the representation using primes with exponents is not unique, it is true that the representation using powers of primes is unique. That is, your issue regarding (-1)^2 is that there are infinitely many representations of 1 or -1 having the form (-1)^x, but if you evaluate (-1)^x (x being integral, of course) you'll only get one of two numbers.
And yes, changing the definition of "prime" does change some special cases -- it removes some (such as extending unique factorization to negative rationals), and adds others (wherever primes are assumed positive).
Lots of modern mathematical texts define counting from 0, and it might be brought up because of the engineering context of indexing convention in a language that lets you flexibly define that.
What defines counting is an initial element, often called 0, and a successor function which constructs the next number. The question is why you're doing such a construction, and if you want an identity element for natural addition.
Brains may win over brawn, but the problem is that brains don't generalize. It requires bespoke creative mathematical work. In that sense, the brute force method while slower has an advantage in that it could theoretically be derived more easily (from another algorithm for example or by a general intelligence system). Direct analytical results are always faster and more accurate than numerical results, but numerical results are more reliably attained.
Turns out, we end up evolving said general intelligence system into doing bespoke creative work, and it slows down the compilation time by around as much as it takes a human to think up the analytical solution =P
Then we end up with a tunable knob to speed up compilation. But then this more or less reduces to coding up either method depending on the situation, aka what we began with!
> Even a Boolean vector taking just 1 bit per element would have to be more than 3e10 bytes long, so it was clear that the problem had to be partitioned.
That's 28GB. That's just astronomical in those days' terms, even stored on hard drives it would have taken a massive array of commodity HDDs. I love these little reminders of how far we've come.
There is a very beautiful way to do it using much less memory.
You need O(sqrt(n)/log(n)) memory, not O(n), if you keep track of the list of primes found so far, and a fixed-size interval over which you sieve: [1, k], [k+1, 2k], [2k+1, 3k], ...
Now, for the beautiful part, if you skip multiples of 2, 3 and 5, and work in blocks of 2 * 3 * 5 = 30 numbers, you only need to sieve {1, 7, 11, 13, 17, 19, 23, 29} + i*30. 8 booleans, that happen to fit in 1 byte. So 1 byte = 1 interval of 30 numbers.
Next, you can unroll the sieving loop, but no compiler will do this for you, you have to do it by hand. This allows you to sieve up to 8 multiples per iteration.
This solution is beautiful. Thank you for sharing. No longer will I need to dynamically allocate huge arrays when solving prime number-related problems on Project Euler.
There were 0.5 to 2gb drives around then as were commercial offerings for arrays that could easily store 28. The growth has been huge, of course, but the mid 90s weren't entirely the stone age either.
Right but it's hardly astronomical and something that easily fit on a single array. My 1996 (work) workstation had about 9gb in regular drives hooked up to it. A lot, but nothing astronomical. DVDs were just around the corner, for another point of context.
Hah, I have pendaticornered myself with the astronomical. I guess a better way of putting it is - 1 gig drives came out in 91, the 2 gig barracuda in 92. By 94, typical personal device storage would be a bigger fraction of 30 gigs than, say, current typical personal device storage as a fraction of a current backblaze 4u pod. A backblaze pod is pretty mundane.
I think an average consumer HDD around that time was probably 100-200MB, no? I don't remember what the cheap desktop I bought in '94 had, but it was definitely not over a gig. I remember I bought a 6GB HDD that was already pretty cheap in '99, thinking "wow, disks are just massive now".
Concrete proof there is no largest prime number: color the number line starting at zero, blackening every other number, every third, every fifth and so on up to every 'theoretical-biggest-prime'. Calculate PIPrime, the product of all of the prime numbers. All of these blackening sequences land on that number (its a multiple of all of them).
Note that the blackened-integer sequence is symmetrical from zero to PIPrime - same forward and backward. In fact it starts to repeat itself from there.
Now note that '1' was not blackened. So of course, the number to the right or left of PIPrime is not blackened. So that number must also be prime (not a multiple of any known prime) or there is some other prime number, larger than the known largest, that would have landed there. In either case, there is a larger prime than you knew.
The article is a story, about how Roger Hui (who with Kenneth E. Iverson developed the programming language J), set about finding the 10 billionth prime: by the Prime Number Theorem it should be about 10^10*log(10^10) which is less than 270 billion, so he split the range into 270 parts, and had each of several machines pick up one part and sieve that billion-number range (to count the number of primes), a million integers at a time. After 20 hours (on 60-70 workstations) he had the counts, so knew the exact million-integer range in which the prime occurred, from which the 10 billionth prime turns out to be either 252,097,800,629 (with 2 as the 0th prime) or 252,097,800,623 (with 2 as the 1st prime).
After doing this, he was able to correct an off-by-one count in a table in a printed book, but the real moral of the story is that this is of course a poor way to compute the nth prime for large n: it has been known since the 1800s how to quickly compute pi(x) (the number of primes not greater than x), and using a published algorithm known at the time would have let him find the ten billionth prime in less than 3 minutes instead of thousands of hours of computer time.
That's the article (though I've focused more on the algorithm while it says “this column is not so much an article about programming as it is about computer logistics”), but these days we can just hit up https://www.wolframalpha.com/input/?i=the+ten+billionth+prim... or https://primes.utm.edu/nthprime/index.php#nth or enter "prime(10000000000)" into https://live.sympy.org/ (this times out for some reason, though primepi(22801763489) takes less than a minute so you could binary-search manually), or enter "nth_prime(10^10)" into Sage (https://www.sagemath.org/) to get the result pretty much instantly (after it starts up, which takes a while), or....