[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C

[Douglas McIlroy <douglas.mcilroy@dartmouth.edu>]

[-- Attachment #1: Type: text/plain, Size: 1570 bytes --]

Moved to Coff, because it's about programming style, not history.

> Perhaps I'm missing something? Clever arithmetic in the index
> calculation aside, this is semantically different than using an actual
> negative integer to index into an array? Moreover, if the intent is to
> start the sequence with 0, why set `fib(0)` to 1? How is this
> substantially different from the usual way of writing this:

I said the Fibonacci example was silly. Maybe you'll be more convinced by
the binomial-coefficient program below.

The array of interest is fib. base is simply scaffolding and doesn't appear
in the working code. You won't find the ith Fibonacci in base[i]; it's in
fib(i). But fib(-1) exists. What's important is that the C convention of
array indexes beginning at 0 has been circumvented.

I could be accused of subterfuge in depending on the semantics of static
storage to initialize fib(-1) to zero. Subterfuge or not, it's customary C
usage. The binomial-coefficient program relies on "out-of-bounds" zeros
abutting two sides of a triangle.

int base[N][N+2];
#define binom(n,i) base[n][(i)+1]

void fill() {
    binom(0,0) = 1;
    for(n=1; n<N; n++)
for(i=0; i<=n; i++)
            binom(n,i) = binom(n-1,i) + binom(n,i-1);
}

I think the offset algorithm above looks better than the more typical one
below.
The two programs happen to have identical character counts.

int binom[N][N+1];

void fill() {
    for(n=0; n<N; n++) {
        binom[n][0] = 1;
for(i=1; i<n; i++)
            binom[n][i] = binom[n-1][i] + binom[n][i-1];
binom[n][n] = 1;
    }
}

Doug

[-- Attachment #2: Type: text/html, Size: 2376 bytes --]