On Saturday, February 11, 2023 at 11:49:42 AM UTC+4, Marcel Hendrix wrote:
> On Saturday, February 11, 2023 at 8:21:06 AM UTC+1, Ala'a wrote:
> > On Saturday, February 11, 2023 at 3:25:52 AM UTC+4, Marcel Hendrix wrote:
> > > On Friday, February 10, 2023 at 9:22:12 PM UTC+1, Ala'a wrote:
> > > > Another solution using the same method by Wirth in nqueen problem (backtracking was called)
> [..]
> > /Allot is combination of ALLOT and 0 FILL
> I found out when trying to run the program more than once.
>
> -marcel
I had updated the code and included /allot, changed ++ into +!, made 'M' at index 0, changed 7 into 8 before the recurse, and added early terminate after finding the solution:

VOCABULARY smem ALSO smem DEFINITIONS

: /ALLOT HERE SWAP DUP ALLOT 0 FILL ;
: 1array CREATE /ALLOT DOES> + ;

8 1array letter
: M ( -- a ) 0 letter ; : S ( -- a ) 1 letter ; : E ( -- a ) 2 letter ;
: N ( -- a ) 3 letter ; : D ( -- a ) 4 letter ; : O ( -- a ) 5 letter ;
: R ( -- a ) 6 letter ; : Y ( -- a ) 7 letter ;

: send s C@ 1000 * e C@ 100 * + n C@ 10 * + d C@ + ;
: more m C@ 1000 * o C@ 100 * + r C@ 10 * + e C@ + ;
: money m C@ 10000 * o C@ 1000 * + n C@ 100 * + e C@ 10 * + y C@ + ;
: sol? send more + money = M C@ 0<> AND ; \ M <> 0 -> 1 unique solution

10 1array digit

: unused ( d - t/f ) digit C@ 0= ; \ safe or unused
: mark ( l d -- ) 1 OVER digit C! SWAP letter C! ;
: unmark ( l d -- ) 0 SWAP digit C! 0 SWAP letter C! ;

VARIABLE tries#

: .send ( -- ) S C@ . E C@ . N C@ . D C@ . ;
: .more ( -- ) M C@ . O C@ . R C@ . E C@ . ;
: .money ( -- ) M C@ . O C@ . N C@ . E C@ . Y C@ . ;
: .tries CR ." After " tries# @ . ." tries, Solution is: " ;
: .equ SPACE SPACE .send CR SPACE SPACE .more CR ." + _ _ _ _" CR .money ;
: .solution ( -- ) CR .tries CR .equ ;
: check ( -- ) sol? IF .solution TRUE ELSE FALSE THEN ;

VARIABLE terminate terminate off

: try ( l -- )
10 0 DO \ Digits \ I digit
1 tries# +! \ CR tries# ? .digits
I unused IF
DUP I mark
DUP 8 < IF DUP 1+ RECURSE ELSE check terminate ! THEN
DUP I unmark
THEN
terminate @ IF DROP UNLOOP EXIT THEN
LOOP DROP ;

: go 0 tries# ! 0 try ;
\ counter go timer BYE
\ timer-reset go .elapsed BYE

go .S KEY BYE

Hope it help

albert@cherry.(none) (albert) writes:
>In article <2023Feb9.115420@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
><SNIP>
>>Plus, in a really good native-code Forth system (beyond what current
>>Forth systems do), locals will also be more efficient, because they
>>can be kept in registers, while global variables have to be stored
>>into memory.
>
>I hope to demonstrate that VARIABLE can be optimised away as easily
>as locals.

Some people hope to build a perpetuum mobile.

For the others, consider:

variable s
variable e
....

: smm ( -- )
\ print all solutions to the SEND+MORE=MONEY puzzle
... \ store to and load from the global variables defined above
;

smm

s ?
e ?
....

SMM has to store at least the final values of the global variables in
memory, so that the user can access them after a call to SMM. You
cannot optimise that away, and even what you can optimise away is not
easy.

>Also there is a false dichotomy (cause by the LOCAL mindset)
>between local and global variables.

And the relevance for the present discussion is?

>In a proper Pascal implementation of qsort there is an intermediate
>storage where e.g. the pointers to procedures are stored.
>They are global to qsort proper, and local to the main program.
>It is almost impossible to break out of the mindset of
>language like c and Forth that cannot have local functions that
>have their own variables. (So I don't blame you ;-) )

Maybe you should read

@InProceedings{ertl&paysan18,
author = {M. Anton Ertl and Bernd Paysan},
title = {Closures --- the {Forth} way},
crossref = {euroforth18},
pages = {17--30},
url = {http://www.complang.tuwien.ac.at/papers/ertl%26paysan.pdf},
url2 = {http://www.euroforth.org/ef18/papers/ertl.pdf},
slides-url = {http://www.euroforth.org/ef18/papers/ertl-slides.pdf},
video = {https://wiki.forth-ev.de/doku.php/events:ef2018:closures},
OPTnote = {refereed},
abstract = {In Forth 200x, a quotation cannot access a local
defined outside it, and therefore cannot be
parameterized in the definition that produces its
execution token. We present Forth closures; they
lift this restriction with minimal implementation
complexity. They are based on passing parameters on
the stack when producing the execution token. The
programmer has to explicitly manage the memory of
the closure. We show a number of usage examples.
We also present the current implementation, which
takes 109~source lines of code (including some extra
features). The programmer can mechanically convert
lexical scoping (accessing a local defined outside)
into code using our closures, by applying assignment
conversion and flat-closure conversion. The result
can do everything one expects from closures,
including passing Knuth's man-or-boy test and living
beyond the end of their enclosing definitions.}
}

@Proceedings{euroforth18,
title = {34th EuroForth Conference},
booktitle = {34th EuroForth Conference},
year = {2018},
key = {EuroForth'18},
url = {http://www.euroforth.org/ef18/papers/proceedings.pdf}
}

One interesting aspect of the work on that paper was that I had
trouble finding simple examples that demonstrate the value of closures
(especially of the (locals-) stack-allocating closures, i.e., what
Pascal is limited to) and that cannot be rewritten without closures in
Forth with relatively little code.

I knew that Niklaus Wirth has this feature is Pascal, Modula-2 and
Oberon, but he is also a minimalist and eliminated features from
Oberon that can be replaced by using other features, such as the FOR
loop. Since he had included access to locals of outer functions in
Oberon, I assumed he had a good motivating use for that feature, so I
asked him about that. Unfortunately, I did not get the answer I was
interested in: He actually had eliminated this feature in a later
revision of Oberon, so he actually had no good reason for it, either.

Concerning the closures of Gforth: You can program without them, so
they are just a convenience, not a necessity. Nevertheless, Bernd
Paysan uses them frequently. I don't use them often. What I use more
often is the feature of postponing the value of a local, which is a
separate feature from Gforth closures, but was implemented when we
implemented closures, because the idea is to use a local where it
normally cannot be used, just like the original idea behind
implementing closures (which then morphed into Gforth closures):

Instead of

: foo {: bar baz :}
... ]] ... [[ bar ]] literal ... [[ baz ]] literal ... [[ ... ;

you just write

: foo {: bar baz :}
... ]] ... bar ... baz ... [[ ... ;

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2022: https://euro.theforth.net

On Saturday, February 11, 2023 at 9:02:55 AM UTC+1, Ala'a wrote:
> On Saturday, February 11, 2023 at 11:49:42 AM UTC+4, Marcel Hendrix wrote:
> > On Saturday, February 11, 2023 at 8:21:06 AM UTC+1, Ala'a wrote:
> > > On Saturday, February 11, 2023 at 3:25:52 AM UTC+4, Marcel Hendrix wrote:
> > > > On Friday, February 10, 2023 at 9:22:12 PM UTC+1, Ala'a wrote:
> > > > > Another solution using the same method by Wirth in nqueen problem (backtracking was called)
> > [..]

That improves the timing from 14.83 to 8.93 milliseconds.
The #tries decreases from 7921010 to 5092470.

-marcel

On 11/02/2023 6:49 pm, Marcel Hendrix wrote:
> On Saturday, February 11, 2023 at 8:21:06 AM UTC+1, Ala'a wrote:
>> On Saturday, February 11, 2023 at 3:25:52 AM UTC+4, Marcel Hendrix wrote:
>>> On Friday, February 10, 2023 at 9:22:12 PM UTC+1, Ala'a wrote:
>>>> Another solution using the same method by Wirth in nqueen problem (backtracking was called)
> [..]
>> /Allot is combination of ALLOT and 0 FILL
>
> I found out when trying to run the program more than once.

SwiftForth has it under that name while VFX calls it ALLOT&ERASE.
Some swear by zeroing variables/buffers etc at compile-time; I
tend to swear at it for the reason you gave.

On Saturday, February 11, 2023 at 11:09:13 AM UTC+1, Marcel Hendrix wrote:
[..]
> That improves the timing from 14.83 to 8.93 milliseconds.
> The #tries decreases from 7921010 to 5092470.

I was quite happy to find this numerical shortcut:
\ : sol? send more + money = M C@ 0<> AND ; \ M <> 0 -> 1 unique solution
: sol? m C@ 0= IF FALSE EXIT ENDIF
( m == 1 ) #10000
o C@ s C@ - ( m C@ ) 1 - #1000 * +
n C@ e C@ - o C@ - #100 * +
e C@ n C@ - r C@ - #10 * +
y C@ d C@ - e C@ - + 0= ;

Unfortunately, the run-time decreases by almost nothing, from 8.93ms to 8.78ms.
The runtime is dominated by the overhead of a recursive call. It could have been
the overhead of the 11 byte fetches, but that proved to be only 13ms.
With a by now very ugly sol?, the best time is 8.65 ms / go.

-marcel

On Saturday, February 11, 2023 at 6:52:50 PM UTC+4, Marcel Hendrix wrote:
> On Saturday, February 11, 2023 at 11:09:13 AM UTC+1, Marcel Hendrix wrote:
> [..]
> > That improves the timing from 14.83 to 8.93 milliseconds.
> > The #tries decreases from 7921010 to 5092470.
> I was quite happy to find this numerical shortcut:
> \ : sol? send more + money = M C@ 0<> AND ; \ M <> 0 -> 1 unique solution
> : sol? m C@ 0= IF FALSE EXIT ENDIF
> ( m == 1 ) #10000
> o C@ s C@ - ( m C@ ) 1 - #1000 * +
> n C@ e C@ - o C@ - #100 * +
> e C@ n C@ - r C@ - #10 * +
> y C@ d C@ - e C@ - + 0= ;
>
> Unfortunately, the run-time decreases by almost nothing, from 8.93ms to 8..78ms.
> The runtime is dominated by the overhead of a recursive call. It could have been
> the overhead of the 11 byte fetches, but that proved to be only 13ms.
> With a by now very ugly sol?, the best time is 8.65 ms / go.
>
> -marcel
This problem can be solved analytically. and using that the first observation is that M can only be 1 through C3 (as M<>0). Thus eliminated as constant. The second (which may be called cheating) is variables (of the letters) ordering (in CSP parlance) using the solution values and changing the indexes of the letters based on their value based on that, help in pruning the search space:

VOCABULARY s11 ALSO s11 DEFINITIONS \ pun intended

: /ALLOT HERE SWAP DUP ALLOT 0 FILL ;
: 1array CREATE /ALLOT DOES> + ;

7 CONSTANT letters#
letters# 1array letter
: O ( -- a ) 0 letter ; : E ( -- a ) 1 letter ; : N ( -- a ) 2 letter ;
: D ( -- a ) 3 letter ; : R ( -- a ) 4 letter ; : S ( -- a ) 5 letter ;
: Y ( -- a ) 6 letter ;

: send s C@ 1000 * e C@ 100 * + n C@ 10 * + d C@ + ;
: more 1000 o C@ 100 * + r C@ 10 * + e C@ + ;
: money 10000 o C@ 1000 * + n C@ 100 * + e C@ 10 * + y C@ + ;
: sol? send more + money = ;

10 1array digit

: unused ( d - t/f ) digit C@ 0= ; \ safe or unused
: mark ( l d -- ) 1 OVER digit C! SWAP letter C! ;
: unmark ( l d -- ) 0 SWAP digit C! 0 SWAP letter C! ;

VARIABLE tries#

: .send ( -- ) S C@ . E C@ . N C@ . D C@ . ;
: .more ( -- ) 1 . O C@ . R C@ . E C@ . ;
: .money ( -- ) 1 . O C@ . N C@ . E C@ . Y C@ . ;
: .tries CR ." After " tries# @ . ." tries, Solution is: " ;
: .equ SPACE SPACE .send CR SPACE SPACE .more CR ." + _ _ _ _" CR .money ;
: .solution ( -- ) CR .tries CR .equ ;
: check ( -- ) sol? IF .solution TRUE ELSE FALSE THEN ;

VARIABLE terminate terminate off

: try ( l -- )
10 0 DO \ Digits \ I digit
1 tries# +! \ CR tries# ? .digits
I unused IF
DUP I mark
DUP letters# < IF DUP 1+ RECURSE ELSE check terminate ! THEN
DUP I unmark
THEN
terminate @ IF DROP UNLOOP EXIT THEN
LOOP DROP ;

: go 0 tries# ! 0 try ;
go
\ ucounter go utimer KEY BYE \ increased preci. from ms to us
\ timer-reset go .elapsed KEY BYE

..S KEY BYE

\\ Tries#
\ previous: 5092470
\ eliminate M: 1535004
\ vars reorder: 304594

Regards,

Ala'a schrieb am Samstag, 11. Februar 2023 um 20:25:36 UTC+1:
> On Saturday, February 11, 2023 at 6:52:50 PM UTC+4, Marcel Hendrix wrote:
> > On Saturday, February 11, 2023 at 11:09:13 AM UTC+1, Marcel Hendrix wrote:
> > [..]
> > > That improves the timing from 14.83 to 8.93 milliseconds.
> > > The #tries decreases from 7921010 to 5092470.
> > I was quite happy to find this numerical shortcut:
> > \ : sol? send more + money = M C@ 0<> AND ; \ M <> 0 -> 1 unique solution
> > : sol? m C@ 0= IF FALSE EXIT ENDIF
> > ( m == 1 ) #10000
> > o C@ s C@ - ( m C@ ) 1 - #1000 * +
> > n C@ e C@ - o C@ - #100 * +
> > e C@ n C@ - r C@ - #10 * +
> > y C@ d C@ - e C@ - + 0= ;
> >
> > Unfortunately, the run-time decreases by almost nothing, from 8.93ms to 8.78ms.
> > The runtime is dominated by the overhead of a recursive call. It could have been
> > the overhead of the 11 byte fetches, but that proved to be only 13ms.
> > With a by now very ugly sol?, the best time is 8.65 ms / go.
> >
> > -marcel
> This problem can be solved analytically. and using that the first observation is that M can only be 1 through C3 (as M<>0). Thus eliminated as constant. The second (which may be called cheating) is variables (of the letters) ordering (in CSP parlance) using the solution values and changing the indexes of the letters based on their value based on that, help in pruning the search space:

Order of variables AND order of constraint evaluation do matter.
Taking profit from this property or even applying constraint propagation
is not cheating but search optimization. ;-)

https://www.ibm.com/docs/en/icos/20.1.0?topic=optimizer-constraint-propagation

Le jeudi 9 février 2023 à 14:24:39 UTC, minf...@arcor.de a écrit :
> Ahmed MELAHI schrieb am Donnerstag, 9. Februar 2023 um 13:47:02 UTC+1:
> > For the case of m<>0 (so m must be 1), the same program gives the also the unique result, by selecting the solution with m=1.
> Merci de tes contributions! Of course M has to be 1 because it has to be a carry bit.
> So you used a mathematical property of one of the constraints to manually reduce your search space.
>
> BTW this shows an interesting common aspect between all the various Forth proposals:
> In their manually coded program formulation they freely join/mix/meddle walking the search space with constraint properties.
> Therefore many different solutions appear on the table depending on programmer's expertise or preference.
>
> Declarative constraint programming languages don't have to do this (ideally). They go in distinctive not related steps:
> 1) declare the variable domains ( here: integers ranging from 0 to 9 )
> 2) span the search space in toto ( here: 8 variables SENDMORY )
> 3) declare the constraints ( here: M<>0 and SEND+MORE=MONEY and all variables unique)
> \ BTW: M<>0 not because of the other constraint but because otherwise MONEY would be written as ONEY ! )
> 4) solve it.
> ( of course real CLP programmers also use their optimization toolbelts .... but that's a different story )
>
> So this is a very generic and very versatile approach! One can add/delete/change constraints in one place without
> having to rewrite the program. And the best: bug-free from start.
>
> How would a Forth programmer come close to this?
>
> ( for fun: try to solve TO+GO=OUT )
Hi,
Here, a program that takes some considerations on m, s and o. m=1, s=9 and o =0.
Also, it uses permutations, for e n d r y
It is based on non informed search algorithm (non informed stochastic search algorithm).
For the timing, it is very fast, but not deterministic, (timing ranges from 20 ms down to about 0.1 ms, but almost under 7ms).
To see this fact, run the program several times and verify the timing.
There are examples of running the program after the program listing.
This program is written and tested with gforth.

\ ---- Program listing begins here
: rand_7 utime drop 7 mod ;

: :- 1 ;
: , and dup 0= if rdrop exit then ;
: -: and if 1 ( cr ." solution found") else 0 then ;

\ here begins the application to send+more=money
0 value solution_found_?

\ sendmory
0 value s
0 value e
0 value n
0 value d
0 value m
0 value o
0 value r
0 value y

\ m s o
: (sendmoremoney)_pre
1 to m \
\ s + m = o + 10m
\ s + 1 = o + 10*1
\ s = o + 9
\ o>=0 ===> o + 9 >= 9 ie s>=9
\ s>=9 and s<=9 ===> unique solution s=9
\ therefore o=0
9 to s
0 to o
;

(sendmoremoney)_pre

\ e n d r y : the 6 first positions
create vals 2 c, 3 c, 4 c, 5 c, 6 c, 7 c, 8 c,

\ for permutations
0 value a
0 value b

\ for carries
0 value c1
0 value c2

: gen_new_permutation
\ by exchanging values in vals at a and b positions,
\ a and b are randomly chosen in 0, 1, 2, ..., 6.
3 0 do
rand_7 to a
rand_7 to b

vals a + c@
vals b + c@
vals a + c!
vals b + c!
loop
;

: gen_endry
gen_new_permutation
4 for vals i + c@ next
to e to n to d to r to y
;

\ send
\ more
\ money

: (sendmoremoney)
:-
gen_endry

d e + 10 /mod to c1 y = ,
c1 n + r + 10 /mod to c2 e = ,
c2 e + n =

-:
;

: go
cr ." Solving ..." cr
0 do
(sendmoremoney)
if 1 to solution_found_? unloop exit else then
loop
0 to solution_found_?
;

: .solution
cr
if
." the solution is: "
cr
s 10 * e + 10 * n + 10 * d + 4 .r ." + "
m 10 * o + 10 * r + 10 * e + 4 .r ." = "
m 10 * o + 10 * n + 10 * e + 10 * y + 5 .r
else
." no solution found."
then
;

utime 100000 go utime d- dnegate d>f 1e-6 f* cr ." Done in: " f. ." seconds." solution_found_? .solution

\ ----Program listing ends here

Examples of running the program:

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.004138 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.005762 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.008374 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.003357 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.000403 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.005634 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.011867 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.019845 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.007549 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.000411 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.000585 seconds.
the solution is:
9567 + 1085 = 10652

>gforth sendmoremoney_3.fs -e "bye"
Solving ...
Done in: 0.005141 seconds.
the solution is:
9567 + 1085 = 10652

Ahmed MELAHI schrieb am Samstag, 11. Februar 2023 um 23:41:19 UTC+1:

> Hi,
> Here, a program that takes some considerations on m, s and o. m=1, s=9 and o =0.
> Also, it uses permutations, for e n d r y
> It is based on non informed search algorithm (non informed stochastic search algorithm).
> For the timing, it is very fast, but not deterministic, (timing ranges from 20 ms down to about 0.1 ms, but almost under 7ms).
> To see this fact, run the program several times and verify the timing.

Each time you were restarting gforth, reloading the program from drive (cache)
someplace into memory, and run your solver only once. This might explain the obeserved
timing jitter.

What are the measurings when you load the program only once and run the solver 1000 times?

Le dimanche 12 février 2023 à 09:03:54 UTC, minf...@arcor.de a écrit :
> Ahmed MELAHI schrieb am Samstag, 11. Februar 2023 um 23:41:19 UTC+1:
>
> > Hi,
> > Here, a program that takes some considerations on m, s and o. m=1, s=9 and o =0.
> > Also, it uses permutations, for e n d r y
> > It is based on non informed search algorithm (non informed stochastic search algorithm).
> > For the timing, it is very fast, but not deterministic, (timing ranges from 20 ms down to about 0.1 ms, but almost under 7ms).
> > To see this fact, run the program several times and verify the timing.
> Each time you were restarting gforth, reloading the program from drive (cache)
> someplace into memory, and run your solver only once. This might explain the obeserved
> timing jitter.
>
> What are the measurings when you load the program only once and run the solver 1000 times?
Hi,
When running inside gforth, 1000 times, the mean timing is:
\ running the program 1000 times and taking the mean value
: timing_1000 utime 1000 0 do 100000 ( max number of tries) go loop utime d- dnegate d>f 1e-6 f* 1000e f/ f. ;
timing_1000 0.003234738 ok
timing_1000 0.003410783 ok
timing_1000 0.003526989 ok
timing_1000 0.003412328 ok
timing_1000 0.003339925 ok
So, approximately 3.4 ms

When invoking the program in command line:
gforth sendmoremoney_3.fs -e "bye"

0.003325417
0.003510594
0.003462138
0.003506971
0.003470388
So, approximately 3.4 ms

Le dimanche 12 février 2023 à 09:03:54 UTC, minf...@arcor.de a écrit :
> Ahmed MELAHI schrieb am Samstag, 11. Februar 2023 um 23:41:19 UTC+1:
>
> > Hi,
> > Here, a program that takes some considerations on m, s and o. m=1, s=9 and o =0.
> > Also, it uses permutations, for e n d r y
> > It is based on non informed search algorithm (non informed stochastic search algorithm).
> > For the timing, it is very fast, but not deterministic, (timing ranges from 20 ms down to about 0.1 ms, but almost under 7ms).
> > To see this fact, run the program several times and verify the timing.
> Each time you were restarting gforth, reloading the program from drive (cache)
> someplace into memory, and run your solver only once. This might explain the obeserved
> timing jitter.
>
> What are the measurings when you load the program only once and run the solver 1000 times?

Hi, again,
Another version of the program, the internal algorithm is modified.

running the timing for 1000 times gives:
Inside gforth
>gforth
Gforth 0.7.9_20170112, Copyright (C) 1995-2016 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `help' for basic help

Here, including the program inside Gforth

include sendmoremoney_4.fs

Mean timing: 0.001022783

Mean timing: 0.001021481

Mean timing: 0.000997707

Mean timing: 0.001114846

Here, executing timing_1000 inside gforth:
Mean timing: 0.001177877 ok
timing_1000
Mean timing: 0.001000998 ok
timing_1000
Mean timing: 0.000886701 ok
timing_1000
Mean timing: 0.000978621 ok
timing_1000
Mean timing: 0.001051597 ok
timing_1000
Mean timing: 0.000961631 ok

When invoked in command line:
>gforth sendmoremoney_4.fs -e "bye"

sendmoremoney_4.fs:9:3: redefined ,
sendmoremoney_4.fs:19:9: redefined n
sendmoremoney_4.fs:48:9: redefined b
sendmoremoney_4.fs:90:9: redefined j with J

Mean timing: 0.000995724

Mean timing: 0.00093175

Mean timing: 0.000977553

Mean timing: 0.000926892

Mean timing: 0.000969498

The program is here

\ ----Program listing begins here
: rand_7 utime drop 7 mod ;
: rand_4 utime drop 4 mod 3 + ;
defer rand
' rand_7 is rand

: :- 1 ;
: , and dup 0= if rdrop exit then ;
: -: and if 1 ( cr ." solution found") else 0 then ;

\ here begins the application to send+more=money
0 value solution_found_?

\ sendmory
0 value s
0 value e
0 value n
0 value d
0 value m
0 value o
0 value r
0 value y

\ m s o
: (sendmoremoney)_pre
1 to m \
\ s + m = o + 10m
\ s + 1 = o + 10*1
\ s = o + 9
\ o>=0 ===> o + 9 >= 9 ie s>=9
\ s>=9 and s<=9 ===> unique solution s=9
\ therefore o=0
9 to s
0 to o
;

(sendmoremoney)_pre

\ y d e r n : the 6 first positions
create vals 2 c, 3 c, 4 c, 5 c, 6 c, 7 c, 8 c,

\ for permutations
0 value a
0 value b

\ for carries
0 value c1
0 value c2

: gen_new_permutation
\ by exchanging values in vals at a and b positions,
\ a and b are randomly chosen in 0, 1, 2, ..., 6.
3 0 do
rand to a
rand to b

vals a + c@
vals b + c@
vals a + c!
vals b + c!
loop
;

: gen_ydern_7
gen_new_permutation
4 for vals i + c@ next
to y to d to e to r to n
;

: gen_ydern_4
gen_new_permutation
1 for vals 3 + i + c@ next
to r to n
; defer gen_ydern
' gen_ydern_7 is gen_ydern

\ send
\ more
\ money

: use_4 ['] gen_ydern_4 is gen_ydern ['] rand_4 is rand ;
: use_7 ['] gen_ydern_7 is gen_ydern ['] rand_7 is rand ;

0 value J
: (sendmoremoney)
:-
gen_ydern

d e + 10 /mod to c1 y = dup if use_4 then ,
J 1+ to J
c1 n + r + 10 /mod to c2 e = J 5 = if 0 to J use_7 then ,
c2 e + n =
-:
;

: sendmoremoney
\ cr ." Solving ..." cr
0 do
(sendmoremoney)
if 1 to solution_found_? unloop exit else then
loop
0 to solution_found_?
;

: .solution
cr
if
." the solution is: "
cr
s 10 * e + 10 * n + 10 * d + 4 .r ." + "
m 10 * o + 10 * r + 10 * e + 4 .r ." = "
m 10 * o + 10 * n + 10 * e + 10 * y + 5 .r
else
." no solution found."
then
;

: go utime 10000 sendmoremoney utime d- dnegate d>f 1e-6 f* cr ." Done in: " f. ." seconds." solution_found_? .solution ;

\ running the program 1000 times and taking the mean value
: timing_1000 utime 1000 0 do 10000 ( max number of tries) sendmoremoney ( solution_found_? .solution) loop utime d- dnegate d>f 1e-6 f* 1000e f/ cr ." Mean timing: " f. ;
cr timing_1000
cr timing_1000
cr timing_1000
cr timing_1000
cr timing_1000

\ ------------- Program listing ends here

On Saturday, February 11, 2023 at 11:41:19 PM UTC+1, Ahmed MELAHI wrote:
> Le jeudi 9 février 2023 à 14:24:39 UTC, minf...@arcor.de a écrit :
> > Ahmed MELAHI schrieb am Donnerstag, 9. Februar 2023 um 13:47:02 UTC+1:
[..]
> Examples of running the program:
[..]
> >gforth sendmoremoney_3.fs -e "bye"
> Solving ...
> Done in: 0.000403 seconds.
> the solution is:
> 9567 + 1085 = 10652
[..]
> >gforth sendmoremoney_3.fs -e "bye"
> Solving ...
> Done in: 0.019845 seconds.
> the solution is:
> 9567 + 1085 = 10652
[..]
> >gforth sendmoremoney_3.fs -e "bye"
> Solving ...
> Done in: 0.000411 seconds.
> the solution is:
> 9567 + 1085 = 10652
>

That's a *very* large variation!

FORTH> go many
Solving ... 39 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 43 microseconds elapsed, the solution is: 9567 + 1085 = 10652
....

Maybe the mysterious "RDROP" in (senmoremany) has something to do with it?
I modified it to:

: (sendmoremoney) ( -- bool )
gen_endry
d e + #10 /MOD TO c1 y <> IF FALSE EXIT ENDIF
c1 n + r + #10 /MOD TO c2 e <> IF FALSE EXIT ENDIF
c2 e + n = ;

-marcel

On Sunday, February 12, 2023 at 1:31:58 PM UTC+1, Marcel Hendrix wrote:
> On Saturday, February 11, 2023 at 11:41:19 PM UTC+1, Ahmed MELAHI wrote:
> > Le jeudi 9 février 2023 à 14:24:39 UTC, minf...@arcor.de a écrit :
> > > Ahmed MELAHI schrieb am Donnerstag, 9. Februar 2023 um 13:47:02 UTC+1:

Still faster: why do gen_new_permutation 3 times?
: gen_new_permutation ( -- )
rand_7 TO a rand_7 TO b
vals a + C@
vals b + C@
vals a + C!
vals b + C! ;

FORTH> GO MANY
Solving ... 15 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 15 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 16 microseconds elapsed, the solution is: 9567 + 1085 = 10652
....
Solving ... 14 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 14 microseconds elapsed, the solution is: 9567 + 1085 = 10652
Solving ... 15 microseconds elapsed, the solution is: 9567 + 1085 = 10652 ok

-marcel

On Sunday, February 12, 2023 at 1:51:37 PM UTC+1, Marcel Hendrix wrote:
> On Sunday, February 12, 2023 at 1:31:58 PM UTC+1, Marcel Hendrix wrote:
> > On Saturday, February 11, 2023 at 11:41:19 PM UTC+1, Ahmed MELAHI wrote:
> > > Le jeudi 9 février 2023 à 14:24:39 UTC, minf...@arcor.de a écrit :
> > > > Ahmed MELAHI schrieb am Donnerstag, 9. Februar 2023 um 13:47:02 UTC+1:

All this basically boils down to:

Given a problem with N variables, where the range of each is known.
It is also known when a random set of values form a correct solution.
The more tests for correctness, the better.

Randomly test variable combinations and stop when a valid solution
is found.

There must be more to it ...
1. Can it be proven that this is faster than testing all possible combinations.
2. Does the algorithm stop in finite time.

This is parallellizable and scales linearly with the number of CPUs?!

Sorry if this has already been answered in the thread (in easily digestable morsels).

-marcel

On Wednesday, February 8, 2023 at 11:09:04 AM UTC+1, Anton Ertl wrote:
> "minf...@arcor.de" <minf...@arcor.de> writes:
> Performance (with gforth-fast on a 4GHz Skylake):
> minforth Ertl
> 6_428_853_392 39_964 cycles:u
> 19_625_679_081 114_372 instructions:u

So it took 1.607 seconds on minforth and 9.991us on Ertl?
(what do "cycles:u" and "instructions:u" mean exactly?)

-marcel

Le dimanche 12 février 2023 à 12:31:58 UTC, Marcel Hendrix a écrit :
> On Saturday, February 11, 2023 at 11:41:19 PM UTC+1, Ahmed MELAHI wrote:
> > Le jeudi 9 février 2023 à 14:24:39 UTC, minf...@arcor.de a écrit :
> > > Ahmed MELAHI schrieb am Donnerstag, 9. Februar 2023 um 13:47:02 UTC+1:
> [..]
> > Examples of running the program:
> [..]
> > >gforth sendmoremoney_3.fs -e "bye"
> > Solving ...
> > Done in: 0.000403 seconds.
> > the solution is:
> > 9567 + 1085 = 10652
> [..]
> > >gforth sendmoremoney_3.fs -e "bye"
> > Solving ...
> > Done in: 0.019845 seconds.
> > the solution is:
> > 9567 + 1085 = 10652
> [..]
> > >gforth sendmoremoney_3.fs -e "bye"
> > Solving ...
> > Done in: 0.000411 seconds.
> > the solution is:
> > 9567 + 1085 = 10652
> >
> That's a *very* large variation!
Yes, I noticed that.
I think it is due the non informed stochastic search algorithm, it does not consider the previous results in order to enhance and speed up the search.
Perhaps, one can use informed search algorithms (particle swarm optimization, genetic algorithms, ... in general meta-heuristic or nature inspired optimization algorithms).
This problem is a combinatorics problem, one can use Ant Colonies Algorithms, they are suited for this kind of problems.

>
> FORTH> go many
> Solving ... 39 microseconds elapsed, the solution is: 9567 + 1085 = 10652
> Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
> Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
> Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
> Solving ... 40 microseconds elapsed, the solution is: 9567 + 1085 = 10652
> Solving ... 43 microseconds elapsed, the solution is: 9567 + 1085 = 10652
> ...
Thanks for testing the program.

>
> Maybe the mysterious "RDROP" in (senmoremany) has something to do with it?
> I modified it to:
>
> : (sendmoremoney) ( -- bool )
> gen_endry
> d e + #10 /MOD TO c1 y <> IF FALSE EXIT ENDIF
> c1 n + r + #10 /MOD TO c2 e <> IF FALSE EXIT ENDIF
> c2 e + n = ;
>
In fact, I don' t want to change that, I wanted a form of Constrained Logic Programming (like in Prolog, but limited).
The algorithm will repeat from the begining with a new combination off SENDMORY when a logical constraint fails. This is done by the comma (here I changed , to do another job than compiling a literal in Here place in the dictionnary).

As another problem, Solving systems of nonlinear equations with several unknowns. Here a program, it is not fast but shows the approach applied.
These programs can be parallelized. I haven't done that.

\ here begins the listing of the program

\ solving system of equations:
\ "x^-2 - 3y + sin(z) + 25.96 = 0"
\ "3x + 2y^-3 + cos(z) - 15.0027 = 0"
\ "x^0.5 + y^2 + 2z - 86.377 = 0"

\ for x real in interval [0, 10] and y real in interval [5 , 15] and z real in interval [0, 10]
\ the exact solution x=5, y=9, z= pi/2=1.57..

s" random.fs" included

10000000000 value max_tries

: :- 1 ;
: , and dup 0= if rdrop exit then ;
: -: and if 1 ( cr ." solution found") else 0 then ;

100000000000000000000 value f_random_interval_size
: frandom f_random_interval_size dup s>f 1/f random s>f f* f* ; \
: f_min_max fover f- frandom f+ ;

0 value nvars

\ here begins the application

3 to nvars

0e fvalue x
0e fvalue y
0e fvalue z

0e fvalue x_lb
10e fvalue x_ub

5e fvalue y_lb
15e fvalue y_ub

0e fvalue z_lb
10e fvalue z_ub

1e-1 fvalue tolerance
0e fvalue d

: f1() x -2e f** 3e y f* f- z fsin f+ 25.96e f+ ;
: f2() 3e x f* 2e y -3e f** f* f+ z fcos f+ 15.0027e f- ;
: f3() x 0.5e f** y 2e f** f+ 2e z f* f+ 86.377e f- ;

: J() f1() fabs f2() fabs fmax f3() fabs fmax ;

: (solve)
:-
x_lb x_ub f_min_max to x
y_lb y_ub f_min_max to y
z_lb z_ub f_min_max to z

J() 0e tolerance f~ ,
cr
cr ." x = " x f.
cr ." y = " y f.
cr ." z = " z f.
cr ." J = " J() f.
cr ." tol = " tolerance f.
tolerance 10e f* to d
x d f- to x_lb x d f+ to x_ub
y d f- to y_lb y d f+ to y_ub
z d f- to z_lb z d f+ to z_ub
tolerance 10e f/ to tolerance

tolerance 1e-5 f<
-:
;

: solve
cr ." Solving ..." cr

0 do
(solve)
if 1 unloop exit else then
loop
0
;

: .solution
if
cr
." the solution is: "
cr
x f. 3 spaces y f. 3 spaces z f.
cr
." and f1(" x f. ." , " y f. ." , " z f. ." ) = " f1() f.
cr
." and f2(" x f. ." , " y f. ." , " z f. ." ) = " f2() f.
cr
." and f3(" x f. ." , " y f. ." , " z f. ." ) = " f3() f.
cr
else
cr
." no solution found"
then
cr
;

: go max_tries solve .solution ;

utime go utime d- dnegate d>f 1e-6 f* cr ." Done in: " f. ." seconds."

\ here the listing ends

An example of execution, invoked from the command line.
>gforth example_17___.fs -e "bye"

example_17___.fs:15:3: redefined ,
Solving ...

x = 5.22328085000251
y = 8.92117924078448
z = 2.21615179013329
J = 0.0718075600349124
tol = 0.1

x = 5.00370337297728
y = 8.99778115706805
z = 1.58740980572947
J = 0.00645933992813141
tol = 0.01

x = 5.00024926378217
y = 8.99989580954397
z = 1.57148403461704
J = 0.000308346974765783
tol = 0.001

x = 4.99992918754341
y = 8.99998001504991
z = 1.5706404342282
J = 0.0000610757223924452
tol = 0.0001

x = 4.99986667439217
y = 9.00000363175878
z = 1.57044565251771
J = 0.00000882346749975227
tol = 0.00001

the solution is:
4.99986667439217 9.00000363175878 1.57044565251771
and f1(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000882346749975227
and f2(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000582164974893828
and f3(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000515850457816214

Done in: 182.639417 seconds.

> -marcel

Marcel Hendrix <mhx@iae.nl> writes:
>On Wednesday, February 8, 2023 at 11:09:04 AM UTC+1, Anton Ertl wrote:
>> "minf...@arcor.de" <minf...@arcor.de> writes:
>> Performance (with gforth-fast on a 4GHz Skylake):
>
>> minforth Ertl
>> 6_428_853_392 39_964 cycles:u
>> 19_625_679_081 114_372 instructions:u
>
>So it took 1.607 seconds on minforth and 9.991us on Ertl?

Yes.

>(what do "cycles:u" and "instructions:u" mean exactly?)

":u" means in user mode. The system-mode stuff is small here. I
usually measure user-mode stuff because that is what I normally
influence. However, if there are significant differences in memory
consumption, the system-mode (":k") time also differs significantly
(due to allocating the memory in system mode).

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2022: https://euro.theforth.net

Ahmed MELAHI schrieb am Sonntag, 12. Februar 2023 um 16:06:44 UTC+1:
> As another problem, Solving systems of nonlinear equations with several unknowns. Here a program, it is not fast but shows the approach applied.
> These programs can be parallelized. I haven't done that.
>
> \ here begins the listing of the program
>
> \ solving system of equations:
> \ "x^-2 - 3y + sin(z) + 25.96 = 0"
> \ "3x + 2y^-3 + cos(z) - 15.0027 = 0"
> \ "x^0.5 + y^2 + 2z - 86.377 = 0"
>
> \ for x real in interval [0, 10] and y real in interval [5 , 15] and z real in interval [0, 10]
> \ the exact solution x=5, y=9, z= pi/2=1.57..
>
>
> s" random.fs" included
>
> 10000000000 value max_tries
> : :- 1 ;
> : , and dup 0= if rdrop exit then ;
> : -: and if 1 ( cr ." solution found") else 0 then ;
> 100000000000000000000 value f_random_interval_size
> : frandom f_random_interval_size dup s>f 1/f random s>f f* f* ; \
> : f_min_max fover f- frandom f+ ;
>
> 0 value nvars
>
>
> \ here begins the application
>
> 3 to nvars
>
> 0e fvalue x
> 0e fvalue y
> 0e fvalue z
>
>
> 0e fvalue x_lb
> 10e fvalue x_ub
>
> 5e fvalue y_lb
> 15e fvalue y_ub
>
> 0e fvalue z_lb
> 10e fvalue z_ub
>
>
> 1e-1 fvalue tolerance
> 0e fvalue d
>
> : f1() x -2e f** 3e y f* f- z fsin f+ 25.96e f+ ;
> : f2() 3e x f* 2e y -3e f** f* f+ z fcos f+ 15.0027e f- ;
> : f3() x 0.5e f** y 2e f** f+ 2e z f* f+ 86.377e f- ;
>
> : J() f1() fabs f2() fabs fmax f3() fabs fmax ;
>
> : (solve)
> :-
> x_lb x_ub f_min_max to x
> y_lb y_ub f_min_max to y
> z_lb z_ub f_min_max to z
>
> J() 0e tolerance f~ ,
> cr
> cr ." x = " x f.
> cr ." y = " y f.
> cr ." z = " z f.
> cr ." J = " J() f.
> cr ." tol = " tolerance f.
> tolerance 10e f* to d
> x d f- to x_lb x d f+ to x_ub
> y d f- to y_lb y d f+ to y_ub
> z d f- to z_lb z d f+ to z_ub
> tolerance 10e f/ to tolerance
>
> tolerance 1e-5 f<
> -:
> ;
>
>
> : solve
> cr ." Solving ..." cr
>
> 0 do
> (solve)
> if 1 unloop exit else then
> loop
> 0
> ;
>
>
> : .solution
> if
> cr
> ." the solution is: "
> cr
> x f. 3 spaces y f. 3 spaces z f.
> cr
> ." and f1(" x f. ." , " y f. ." , " z f. ." ) = " f1() f.
> cr
> ." and f2(" x f. ." , " y f. ." , " z f. ." ) = " f2() f.
> cr
> ." and f3(" x f. ." , " y f. ." , " z f. ." ) = " f3() f.
> cr
> else
> cr
> ." no solution found"
> then
> cr
> ;
> : go max_tries solve .solution ;
>
> utime go utime d- dnegate d>f 1e-6 f* cr ." Done in: " f. ." seconds."
>
>
> \ here the listing ends
>
> An example of execution, invoked from the command line.
> >gforth example_17___.fs -e "bye"
>
> example_17___.fs:15:3: redefined ,
> Solving ...
>
>
> x = 5.22328085000251
> y = 8.92117924078448
> z = 2.21615179013329
> J = 0.0718075600349124
> tol = 0.1
>
> x = 5.00370337297728
> y = 8.99778115706805
> z = 1.58740980572947
> J = 0.00645933992813141
> tol = 0.01
>
> x = 5.00024926378217
> y = 8.99989580954397
> z = 1.57148403461704
> J = 0.000308346974765783
> tol = 0.001
>
> x = 4.99992918754341
> y = 8.99998001504991
> z = 1.5706404342282
> J = 0.0000610757223924452
> tol = 0.0001
>
> x = 4.99986667439217
> y = 9.00000363175878
> z = 1.57044565251771
> J = 0.00000882346749975227
> tol = 0.00001
>
> the solution is:
> 4.99986667439217 9.00000363175878 1.57044565251771
> and f1(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000882346749975227
> and f2(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000582164974893828
> and f3(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000515850457816214
>
> Done in: 182.639417 seconds.
>

This took long. "In practice" or "usually" such numerical Monte Carlo methods are stopped after a certain time.
The results are used as start values for a following Newtor-Raphson iteration.

Marcel Hendrix <mhx@iae.nl> writes:
>All this basically boils down to:
>
>Given a problem with N variables, where the range of each is known.
>It is also known when a random set of values form a correct solution.=20
>The more tests for correctness, the better.

What you call tests are called constraints in the literature. See
<https://en.wikipedia.org/wiki/Constraint_satisfaction_problem>

>Randomly test variable combinations and stop when a valid solution
>is found.

The more common approach is to walk the search space in a systematic
way, especially if you want to find all solutions, or are searching
for an optimal solution. There are general and problem-specific
heuristics for the search.

>There must be more to it ...=20
>1. Can it be proven that this is faster than testing all possible combinati=
>ons.=20

A random search that does not exclude the previously searched space
will likely take more time than a search that visits every part of the
search space at most once.

>2. Does the algorithm stop in finite time.

That probably depends on the definition of finite time you use. For
every time span you give, there is a probability p>0 that such a
random search does not stop. OTOH, the probability that this
algorithm never stops is 0 (at least with a true random number
generator).

>This is parallellizable and scales linearly with the number of CPUs?!

Random search that ignores other attempts is perfectly parallelizable.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: https://forth-standard.org/
EuroForth 2022: https://euro.theforth.net

Le dimanche 12 février 2023 à 15:50:04 UTC, minf...@arcor.de a écrit :
> Ahmed MELAHI schrieb am Sonntag, 12. Februar 2023 um 16:06:44 UTC+1:
> > As another problem, Solving systems of nonlinear equations with several unknowns. Here a program, it is not fast but shows the approach applied.
> > These programs can be parallelized. I haven't done that.
> >
> > \ here begins the listing of the program
> >
> > \ solving system of equations:
> > \ "x^-2 - 3y + sin(z) + 25.96 = 0"
> > \ "3x + 2y^-3 + cos(z) - 15.0027 = 0"
> > \ "x^0.5 + y^2 + 2z - 86.377 = 0"
> >
> > \ for x real in interval [0, 10] and y real in interval [5 , 15] and z real in interval [0, 10]
> > \ the exact solution x=5, y=9, z= pi/2=1.57..
> >
> >
> > s" random.fs" included
> >
> > 10000000000 value max_tries
> > : :- 1 ;
> > : , and dup 0= if rdrop exit then ;
> > : -: and if 1 ( cr ." solution found") else 0 then ;
> > 100000000000000000000 value f_random_interval_size
> > : frandom f_random_interval_size dup s>f 1/f random s>f f* f* ; \
> > : f_min_max fover f- frandom f+ ;
> >
> > 0 value nvars
> >
> >
> > \ here begins the application
> >
> > 3 to nvars
> >
> > 0e fvalue x
> > 0e fvalue y
> > 0e fvalue z
> >
> >
> > 0e fvalue x_lb
> > 10e fvalue x_ub
> >
> > 5e fvalue y_lb
> > 15e fvalue y_ub
> >
> > 0e fvalue z_lb
> > 10e fvalue z_ub
> >
> >
> > 1e-1 fvalue tolerance
> > 0e fvalue d
> >
> > : f1() x -2e f** 3e y f* f- z fsin f+ 25.96e f+ ;
> > : f2() 3e x f* 2e y -3e f** f* f+ z fcos f+ 15.0027e f- ;
> > : f3() x 0.5e f** y 2e f** f+ 2e z f* f+ 86.377e f- ;
> >
> > : J() f1() fabs f2() fabs fmax f3() fabs fmax ;
> >
> > : (solve)
> > :-
> > x_lb x_ub f_min_max to x
> > y_lb y_ub f_min_max to y
> > z_lb z_ub f_min_max to z
> >
> > J() 0e tolerance f~ ,
> > cr
> > cr ." x = " x f.
> > cr ." y = " y f.
> > cr ." z = " z f.
> > cr ." J = " J() f.
> > cr ." tol = " tolerance f.
> > tolerance 10e f* to d
> > x d f- to x_lb x d f+ to x_ub
> > y d f- to y_lb y d f+ to y_ub
> > z d f- to z_lb z d f+ to z_ub
> > tolerance 10e f/ to tolerance
> >
> > tolerance 1e-5 f<
> > -:
> > ;
> >
> >
> > : solve
> > cr ." Solving ..." cr
> >
> > 0 do
> > (solve)
> > if 1 unloop exit else then
> > loop
> > 0
> > ;
> >
> >
> > : .solution
> > if
> > cr
> > ." the solution is: "
> > cr
> > x f. 3 spaces y f. 3 spaces z f.
> > cr
> > ." and f1(" x f. ." , " y f. ." , " z f. ." ) = " f1() f.
> > cr
> > ." and f2(" x f. ." , " y f. ." , " z f. ." ) = " f2() f.
> > cr
> > ." and f3(" x f. ." , " y f. ." , " z f. ." ) = " f3() f.
> > cr
> > else
> > cr
> > ." no solution found"
> > then
> > cr
> > ;
> > : go max_tries solve .solution ;
> >
> > utime go utime d- dnegate d>f 1e-6 f* cr ." Done in: " f. ." seconds."
> >
> >
> > \ here the listing ends
> >
> > An example of execution, invoked from the command line.
> > >gforth example_17___.fs -e "bye"
> >
> > example_17___.fs:15:3: redefined ,
> > Solving ...
> >
> >
> > x = 5.22328085000251
> > y = 8.92117924078448
> > z = 2.21615179013329
> > J = 0.0718075600349124
> > tol = 0.1
> >
> > x = 5.00370337297728
> > y = 8.99778115706805
> > z = 1.58740980572947
> > J = 0.00645933992813141
> > tol = 0.01
> >
> > x = 5.00024926378217
> > y = 8.99989580954397
> > z = 1.57148403461704
> > J = 0.000308346974765783
> > tol = 0.001
> >
> > x = 4.99992918754341
> > y = 8.99998001504991
> > z = 1.5706404342282
> > J = 0.0000610757223924452
> > tol = 0.0001
> >
> > x = 4.99986667439217
> > y = 9.00000363175878
> > z = 1.57044565251771
> > J = 0.00000882346749975227
> > tol = 0.00001
> >
> > the solution is:
> > 4.99986667439217 9.00000363175878 1.57044565251771
> > and f1(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000882346749975227
> > and f2(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000582164974893828
> > and f3(4.99986667439217 , 9.00000363175878 , 1.57044565251771 ) = -0.00000515850457816214
> >
> > Done in: 182.639417 seconds.
> >
> This took long. "In practice" or "usually" such numerical Monte Carlo methods are stopped after a certain time.
Yes, that is exact. Here, we can add that.
After max tries reached, the program ends displaying "No solution found."
> The results are used as start values for a following Newtor-Raphson iteration.

Newton-Raphson method is applyied when derivatives can be obtained exactly or approximately.
and the risc of local minima, when doing optimization
Here, the system of equations is modified to an optimization problem (minimize J(x,y,z) = max(|f1(x,y,z)|, |f2(x,y,z)|,|f3(x,y,z)|).
This approach is for global optimization.
This program can be easily adapted to do PSO, GA, ACO, ...

If we know approximatly where the exact solution is, we can narrow the search by better choosing the bounds x_lb, x_ub, y_lb, y_ub, z_lb, z_ub from the begining.
when doing that, here is an example of execution of the program: begin with a guess such that 4<x0<6, 8<y<10 and 1<z<2

>gforth example_17___.fs

example_17___.fs:15:3: redefined ,
Solving ...

x = 5.13340715565075
y = 8.96324338810272
z = 1.90589619163218
J = 0.0714353597311668
tol = 0.1

x = 5.0106695818288
y = 8.99665735028719
z = 1.60276546379233
J = 0.00934681137117011
tol = 0.01

x = 5.00005030825161
y = 8.99999139570694
z = 1.57072125014805
J = 0.00036684983365376
tol = 0.001

x = 4.9999655699891
y = 8.99997686550441
z = 1.57071415902657
J = 0.000072176369840804
tol = 0.0001

x = 4.99987183911066
y = 9.00000197566145
z = 1.57046031227259
J = 0.00000498573381513268
tol = 0.00001
the solution is:
4.99987183911066 9.00000197566145 1.57046031227259
and f1(4.99987183911066 , 9.00000197566145 , 1.57046031227259 ) = -0.00000393278417121223
and f2(4.99987183911066 , 9.00000197566145 , 1.57046031227259 ) = -0.00000498573381513268
and f3(4.99987183911066 , 9.00000197566145 , 1.57046031227259 ) = -0.00000449387462708728

Done in: 61.759371 seconds

another execution: tolerance <0.001,

>gforth example_17___.fs

example_17___.fs:15:3: redefined ,
Solving ...

x = 5.01952077651797
y = 8.99102558931017
z = 1.66198604322517
J = 0.0324493494156268
tol = 0.1

x = 5.2117127444467
y = 8.91966518354894
z = 2.26680933844081
J = 0.00590664353095427
tol = 0.01

x = 5.21753194764435
y = 8.91782527807446
z = 2.28290184633388
J = 0.000713201761579185
tol = 0.001
the solution is:
5.21753194764435 8.91782527807446 2.28290184633388
and f1(5.21753194764435 , 8.91782527807446 , 2.28290184633388 ) = 0.00024604367860448
and f2(5.21753194764435 , 8.91782527807446 , 2.28290184633388 ) = -0.000713201761579185
and f3(5.21753194764435 , 8.91782527807446 , 2.28290184633388 ) = 0.000603132247888993

Done in: 14.389063 seconds.

In general, one can speed up the execution by modifying some parameters.
When using informed search (stochastic, PSO, ...) the random choose of x, y and z can be lowered slightly. (I have done this in matlab, julia, python, and gforth with other programs that implement PSO for upto 4 unkowns, can be done for >4 unkowns) ).

On Sunday, February 12, 2023 at 5:05:21 PM UTC+1, Anton Ertl wrote:
> Marcel Hendrix <m...@iae.nl> writes:
[..]
> >This is parallellizable and scales linearly with the number of CPUs?!
> Random search that ignores other attempts is perfectly parallelizable.

I guess it wouldn't help for the problem at hand because the variation
in run-time is almost negligible.

In a general case, one might need a way to generate batched (size N)
random numbers that don't repeat in the same batch (Sobel sequences)?

-marcel

On Sunday, February 12, 2023 at 5:38:04 PM UTC+1, Ahmed MELAHI wrote:
> Le dimanche 12 février 2023 à 15:50:04 UTC, minf...@arcor.de a écrit :
> > Ahmed MELAHI schrieb am Sonntag, 12. Februar 2023 um 16:06:44 UTC+1:
> > > As another problem, Solving systems of nonlinear equations with several unknowns.
> > > Here a program, it is not fast but shows the approach applied.

Won't Amoeba work here? With linear bounds it is by definition possible
to construct a convex hull.

-marcel

Ahmed MELAHI schrieb am Sonntag, 12. Februar 2023 um 17:38:04 UTC+1:
> > This took long. "In practice" or "usually" such numerical Monte Carlo methods are stopped after a certain time.
> Yes, that is exact. Here, we can add that.
> After max tries reached, the program ends displaying "No solution found."
> > The results are used as start values for a following Newtor-Raphson iteration.
> Newton-Raphson method is applyied when derivatives can be obtained exactly or approximately.
> and the risc of local minima, when doing optimization
> Here, the system of equations is modified to an optimization problem (minimize J(x,y,z) = max(|f1(x,y,z)|, |f2(x,y,z)|,|f3(x,y,z)|).
> This approach is for global optimization.

The big difference to other optimization problems is that here the functions are
known and therefore gradients can be calculated directly.

Of course there still is a low probability that the last best global Monte Carlo estimation
is not local enough around the unknown target and sidetracks to an inferior solution.

Le dimanche 12 février 2023 à 19:38:49 UTC, minf...@arcor.de a écrit :
> Ahmed MELAHI schrieb am Sonntag, 12. Februar 2023 um 17:38:04 UTC+1:
> > > This took long. "In practice" or "usually" such numerical Monte Carlo methods are stopped after a certain time.
> > Yes, that is exact. Here, we can add that.
> > After max tries reached, the program ends displaying "No solution found.."
> > > The results are used as start values for a following Newtor-Raphson iteration.
> > Newton-Raphson method is applyied when derivatives can be obtained exactly or approximately.
> > and the risc of local minima, when doing optimization
> > Here, the system of equations is modified to an optimization problem (minimize J(x,y,z) = max(|f1(x,y,z)|, |f2(x,y,z)|,|f3(x,y,z)|).
> > This approach is for global optimization.
> The big difference to other optimization problems is that here the functions are
> known and therefore gradients can be calculated directly.
>
> Of course there still is a low probability that the last best global Monte Carlo estimation
> is not local enough around the unknown target and sidetracks to an inferior solution.

Agreed,

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> However, given that your C++ solution is a lot faster and cannot
> benefit from lazy evaluation, I expect that the potential lazy
> evaluation advantage does not happen in this Haskell program.

OK, here is my insane Forth version. Runtime with gforth-fast 0.7 about
1.4 seconds on same laptop as before. Same brute force algorithm. Uses
the following highly recommended (lol) Forth techniques:

- ROLL and FPICK with variable depths up to 10 deep
- 13 local variables in one word
- stores temporary small integer values on floating point stack
(this works with IEEE floating point, YMMV otherwise)
- A couple more that I have forgotten.

================================================================

: 10f@>s ( copy 10 integers from fp stack to data stack :O )
10 0 do 9 i - fpick f>s loop ;

: checkresult ( -- )
10f@>s { x0 x1 s e n d m o r y }
m 0> x0 x1 > and IF
s 1000 * e 100 * + n 10 * + d + { send }
m 1000 * o 100 * + r 10 * + e + { more }
m 10000 * o 1000 * + n 100 * + e 10 * + y + { money }
send more + money = IF
send . more . money . cr
THEN
THEN ;

: rec ( n1 n2 ... )
depth 0= IF
checkresult
ELSE
depth { d }
d 0 DO
s>f RECURSE f>s d 1- ROLL
LOOP
THEN ;

0 1 2 3 4 5 6 7 8 9 rec bye