Why using double arithmetic when we can use simply Pascal triangle?
...
Here is a version with double numbers
and Pascal triangle
create table 50 50 2* * cells allot
table 50 50 2* * cells erase
: table.init 50 0 do 1. table i 50 * cells + 2! loop ;
table.init
: table.calc 49 1 do 50 1 do table j 1 - 50 * i 1 - 2* + cells + 2@
table j 1 - 50 * i 2* + cells + 2@ d+
table j 50 * i 2* + cells + 2!
loop loop ;
table.calc
table 42 50 * 21 2* + cells + 2@ d.
It gives 538257874440. (the same result)
On 7/6/24 16:59, Ahmed wrote:...
: solution ( -- d)
1 s>d 43 22 do i 1 m*/ loop d>f
21 dup s>d rot 2 do I 1 m*/ loop d>f
f/ fround f>d ;
Krishna
I've been working on extending the kForth-64 User's Manual and, in >particular, illustrating double length arithmetic, which, being one of
the strengths of Forth, often does not get enough exposure. Here's an >exercise which you can do using only standard Forth words.
How many different ways can you choose 42 distinct objects, 21 at a
time? This is "n choose k" or the binomial coefficent.
Please show your code.
--
Krishna Myneni
On Sat, 6 Jul 2024 23:50:28 (UTC), Krishna Myneni wrote:
On 7/6/24 16:59, Ahmed wrote:...
: solution ( -- d)...
1 s>d 43 22 do i 1 m*/ loop d>f
21 dup s>d rot 2 do I 1 m*/ loop d>f
f/ fround f>d ;
Krishna
You have not to use fround. (42!/21!) is an integer and is multiple of
21!.
in other words 42! is multiple of (21!)^2.
On 7/7/24 00:48, Ahmed wrote:
On Sat, 6 Jul 2024 23:50:28 (UTC), Krishna Myneni wrote:
On 7/6/24 16:59, Ahmed wrote:...
: solution ( -- d)...
1 s>d 43 22 do i 1 m*/ loop d>f
21 dup s>d rot 2 do I 1 m*/ loop d>f
f/ fround f>d ;
Krishna
You have not to use fround. (42!/21!) is an integer and is multiple of
21!.
in other words 42! is multiple of (21!)^2.
The FROUND is necessary because 42!/21! is too large of an integer to be exactly represented by double-precision fp (IEEE format) and F>D is a truncating operation, not rounding.
The whole D>F and floating point operations can be dispensed with if we
have D/MOD -- a double length version /MOD.
--
Krishna
[..]How many different ways can you choose 42 distinct objects, 21 at a
time? This is "n choose k" or the binomial coefficent.
Please show your code.
2 \ For N M return "N OVER M " (N/M)[..]
3 : CHS >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
On Sun, 7 Jul 2024 11:24:35 (UTC), albert@spenarnc.xs4all.nl wrote:
[..]How many different ways can you choose 42 distinct objects, 21 at a
time? This is "n choose k" or the binomial coefficent.
Please show your code.
2 \ For N M return "N OVER M " (N/M)[..]
3 : CHS >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
Really great!
FORTH> 42 21 CHS . 538257874440 ok
FORTH> 66 33 CHS . 7219428434016265740 ok
FORTH> 68 34 CHS . ( ... )
-marcel
On 7/7/24 00:48, Ahmed wrote:
On Sat, 6 Jul 2024 23:50:28 (UTC), Krishna Myneni wrote:
On 7/6/24 16:59, Ahmed wrote:...
: solution ( -- d)...
1 s>d 43 22 do i 1 m*/ loop d>f
21 dup s>d rot 2 do I 1 m*/ loop d>f
f/ fround f>d ;
Krishna
You have not to use fround. (42!/21!) is an integer and is multiple of
21!.
in other words 42! is multiple of (21!)^2.
The FROUND is necessary because 42!/21! is too large of an integer to be exactly represented by double-precision fp (IEEE format) and F>D is a truncating operation, not rounding.
The whole D>F and floating point operations can be dispensed with if we
have D/MOD -- a double length version /MOD.
--
Krishna
On Sun, 7 Jul 2024 15:41:54 (UTC), mhx wrote:[..]
[..]2 \ For N M return "N OVER M " (N/M)
3 : CHS >R R@ - 1 R> 1+ 1 ?DO OVER I + I */ LOOP NIP ;
table.calc
table 68 N * 34 + 2* cells + 2@ d. 28453041475240576740 ok
Wolfram alpha gives C(68,43) = 28453041475240576740
minforth version gives: 68 34 bcoef 28453041475240574976 ok (it is different)
minforth version gives: 68 34 bcoef 28453041475240574976 ok (it is different)
FORTH> 131 dup 2/ chs cr ud.
188694833082770476622296176145946360850
( correct cf. WolframAlpha, but 132 66 CHS is incorrect )
-marcel
OK, let's extend it a little.
: CHS ( M N -- M!/{M-N}!/N! )
DUP local N
- local M-N
1. N 1+ 1 DO M-N I + I M*/ LOOP ;
130 65 binom d...
95067625827960698145584333020095113100 ok
Krishna
And it works for n=131, k=65
131 65 binom ud. 188694833082770476622296176145946360850 ok
Good work. This thread was fruitful.
On 07/07/2024 14:17, Krishna Myneni wrote:...
The whole D>F and floating point operations can be dispensed with if
we have D/MOD -- a double length version /MOD.
--
Krishna
There is a +D/MOD in this link
http://www3.cs.stonybrook.edu/~algorith/implement/random-number/distrib/r250.seq
On Mon, 8 Jul 2024 1:02:37 (UTC), Krishna Myneni wrote:
..
130 65 binom d...
95067625827960698145584333020095113100 ok
Krishna
And it works for n=131, k=65
131 65 binom ud. 188694833082770476622296176145946360850 ok (correct,
see WolframAlpha)
But for n>=132 it gives uncorrect results.
Good work. This thread was fruitful.
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
On 7/7/24 09:33, Gerry Jackson wrote:
On 07/07/2024 14:17, Krishna Myneni wrote:...
The whole D>F and floating point operations can be dispensed with if
we have D/MOD -- a double length version /MOD.
--
Krishna
There is a +D/MOD in this link
http://www3.cs.stonybrook.edu/~algorith/implement/random-number/distrib/r250.seq
Thanks, Gerry. It looks like D/MOD is not essential to computing the
binomial coefficients with double length numbers. We can use M*/ for
single computations, or simply D+ to build up a table of coefficients.
But, it's good to have a reference for D/MOD.
I remember that I wanted to update the FSL R250 code to generate 64-bit random numbers, but I never got around to it. There is also a
permutations and combinations module in FSL which may benefit from what
has been demonstrated in this thread.
--
Krishna
On 10/07/2024 5:51 pm, Gerry Jackson wrote:
[...] I found I had another definition for D/MOD from Forth Dimensions Vol 14 Issue 6, p 27 "Math - Who Needs It"
https://www.forth.org/fd/FD-V14N6.pdf
I've no idea how good it is
Here's the source file (32MATH.SEQ) for those interested:
https://pastebin.com/mfU8FZ1x
On 10/07/2024 6:41 pm, dxf wrote:
On 10/07/2024 5:51 pm, Gerry Jackson wrote:
[...] I found I had another definition for D/MOD from Forth Dimensions Vol 14 Issue 6, p 27 "Math - Who Needs It"
https://www.forth.org/fd/FD-V14N6.pdf
I've no idea how good it is
Here's the source file (32MATH.SEQ) for those interested:
https://pastebin.com/mfU8FZ1x
Here's one I had lying around. Not sure if I used it so may require checking first! The 2variable is an eye-sore. Perhaps someone can eliminate it without
resorting to locals :)
2variable d
\ Divide quad by double. Unsigned.
: DUM/MOD ( uq ud -- udrem udquot )
d 2! [ 16 cells ] literal 0 do
dup >r 2swap dup >r d2* 2swap d2*
r> 0< dup d- 2dup d 2@ du< 0= r> 0< or
if d 2@ d- 2swap 1 0 d+ 2swap then
loop 2swap ;
\ Divide doubles. Unsigned.
: DU/MOD ( ud1 ud2 -- udrem udquot )
0 0 2swap dum/mod ;
\ Divide doubles. Signed. Symmetric.
: D/MOD ( d1 d2 -- drem dquot )
2 pick 2dup xor 2>r dabs 2swap dabs
2swap du/mod r> 0< if dnegate then
r> 0< if 2swap dnegate 2swap then ;
Had them somewhere on my drive, but have no access
to my system right now, so could not double-check
whether this is still correct:
\ Check double symmetric and floored division
1 8 CELLS 1- LSHIFT CONSTANT MSB
MSB INVERT CONSTANT MINT
T{ 0. 1. d/rem -> 0. 0. }T
T{ 2. 3. d/rem -> 2. 0. }T
T{ 10. 7. d/rem -> 3. 1. }T
T{ -10. 7. d/rem -> -3. -1. }T
T{ 10. -7. d/rem -> 3. -1. }T
T{ -10. -7. d/rem -> -3. 1. }T
T{ 0 1 2. d/rem -> 0. msb 0 }T
T{ 0 mint 2. d/rem -> 0. msb mint 2/ }T
T{ -1 mint 2dup d/rem -> 0. 1. }T
T{ 1 mint 0 mint d/rem -> 1. 1. }T
T{ 0 mint 1 mint d/rem -> 0 mint 0. }T
T{ -1 mint 2. d/rem -> 1. -1 mint 1 rshift }T
T{ 10. 7. d/mod -> 3. 1. }T
T{ -10. 7. d/mod -> 4. -2. }T
T{ 10. -7. d/mod -> -4. -2. }T
T{ -10. -7. d/mod -> -3. 1. }T
T{ 0. 1. d/ -> 0. }T
T{ 20. 7. d/ -> 2. }T
T{ -20. 7. d/ -> -2. }T
T{ 20. -7. d/ -> -2. }T
T{ -20. -7. d/ -> 2. }T
I've been working on extending the kForth-64 User's Manual and, in particular, illustrating double length arithmetic, which, being one of
the strengths of Forth, often does not get enough exposure. Here's an exercise which you can do using only standard Forth words.
How many different ways can you choose 42 distinct objects, 21 at a
time? This is "n choose k" or the binomial coefficent.
On Sat, 06 Jul 2024 22:20:45 Krishna Myneni wrote:_________________________________________________________^^^^^^^^^^
[...]
Yes, M*/ comes in handy for C(n,0) = 1 , C(n+1,k+1) = C(n,k)*n/k
On Sat, 06 Jul 2024 22:20:45 Krishna Myneni wrote:...
How many different ways can you choose 42 distinct objects, 21 at a
time? This is "n choose k" or the binomial coefficent.
Yes, M*/ comes in handy for C(n,0) = 1 , C(n+1,k+1) = C(n,k)*n/k
42 21 binom d.
gives 538257874440
where
: binom ( n1 n2 -- nd ) \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
Gforth SEE nicely replaced the original 'recurse' with 'binom' for
better readability.
The limitiation is within FALOG that works with float64
i.e. 52 significant bits ~ about 16 decimal digits only.
A Forth with DFLOAT=float80 (x87) works with 64 signif. bits
i.e. about 21 decimal digits.
If this is a problem, the Pascal triangle does not have
such limitations.
: binom ( n1 n2 -- nd ) \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
Gforth SEE nicely replaced the original 'recurse' with 'binom' for
better readability.
M.O.
The limitiation is within FALOG that works with float64
i.e. 52 significant bits ~ about 16 decimal digits only.
A Forth with DFLOAT=float80 (x87) works with 64 signif. bits
i.e. about 21 decimal digits.
If this is a problem, the Pascal triangle does not have
such limitations.
So I prefer:
:F binom ;
:R binom ( n1 n2 -- nd ) \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
In my efforts to Make A Lisp (a github https://github.com/kanaka/mal )
I discovered that using recurse is an ugly cludge that present
a lot of problems in refactoring code, if not prevent it.
Forward and resolve definitions is the more sane method, cf. c.
It is hardly more complicated.
There's a reason why RECURSE (or equivalent) is preferable to having the
name of the word in the output of SEE in Forth. This is because it is >possible to have an earlier definition with the same name and to call it
from within the definition e.g.
: binom ... ;
: binom ... binom ... ;
On Mon, 15 Jul 2024 10:41:54 +0000, albert@spenarnc.xs4all.nl wrote:
So I prefer:
:F binom ;
:R binom ( n1 n2 -- nd ) \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
In my efforts to Make A Lisp (a github https://github.com/kanaka/mal )
I discovered that using recurse is an ugly cludge that present
a lot of problems in refactoring code, if not prevent it.
Forward and resolve definitions is the more sane method, cf. c.
It is hardly more complicated.
IIRC gforth has RECURSIVE to avoid duplicating definitions.
minforth@gmx.net (minforth) writes:
On Mon, 15 Jul 2024 10:41:54 +0000, albert@spenarnc.xs4all.nl wrote:
So I prefer:
:F binom ;
:R binom ( n1 n2 -- nd ) \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
In my efforts to Make A Lisp (a github https://github.com/kanaka/mal )
I discovered that using recurse is an ugly cludge that present
a lot of problems in refactoring code, if not prevent it.
Forward and resolve definitions is the more sane method, cf. c.
It is hardly more complicated.
IIRC gforth has RECURSIVE to avoid duplicating definitions.
Yes. So for a direct recursion like this one you can write
: binom ( n1 n2 -- nd ) recursive \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
RECURSIVE also allows you to tick the word in its own definition (not possible with RECURSE), a feature that I actually have used; something
along the lines:
: walk ( node -- ) recursive
dup is-leaf? if
... \ do something for the leaf
else \ the node has subnodes
node ['] walk for-each-subnode
then ;
Gforth (development) also has FORWARD, which also allows you to do
mutual recursion, e.g.
forward foo
: bar ( n -- ) dup . 1- foo ;
: foo ( n -- ) dup 0> if bar else drop then ;
5 foo \ prints "5 4 3 2 1 "
let's see what the decompiler says:
simple-see foo
$7F54E256E870 dup 0->0
$7F54E256E878 0> 0->0
$7F54E256E880 ?branch 0->0
$7F54E256E888 <foo+$40>
$7F54E256E890 call 0->0
$7F54E256E898 bar
$7F54E256E8A0 branch 0->0
$7F54E256E8A8 <foo+$48>
$7F54E256E8B0 drop 0->0
$7F54E256E8B8 ;s 0->0 ok
simple-see bar
$7F54E256E810 dup 0->0
$7F54E256E818 call 0->0
$7F54E256E820 .
$7F54E256E828 1- 0->0
$7F54E256E830 call 0->0
$7F54E256E838 foo
$7F54E256E840 ;s 0->0 ok
$7F54E256E838 @ hex. \ prints $7F54E256E870
The last like shows that the call to FOO inside BAR directly calls the
FOO defined above, no DEFER or somesuch involved in this case.
The definition of FORWARD is quite intricate and uses several recent
features of Gforth. Read all about it in <2018Dec31.161743@mips.complang.tuwien.ac.at>.
Is the Stirling approximation really precise enough in order
to compute binomial coefficients to the last decimnal digit?
Gforth (development) also has FORWARD, which also allows you to do
mutual recursion, e.g.
forward foo
: bar ( n -- ) dup . 1- foo ;
: foo ( n -- ) dup 0> if bar else drop then ;
5 foo \ prints "5 4 3 2 1 "
let's see what the decompiler says:
The definition of FORWARD is quite intricate and uses several recent
features of Gforth. Read all about it in ><2018Dec31.161743@mips.complang.tuwien.ac.at>.
- anton--
RECURSIVE also allows you to tick the word in its own definition (not
possible with RECURSE), a feature that I actually have used;
I think, there should be a standard method to get the xt of the current definition (regardless whether it is a named definition, or nameless definition).
On 7/14/24 16:43, Marc Olschok wrote:
On Sat, 06 Jul 2024 22:20:45 Krishna Myneni wrote:...
How many different ways can you choose 42 distinct objects, 21 at a
time? This is "n choose k" or the binomial coefficent.
Yes, M*/ comes in handy for C(n,0) = 1 , C(n+1,k+1) = C(n,k)*n/k
42 21 binom d.
gives 538257874440
where
: binom ( n1 n2 -- nd ) \ n k --> C(n,k)
dup 0=
IF 2drop 1 s>d
ELSE 2dup 1- swap 1- swap binom 2swap m*/
THEN ;
Gforth SEE nicely replaced the original 'recurse' with 'binom' for
better readability.
THank you for the recursive version. It's nice to have both looping and recursive examples.
There's a reason why RECURSE (or equivalent) is preferable to having the
name of the word in the output of SEE in Forth. This is because it is possible to have an earlier definition with the same name and to call it
from within the definition e.g.
: binom ... ;
: binom ... binom ... ;
In the later definition of BINOM Forth requires the call to BINOM be the earlier definition if it exists in the search order. If it does not
exist in the search order, then I believe the standard would require an
error to occur.
On 15/07/2024 20:37, Ruvim wrote:^^^^^^^^
RECURSIVE also allows you to tick the word in its own definition (not
possible with RECURSE), a feature that I actually have used;
I think, there should be a standard method to get the xt of the
current definition (regardless whether it is a named definition, or
nameless definition).
It can be done by using DEFER as a forward definition
e.g.
defer foo
:noname ... ['] foo defer@ ... ; is foo
using DEFER@ gives the xt of the code, omittimg it gives the xt of the
name.
as FOO can be called by name by executing
synoname foo recurse
I would guess that your suggestion of FORWARD FOO could be defined using
that and something like EXECUTE-PARSING e.g. copying "FOO RECURSE" to a buffer and doing:
BUF COUNT ' SYNONYM EXECUTE-PARSING
followed by IMMEDIATE of course
As DEFER can be used as a forward definition it can also be used for
mutual recursion
I would guess that your suggestion of FORWARD FOO could be defined using
that and something like EXECUTE-PARSING e.g. copying "FOO RECURSE" to a buffer and doing:
BUF COUNT ' SYNONYM EXECUTE-PARSING
followed by IMMEDIATE of course
I think, there should be a standard method to get the xt of the current definition (regardless whether it is a named definition, or nameless definition).
forward foo
: bar ( n -- ) dup . 1- foo ;
: foo ( n -- ) dup 0> if bar else drop then ;
5 foo \ prints "5 4 3 2 1 "
Pretzel coding. I wondered what that could be useful for.
With a 2-pass Forth compiler, it becomes a trivial matter.
forward foo
: bar ( n -- ) dup . 1- foo ;
: foo ( n -- ) dup 0> if bar else drop then ;
5 foo \ prints "5 4 3 2 1 "
Toad code using Wil Baden type local macros ( /MM: MM ):
"dup . 1- myself" /mm: bar OK
: foo dup 0> if mm bar else drop then ; OK
5 foo 5 4 3 2 1 OK
Note: The macro BAR does not remain in the system image.
--
me
Shortly after I posted I recalled that some have an aversion to
the use of macros and the main point of the example code, I
assume, is the use of a hard coded fragment that includes some
variable that can somehow bind to the entry of the word(s) in
which it will be used.
--
me
On 16/07/2024 10:02 pm, sjack wrote:
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
forward foo
: bar ( n -- ) dup . 1- foo ;
: foo ( n -- ) dup 0> if bar else drop then ;
5 foo \ prints "5 4 3 2 1 "
Toad code using Wil Baden type local macros ( /MM: MM ):
"dup . 1- myself" /mm: bar OK
: foo dup 0> if mm bar else drop then ; OK
5 foo 5 4 3 2 1 OK
Note: The macro BAR does not remain in the system image.
I would use:
defer foo
: bar ( n -- ) dup . 1- foo ;
:noname ( n -- ) dup 0> if bar else drop then ; is foo
5 foo \ prints "5 4 3 2 1 "
DEFER may not be as fast as a directly patched definition but neither
has that prevented a generation from using it.
DEFER may not be as fast as a directly patched definition but neither
has that prevented a generation from using it.
On 17 Jul 2024 at 08:47:45 BST, "dxf" <dxforth@gmail.com> wrote:
DEFER may not be as fast as a directly patched definition but neither
has that prevented a generation from using it.
At least on x64 and CISC CPUs, calling a deferred word is just
CALL [] foo
rather than
CALL foo
The difference on x64 is one byte and a a few (hardware and cache
dependent) cycles.
IMHO Forward referencing and resolving words are likely just to be
wrappers for syntactic sugar around DEFER and IS.
[...]
THank you for the recursive version. It's nice to have both looping and recursive examples.
There's a reason why RECURSE (or equivalent) is preferable to having the
name of the word in the output of SEE in Forth. This is because it is possible to have an earlier definition with the same name and to call it
from within the definition e.g.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 475 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 18:48:42 |
| Calls: | 9,487 |
| Calls today: | 6 |
| Files: | 13,617 |
| Messages: | 6,121,093 |