21 Sep
2024
21 Sep
'24
2:22 a.m.
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
23 Sep
23 Sep
2:12 p.m.
New subject: Maximum Array Sizes in 16 bit C
Hi Doug,
int base[N][N+2];
#define binom(n,i) base[n][(i)+1]
Thanks for the interesting prompt. I've been having a think about it
along the lines of sliding the ints in memory.
Have you considered having a single dimension of ints and then accessing
them as if a two-dimensional array, with [0][0] being offset?
$ cat offset.c
#include <stdio.h>
#define N 4 // N×N values
#define L 3 // L columns of 0 to the left
#define U 2 // U columns of 0 upwards
int main()
{
char m[(U + N) * (L + N)] =
"abcdefg"
"hijklmn"
"opq+BCD" // The '+' is a[0][0].
"rstEFGH"
"uvwIJKL"
"xyzMNOP";
char (*a)[L + N] = (char (*)[L + N])&m[U * (L + N) + L];
for (int y = -U; y < N; y++) {
if (!y)
putchar('\n');
for (int x = -L; x < N; x++) {
if (!x)
putchar(' ');
putchar(a[y][x]); // y,x relative to ‘+’
}
putchar('\n');
}
}
$ gcc -Wall -Wextra -Werror offset.c
$ ./a.out
abc defg
hij klmn
opq +BCD
rst EFGH
uvw IJKL
xyz MNOP
$
--
Cheers, Ralph.
24 Sep
24 Sep
6:44 p.m.
New subject: [TUHS] Maximum Array Sizes in 16 bit C
On Fri, Sep 20, 2024 at 8:22 PM Douglas McIlroy
<douglas.mcilroy(a)dartmouth.edu> wrote:
The caveat sent later notwithstanding, I agree that I was overly
fixated on the Fibonacci example in my response and this better
illustrates the motivation for the technique.
Regardless, I feel like we're somewhat speaking at cross-purposes. In
particular, this uses macros to introduce a more pleasant syntax, but
at the language level, the index into the underlying array is always
non-negative and within the array's defined bounds. This is
qualitatively and quantitatively different from using an actual
negative value in the actual indexing operation.
- Dan C.
Moved to Coff, because it's about programming
style, not history.
Heh, I had deliberately removed the list in my response to you, but
it's not too embarrassing to have this redirected back to COFF. :-)
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.
[snip]
24
days inactive
27
days old
2 comments
3 participants
participants (3)
-
Dan Cross -
Douglas McIlroy -
Ralph Corderoy