From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.5 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI autolearn=ham autolearn_force=no version=3.4.4 Received: from minnie.tuhs.org (minnie.tuhs.org [50.116.15.146]) by inbox.vuxu.org (Postfix) with ESMTP id 81D7426E77 for ; Sat, 21 Sep 2024 02:22:27 +0200 (CEST) Received: from minnie.tuhs.org (localhost [IPv6:::1]) by minnie.tuhs.org (Postfix) with ESMTP id 219CB4334D; Sat, 21 Sep 2024 10:22:25 +1000 (AEST) Received: from mail-vs1-xe2d.google.com (mail-vs1-xe2d.google.com [IPv6:2607:f8b0:4864:20::e2d]) by minnie.tuhs.org (Postfix) with ESMTPS id 856724330C for ; Sat, 21 Sep 2024 10:22:21 +1000 (AEST) Received: by mail-vs1-xe2d.google.com with SMTP id ada2fe7eead31-49bd2b37fe9so852200137.1 for ; Fri, 20 Sep 2024 17:22:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=dartmouth.edu; s=google1; t=1726878140; x=1727482940; darn=tuhs.org; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=bk6jwB+FY9W2N555XkChAo3ZQgLWtbD9vbUzgLHvSG4=; b=ZPmJOvq1iSA+dTs7G6B58ksIbiASfcrVlGLafoiAdfm2fU8E1SoNyRZQl/SQ1ffze1 C9vELHpjT02Fm5bgFyReKRXneUZAWDYFo8dyI94tsKTmnSFJJWbFkhR9UWQaAeGOqmeB dJP+a2moUxbTmVi0WWwUS6/I12mSXDdLzvzXJw3gUdQ0CTxDub/6T77cWqifn3xl2FeB iKlJrmZ8gKCaRjw3BlIqspKwYeWxsy7BMHUacYaNUOuDTJsXvX/8bBk5aZFqyjW0v+Ob 4SQ2jlRZKcOTFbYo8snpe+5Orw6g+CrZOjn6u7NYoeO14/O29nWptP8/ndg3zW3pvFA+ qPDw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1726878140; x=1727482940; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=bk6jwB+FY9W2N555XkChAo3ZQgLWtbD9vbUzgLHvSG4=; b=mCFiSp0YLDGTAuDTNasUUo+n4MOnJWhropb6StRRAYV6nq15XkY4obIGEAy+OhHIDt yc6y0bnqDIq11PzaIRbdQRe5LxHVAQGPKMk6RD36xi32stAx/5iAniyqkWXFgolEoe0/ 1rZM9ppgdyx3jcpWTIHSafykvgy0I9at3Gqpwx+qzP8mrU23dBTG9EjPddkjTY87tq4E u3MAVNqNjhLo1ssf+pvJfNJ1wTmgbuvE94rOLwcre7w2ubp+0qdzL7Klr5nkm+2iWXwX SBe2NGrdNXWOxUaK6ahl6Sx168HsySKE18h5Kk1T3M67MQYk5Wru1zMOJY9PwD0qrPqp cXEw== X-Gm-Message-State: AOJu0YyB66l8DgfIZIwhPCOi3GAkzA8DB2bnGIInpBrmMwqOPia6NH1P DEHW6+5GPqE8wWTQza5yF1K+oKGUWGkNfOBBLCfWK8NYk3E+3ReZJwajBB0Simb5G7ZrM1/SQAf 0TgUEIFM2P5nASKlapBArwhNE4XgYU/K+tWxTPdxCKScCiJRL6n4= X-Google-Smtp-Source: AGHT+IFr7NlM1XwRGKrWGP7YzDCb15dd0Vt/Be3AeGqKvNp5GlqJt6lUhATQcNa9Q9kEClU5fVnvXUK4tQmErpSSS4A= X-Received: by 2002:a05:6102:6c8:b0:48f:cb62:231a with SMTP id ada2fe7eead31-49fc96526dfmr3254482137.23.1726878140556; Fri, 20 Sep 2024 17:22:20 -0700 (PDT) MIME-Version: 1.0 From: Douglas McIlroy Date: Fri, 20 Sep 2024 20:22:05 -0400 Message-ID: To: COFF , Dan Cross Content-Type: multipart/alternative; boundary="000000000000237ffa06229626e1" Message-ID-Hash: N23MENH2TTQNAJB2Q6MHJ5KHE3ESIBJF X-Message-ID-Hash: N23MENH2TTQNAJB2Q6MHJ5KHE3ESIBJF X-MailFrom: douglas.mcilroy@dartmouth.edu X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header X-Mailman-Version: 3.3.6b1 Precedence: list Subject: [COFF] Re: [TUHS] Maximum Array Sizes in 16 bit C List-Id: Computer Old Farts Forum Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --000000000000237ffa06229626e1 Content-Type: text/plain; charset="UTF-8" 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
Moved to Coff, because it's abou= t programming style, not history.

> Perhaps I'm missing something? Clever arithmetic in the i= ndex
> calculation aside, this is semantically different than using a= n 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. Mayb= e you'll be more convinced by the binomial-coefficient program below.= =C2=A0

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

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

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

void fill() {
=C2=A0 =C2=A0 binom(0,0) =3D 1;
=C2=A0 =C2=A0 for(n=3D1; n<N= ; n++)
for(i=3D0; i<=3Dn; i++)
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 binom(n,i) =3D 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 t= o have identical character counts.

int binom[N][N+= 1];

void fill() {
=C2=A0 =C2=A0 for(n=3D= 0; n<N; n++) {
=C2=A0 =C2=A0 =C2=A0 =C2=A0 binom[n][0] =3D 1;<= /div>
for(i=3D1; i<n; i++)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 binom[n][i] =3D binom[n-1][i] + binom[n][i-1];
= = binom[n][n] =3D 1;
=C2=A0 =C2=A0 }
}
<= br>
Doug
--000000000000237ffa06229626e1--