Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!panix!.POSTED.spitfire.i.gajendra.net!not-for-mail
From: cross@spitfire.i.gajendra.net (Dan Cross)
Newsgroups: alt.folklore.computers,comp.os.linux.misc
Subject: Re: The joy of FORTRAN
Followup-To: alt.folklore.computers
Date: Thu, 6 Mar 2025 15:28:14 -0000 (UTC)
Organization: PANIX Public Access Internet and UNIX, NYC
Message-ID: <vqceue$g9g$2@reader1.panix.com>
References: <59CJO.19674$MoU3.15170@fx36.iad> <vqb267$lig$1@reader1.panix.com> <m2sohjF3sciU1@mid.individual.net> <vqceia$g9g$1@reader1.panix.com>
Injection-Date: Thu, 6 Mar 2025 15:28:14 -0000 (UTC)
Injection-Info: reader1.panix.com; posting-host="spitfire.i.gajendra.net:166.84.136.80";
	logging-data="16688"; mail-complaints-to="abuse@panix.com"
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
Originator: cross@spitfire.i.gajendra.net (Dan Cross)

[Note: Followup-To: set to remove comp.os.linux.misc.
The discussion doesn't feel particularly relevant there.]

In article <vqceia$g9g$1@reader1.panix.com>,
Dan Cross <cross@spitfire.i.gajendra.net> wrote:
>In article <m2sohjF3sciU1@mid.individual.net>,
>rbowman  <bowman@montana.com> wrote:
>>On Thu, 6 Mar 2025 02:44:23 -0000 (UTC), Dan Cross wrote:
>>
>>> At best, he reminds me of Herb Schildt.
>>
>>There's a name I haven't heard in a long time, he of 'void main(void)' 
>>fame.
>
>That's the one.  Generations of programmers led astray by that
>guy's books.
>
>>https://www.seebs.net/c/c_tcn4e.html
>>
>>"C: The Complete Reference is a popular programming book, marred only by 
>>the fact that it is largely tripe. Herbert Schildt has a knack for clear, 
>>readable text, describing a language subtly but quite definitely different 
>>from C."
>
>That describes Martin's books to a T, I think.  He writes very
>well, but what he writes, maybe not so much.
>
>Since the topic of their prime number generator program came up,
>I'll append my version here.  Caveat that I'm not at all a Java
>programmer (let us give things to zog for small blessings), I
>think it's better than ether version presented in the Martin and
>Ousterhout debate, though I'm sure it could be further improved.
>
>This version tends closer to Knuth (and Dijkstra, where Knuth
>got it) than either of the two in the debate at
>https://github.com/johnousterhout/aposd-vs-clean-code

Oh gee; a bunch of tab literals snuck in there, which messed up
the formatting when posted.  :-(  With my apologies, here's a
fixed-up version.

	- Dan C.

--->BEGIN Primes.java<---
package literatePrimes;

public class Primes {
    // The algorithm used here comes from Dijkstra via Knuth.  The basic
    // idea is to special case 2, as the first (and only even) prime
    // number, and then step through the odd integers, testing each as
    // a candidate for primality.  A number is prime iff it is not
    // evenly divisible by any smaller prime.
    //
    // To understand how it works, observe that for any composite
    // number j, the smallest prime factor of j will be less than or
    // equal to sqrt(j).  Hence, when testing a candidate for primality,
    // we need not consider whether primes larger than the candidate's
    // square root evenly divide the candidate.  As the number of
    // generated primes grows, the number of primes smaller than the
    // square root grows much more slowly, cutting down on the search
    // space and yielding a considerable performance benefit.
    //
    // When iterating, we are only concerned about the odd primes,
    // so we only need to consider odd candidates starting from 3.  By
    // definition such candidates are not divisible by 2 and so the
    // problem of determining primality is reduced to determining whether
    // a is candidate odd and divisible by some other prime less than or
    // equal to the square root of the candidate.
    //
    // As a further optimization, we avoid division by maintaining an
    // auxilliary array of multiples of primes; that is, a table,
    // `primeMultiples` of multiples of primes p_n.  By maintaining the
    // invariant that, for a given candidate j and prime p_n,
    // primeMultiples[n] < j + 2*p_n, we can quickly test j for
    // divisibility by p_n: if primeMultiples[n] < j, then clearly the
    // invariant holds if we add 2*p_n to primeMultiples[n].  However,
    // if primeMultiples[n] >= j + 2*p_n, then p_n is a factor of j if
    // and only if primeMultiples[n] = j.
    //
    // Note that the factor of 2 in 2*p_n ensures that `primeMultiples[n]`
    // always remains odd, for n > 0: 2*odd is even, and odd+even is odd.
    //
    // To avoid the performance impact of computing square roots, we keep
    // track of the square of the prime that's square root is greater
    // than the square root of the current candidate, and we use this to
    // define an upper bound on multiples table entries that we must
    // use to test a candidate for divisibility.  When we have increased
    // the candidate value such that it becomes equal to this tracked
    // square value, we increase the bound by 1, reset the tracked square
    // to that of the prime now indexed by the new upper bound, and add
    // an entry to the primeMultiples table.  It is safe to refer to the
    // next such prime because we know from "Bertrand's Postulate" that,
    // for a given prime p_n, the next prime p_{n+1} < 2*p_n, and
    // 2*p_n < p_n^2 for p_nn > 2, so such a prime must already have been
    // generated.  Therefore, we simply add the next prime's square to the
    // table as the first multiple of p_{n+1} and set `square` to that
    // same value.
    //
    // Readers who want a deeper explanation may refer to:
    // Knuth, Donald E. 1982. Literate Programming. _The Computer
    // Journal_ 27, 2 (1984), 97-111.
    // http://www.literateprogramming.com/knuthweb.pdf

    private int[] primeMultiples;
    private int[] primes;
    private int nPrimes;
    private int multiplesUpperBound;
    private int nextCandidate;
    private int square;

    // Resets generator state and fills the `primes` array in
    // ascending order.  Note that, as a special case, `reset`
    // returns the first prime number (2), so that we do not
    // have to consider even numbers later.  This simplifies
    // the `next` method, since it only needs to consider odd
    // numbers, and eliminating a conditional probably confers
    // a slight performance advantage.
    private void fill(int[] primes) {
        primes[0] = reset(primes);
        for (int i = 1; i < primes.length; i++) {
            primes[i] = next();
        }
    }

    // Resets the generator state and returns 2: the first, and
    // only even, prime number.
    //
    // The resulting state is set so that the first subsequent
    // invocation of `next` will return the first odd prime, 3.
    // Note that a user must call `reset` before the first
    // invocation of `next`.
    private int reset(int[] primes) {
        nextCandidate = 3;
        this.primes = primes;
        multiplesUpperBound = 1;
        nPrimes = 1;
        primeMultiples = new int[multiplesUpperBound + 1 + primes.length / 2];
        square = 9;
        primeMultiples[multiplesUpperBound] = square;
        return 2;
    }

    // Computes, stores, and returns the next odd prime.
    // The first time this is called, it will return 3,
    // then 5, 7, 11, and so on, up to the defined maximum
    // number of primes.  Attempts to invoke `next` beyond
    // the maximum will generate exceptions, as they try
    // to index beyond the end of the `primes` array.
    //
    // `reset` must be called before the first invocation
    // of `next`.
    private int next() {
        candidates: for (;;) {
            int candidate = nextCandidate;
            nextCandidate += 2;
            if (candidate == square) {
                multiplesUpperBound++;
                square = primes[multiplesUpperBound] * primes[multiplesUpperBound];
                primeMultiples[multiplesUpperBound] = square;
            }
            for (int i = 1; i < multiplesUpperBound; i++) {
                while (primeMultiples[i] < candidate) {
                    primeMultiples[i] += 2*primes[i];
                }
                if (primeMultiples[i] == candidate) {
                    continue candidates;
                }
            }
            primes[nPrimes] = candidate;
            nPrimes++;
            return candidate;
        }
    }

    /**
     * Returns an array of integers holding the first _n_ prime
     * numbers, in ascending order.  Returns null if n < 1.
     *
     * @param n
     *     The number of primes to return.
     */
    public static int[] getFirst(int n) {
        if (n < 1)
            return null;
        var primes = new int[n];
========== REMAINDER OF ARTICLE TRUNCATED ==========