*[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C@ 2024-09-21 0:22 Douglas McIlroy2024-09-23 12:12 ` [COFF] " Ralph Corderoy 2024-09-24 16:44 ` [COFF] Re: [TUHS] " Dan Cross 0 siblings, 2 replies; 5+ messages in thread From: Douglas McIlroy @ 2024-09-21 0:22 UTC (permalink / raw) To: COFF, Dan Cross [-- 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 --] ^ permalink raw reply [flat|nested] 5+ messages in thread

*[COFF] Re: Maximum Array Sizes in 16 bit C2024-09-21 0:22 [COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C Douglas McIlroy@ 2024-09-23 12:12 ` Ralph Corderoy2024-09-24 16:44 ` [COFF] Re: [TUHS] " Dan Cross 1 sibling, 0 replies; 5+ messages in thread From: Ralph Corderoy @ 2024-09-23 12:12 UTC (permalink / raw) To: Douglas McIlroy;+Cc:COFF 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. ^ permalink raw reply [flat|nested] 5+ messages in thread

*2024-09-21 0:22 [COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C Douglas McIlroy 2024-09-23 12:12 ` [COFF] " Ralph Corderoy[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C@ 2024-09-24 16:44 ` Dan Cross1 sibling, 0 replies; 5+ messages in thread From: Dan Cross @ 2024-09-24 16:44 UTC (permalink / raw) To: Douglas McIlroy;+Cc:COFF On Fri, Sep 20, 2024 at 8:22 PM Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote: > 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] 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. ^ permalink raw reply [flat|nested] 5+ messages in thread

*[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C@ 2024-09-23 20:59 Douglas McIlroy0 siblings, 0 replies; 5+ messages in thread From: Douglas McIlroy @ 2024-09-23 20:59 UTC (permalink / raw) To: COFF [-- Attachment #1: Type: text/plain, Size: 494 bytes --] A summary of a couple of longer posts. Ralph Corderoy and I used different C syntax than to access an MxN array A, whose subscripts begin at M0 and N0 in the respective dimensions. Here's a somewhat simplified version of both. In our examples, M0 and M0 were negative. Mine: int base[M][N]; #define A(i,j) base[i-M0][j-N0] Ralph's int base[M][N]; int (*A)[N] = (int(*)[N])&base[-M0][-N0]; In my scheme element references must be written A(i,j). Ralph retains C array syntax, A[i][j]. Doug [-- Attachment #2: Type: text/html, Size: 755 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread

*[COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C@ 2024-09-21 14:37 Douglas McIlroy0 siblings, 0 replies; 5+ messages in thread From: Douglas McIlroy @ 2024-09-21 14:37 UTC (permalink / raw) To: COFF, Dan Cross [-- Attachment #1: Type: text/plain, Size: 366 bytes --] Mea culpa. I thought I could offer a simple example, but my binomial-coefficient program is wrong, and loses its force when corrected. For a convincing example, see the program in https://digitalcommons.dartmouth.edu/cs_tr/385/ Unfortunately you have to read a couple of pages of explanation to see what this program is up to. It's a fun problem, though. Doug [-- Attachment #2: Type: text/html, Size: 578 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread

end of thread, other threads:[~2024-09-24 16:45 UTC | newest]Thread overview:5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2024-09-21 0:22 [COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C Douglas McIlroy 2024-09-23 12:12 ` [COFF] " Ralph Corderoy 2024-09-24 16:44 ` [COFF] Re: [TUHS] " Dan Cross 2024-09-21 14:37 Douglas McIlroy 2024-09-23 20:59 Douglas McIlroy

This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).