Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: melahi_ahmed@yahoo.fr (Ahmed)
Newsgroups: comp.lang.forth
Subject: Re: exercise in double number arithmetic
Date: Mon, 8 Jul 2024 14:00:53 +0000
Organization: novaBBS
Message-ID: <015f98d38af241fcd0aeb55df73bfb57@www.novabbs.com>
References: <v6c8v0$3usoe$1@dont-email.me> <nnd$190e18f3$02eb8e44@e16a1d647fb55d93> <8da4b31b5cb3f13d9c296278d6821e6f@www.novabbs.com> <db3806e0ad371735050140c7a6b35f24@www.novabbs.com> <06259926ff879b77247d41e9625b3364@www.novabbs.com> <1c9d7fdc4b5b9bc4cb38e1993a68fb15@www.novabbs.com> <686af9fbeca7b6bb6d657b90a1d24d1c@www.novabbs.com> <v6fdrf$ie3q$1@dont-email.me> <64d4486dc46bc7b93115c7ad489e1f4d@www.novabbs.com> <v6glrj$s90n$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: i2pn2.org;
	logging-data="2579951"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="hogn68ACS2mVV0PcPkBzD/3kIXL71Lu5zlxJ/QczJJE";
User-Agent: Rocksolid Light
X-Rslight-Site: $2y$10$u21/11TG7rLlem5qumTmuOycIbyfbT3f99IhDWdBa0QtafuNXQm6C
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Rslight-Posting-User: cdd77cd46f5cefdf617b921703a970831cf47f35
Bytes: 3410
Lines: 73

On Mon, 8 Jul 2024 12:25:23 +0000, Krishna Myneni wrote:
....
> All of the different solutions have utility, particularly the Pascal
> triangle method when a number of binomial coefficients must be
> available. I recall that modern Fortran has ways to specify
> non-rectangular arrays. We should be able to define a triangle array
> structure in Forth as well, to reduce the storage required for n = 1 to
> nmax array of coefficients.
>
> --
> Krishna

Here is a version that uses Pascal's triangle saved in a table (array)
with minimal size.
The table has just 8778 double cells (132*133/2 = 8778 double cells) and
not (132*132 double cells).
The table is structured as below:
     the number of double cell:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 ...
The content of the double cell:  1 1 1 1 2 1 1 3 3 1  1  4  6  4  1  1 
5 10 10  5  1 ...
                             n:  0 1 1 2 2 2 3 3 3 3  4  4  4  4  4  5 
5  5  5  5  5
                             p:  0 0 1 0 1 2 0 1 2 3  0  1  2  3  4  0 
1  2  3  4  5 ...

The code begins here.

132 value M
M dup 1+ * 2/ value table_size (132*133/2 = 8778 double cells)

create binomial_coeffs table_size 2* cells allot

: th ( n p -- r) swap dup 1+ * 2/ + ;

: bc_th th 2* cells binomial_coeffs + ;
: bc_th! bc_th 2! ;
: bc_th@ bc_th 2@ ;

: coeffs.init
    binomial_coeffs table_size 2* cells erase
    M 0 do 1. i 0 bc_th! loop ;

: coeffs.calc
     coeffs.init
     M 1 do
        M 1 do
           j 1- i 1- bc_th@
           j 1- i  < if 0. else j 1- i bc_th@ then d+
           j    i    bc_th!
        loop
      loop
;


: get_binomial_coeff ( n p -- c) bc_th@ ;
: binomial bc_th@ ;

coeffs.calc

Here, the code ends.

Some calculations:

table_size . 8778  ok

42 21 binomial d. 538257874440  ok
68 34 binomial d. 28453041475240576740  ok
130 65 binomial d. 95067625827960698145584333020095113100  ok
131 65 binomial d. -151587533838167986841078431285821850606  ok
131 65 binomial ud. 188694833082770476622296176145946360850  ok (notice
ud. here)

Ahmed