Problem with a rosetta code exercise

[Frizzus]

Hi, 

I'm brand new to 4tH and i'm learning through rosetta code exercise.

I'm currently on the "proper divisors" .

On the rosetta code web page, the numbers are only printed and not stored.

I tried to store the result in an array to get some experience with arrays.

Then this error appears when i'm calculating the proper divisors for numbers from 1 to 20 000.

```

The proper divisors of 6 are : {1 , 2 , 3 }
The proper divisors of 100 are : {1 , 2 , 4 , 5 , 10 , 20 , 25 , 50 }
Cannot resize darray
Executing;      Word 217: Unhandled exception
```

My guess is that the darray is not made to be this big.
Is there a way to augment the storage capacity ?
Should i try with another structure like an array or a varray ?

I'll gladly accept every other pieces of advice, if you find something wrong or odd.

Loïc

My code :

```

include lib/darray.4th
\ All number used will be positive integers

( is n1 a proper divisor of n2 )
: proper_divisor?  ( n1 n2 -- bool )
    swap mod
    0 =
;
: proper_divisors_of ( n -- )
    variable divisors
    divisors +darray

    dup 1 do
        dup i swap proper_divisor? if
            divisors d.cell+
            i divisors d.len 1 - divisors d.!
        then
    loop
;


variable number_in

: .divisors ( -- )
    ." The proper divisors of " number_in @ . ." are : {"
    divisors d.len 0 ?do
        i divisors d.@ .
        i divisors d.len 1 - = not if ." , " then
    loop
    ." }" cr
;

\ proper_divisors_of tests
6 number_in !
number_in @ proper_divisors_of
.divisors

divisors -darray

100 number_in !
number_in @ proper_divisors_of
.divisors

divisors -darray

\ get the integer with the most proper divisors up to 20 000
variable divisor_count
0 divisor_count !
variable answer
0 answer !
20000 1 ?do
    i proper_divisors_of
    divisors d.len divisor_count @ > if
        divisors d.len divisors !
        i answer !
        divisors d.len . ." | "
    then
loop
." The number between 1 and 20 000 with the most proper divisors is " answer @ . ." with " divisor_count @ . ." divisors"

divisors -darray

```

[The Beez]

Ok, this one works.

include lib/anstools.4th

include lib/darray.4th

\ All number used will be positive integers

variable number_in
variable divisors
variable answer
variable divisor_count

( is n1 a proper divisor of n2 )
: proper_divisor?  ( n1 n2 -- bool )
    swap mod
    0=
;

: proper_divisors_of ( n -- )

    dup 1 do
        dup i swap proper_divisor? if
            divisors d.cell+
            i divisors d.len 1- divisors d.!
        then

    loop drop
;

: .divisors ( -- )
    ." The proper divisors of " number_in @ . ." are : {"
    divisors d.len 0 ?do
        i divisors d.@ .

        i divisors d.len 1- <> if ." , " then
    loop
    ." }" cr
;

\ Next, define a variable - and turn it into a dynamic array:

divisors +darray

\ proper_divisors_of tests
6 number_in !
number_in @ proper_divisors_of
.divisors
divisors -darray

divisors +darray

100 number_in !
number_in @ proper_divisors_of
.divisors
divisors -darray


\ get the integer with the most proper divisors up to 20 000

0 divisor_count !
1 answer !

divisors +darray

20000 1 ?do i proper_divisors_of

  divisors d.len dup divisor_count @ >
  if divisor_count ! i answer ! else drop then
  divisors -darray divisors +darray
loop  
divisors -darray

cr ." The number between 1 and 20 000 with the most proper divisors is " answer @ . ." with " divisor_count @ . ." divisors" cr

Well, there were a few problems here:

1. You list all variables at the beginning of the program. You don't want to go hunting for variables throughout your program. This is not C;
2. You NEVER initialize virtual memory within a subroutine, unless you free it there too. Make it easy on yourself to match allocations with deallocations;
3. If you're using an API, don't assume, use that API consistently;
4. I kept it like that, but why use virtual memory anyway?? You make it very hard on yourself. Why not use a STATIC array? When using a range of 20,000 it is unlikely it has more than 20,000 divisors..
5. Use shortcuts like <>, 1-, etc. BTW, NOT is no part of Forth anymore;
6. Keep track of the stack! You caused stack corruption!
7. Proper array indexes are not optional. D.LEN is NEVER a proper array index! D.LEN 1- is..
8. Managing virtual memory is not optional!

BTW, does this make sense?

": proper_divisor? SWAP mod 0= ;" vs. "dup i SWAP proper_divisor?"

You swap the items in the proper order - and then swap them again.

If I sound harsh, I'm sorry. But Forth is not very forgiving. If you want to write significant programs in Forth, you need to be very disciplined, because a simple mistake may bring your work down. 

In Forth, nobody is holding your hand. Nor will anyone save you when you run onto the road..

Build your word, test it (also for stack errors, most importantly) rigorously and then continue. Look for consistency (like the two SWAPs). Keep things close together  (like +DARRAY and -DARRAY).

All in all, you did pretty good for someone new to the language. Keep up the good work! And come back when you need any help!

Hans Bezemer

[The Beez]

Same program, same output, no variables at all.

: proper_divisor? mod 0= ;             ( n1 -- n2)
: proper_divisors_of dup 1 do dup i proper_divisor? if i . then loop drop ;
: proper_divisors# 0 over 1 do over i proper_divisor? if 1+ then loop nip ;
                                       ( n1 -- #div)
: .divisors                            ( n --)
  ." The proper divisors of " dup . ." are : { " proper_divisors_of ." }" cr
;

: most_divisors  ( n1 -- num #div)
  1 0 rot 1
  ?do i proper_divisors# over over < if i swap 2nip else drop then loop
;

    6 .divisors
  100 .divisors
 20000 most_divisors

cr ." The number between 1 and 20 000 with the most proper divisors is " swap . ." with " . ." divisors" cr
\ depth .

Hans Bezemer

On Tuesday, March 4, 2025 at 5:08:37 PM UTC+1 Frizzus wrote:

[Frizzus]

Thanks for your answer !

I will check all of this and ask if I find anything weird.
You do not sound harsh, not to me at least, don't worry. One reason I want to learn more about forth is because you need that discipline to do things, it will help me as I often need someone to keep me on track.

Loïc

[The Beez]

Hi Frizzus!

".. because you need that discipline to do things"

Exactly! In Python or BASIC (or even C) you can fool around - and somehow still get something working. Forth is much more like Assembly - one small error and you're done. 4tH is in a sense more forgiving than most other Forths, because it will bail out and tell you where it bailed out and why.

In Forth, it's best to practice the chamois principle: don't move a leg before you're sure the other three legs are firmly footed. So, design a word, test it, make a word that uses that word, test it, etc. Now why is it more fun? Because you are capable of coding and testing even when very early in the process. I find myself writing much more code in C before I'm comfortable to test anything. In Forth you get that dopamine rush a lot sooner.

So get rid of that feeling you have to write a lot of code (or even an entire program) before you can start to test it as soon as possible. And sure - everyone violates that rule every now and then. I do every now and then when I transcribe a subroutine from another language. But often, you find you regret that decision. I know I do ;-)

But you're getting it, I like it!

Hans Bezemer

[The Beez]

BTW, I found the most crucial error in the latter part of your program:

20000 1 ?do
  i proper_divisors_of
  divisors d.len divisor_count @ > if

    divisors d.len divisor_count !
    i answer !

    divisors d.len . ." | "
  then

  divisors -darray divisors +darray
loop

The point is, you didn't free up the previous divisors in your program. So the virtual array grew and grew and grew until it blew out of its default available memory (16K, that's just 2048 elements) and was unable to reallocate the array. Now, this could have freed all that memory, but deleting the entire thing and recreating it again is much faster:

  divisors d.len 0 ?do divisors d.cell- loop

You have to know that DARRAYs are created for situations where (sequential) data is consistently incoming - and you don't know how much memory you will actually need. VARRAYs are similar, but the difference is that you don't know the actual index range. So if you happen to need element #1024 it will enlarge the VARRAY so that element #1024 is valid - even when all elements between index 0 and 1023 remain unused.

4tH also supports static arrays out of the box, like: 20000 ARRAY MYDIVISORS

Hope this helps, BTW, this is the output of your original program:

The proper divisors of 6 are : {1 , 2 , 3 }
The proper divisors of 100 are : {1 , 2 , 4 , 5 , 10 , 20 , 25 , 50 }

1 | 2 | 3 | 5 | 7 | 8 | 9 | 11 | 15 | 17 | 19 | 23 | 29 | 31 | 35 | 39 | 47 | 59 | 63 | 71 | 79 |
The number between 1 and 20 000 with the most proper divisors is 15120 with 79 divisors

Hans Bezemer

[Frizzus]

Hi !
I took note of it, and I'm writing a version with static arrays and fewer variables.

I was wondering how efficient shortcuts are compared to longer versions.
Is there a real point in using "1+" instead of "1 +" ?

Loïc

[Guy Mengel]

Hi all,

Just a quick note. 

1. Rosetta Stone and programming problems.. I am inspired ! forth too!

2. This is my first real post here.  Use forth for many years in the late 70's thru 90's...

3. Programming forth is helping me overcome my strokes.. ;-)

Thanks for the info on Rosetta Stone, and Hans, for putting this together.. just installed on my Debian 12 instance..

regards

Guy (N1GMM)  yeah a ham.. going to make vfo's evntually using fourth (4th).

[The Beez]

Franky, 4tH optimizes these expressions automatically. So, 1 + is compiled as 1+. As a matter of fact, 4tH does "constant folding', so every expression that can be simplified at compile time, is automatically simplified.

Other Forths don't. So it is a good habit to use "shortcuts" where ever you can.

Hans Bezemer

[The Beez]

Hi!

This is a nice example of how 4tH compiles and optimizes code. The basic idea is that 4tH's optimizer HELPS to optimize code that would otherwise be hard to achieve (or only through dirty tricks, which are hard to understand) - NOT to clean up thoughtless code.

This is a nice example - it comes from a .BMP loading routine:

: rgb!                                 ( a --)
  /BMPpix BMPpix over accept = if      \ invert RGB values
    /BMPpix 0 do BMPpix /BMPpix 1- i - chars + c@ over i chars + c! loop drop
  ;then drop BMPabort                  \ abort on read error
;

  1203| branch                           1227
  1204| literal                             3
  1205| literal                       1441674
  1206| over                                0
  1207| accept                              0
  1208| =                                   0
  1209| 0branch                          1225
  1210| literal                             3
  1211| literal                             0
  1212| do                               1223
  1213| literal                       1441674
  1214| literal                             2
  1215| r@                                  0
  1216| -                                   0
  1217| +                                   0
  1218| c@                                  0
  1219| over                                0
  1220| r@                                  0
  1221| +                                   0
  1222| c!                                  0
  1223| loop                             1212
  1224| drop                                0
  1225| exit                                0
  1226| drop                                0
  1227| branch                           1175

blabla

Now, /BMPpix equals 3. We can deduct that from opcode 1210, where it is the upper limit of a DO..LOOP. That means that this snippet "/BMPpix 1-" should normally translate to "3 1-" - but it doesn't. It compiles to opcode 1214, which is a single "2". Of course, we could also have written: "/BMPpix i 1+ -" but then the optimizer could not have added that "1+" to "i" (since "i" changes throughout the loop), and it would have resulted in "3 i 1+ -", which is four instructions instead of one. In a loop no less. That is called for every single pixel in the file. Even for a 800*600 pixel file that is 480K times which you could have saved by simply rearranging a few instructions.

We can see another saving in 1224-1227. Normally one would write ".. drop else drop BMPabort then". ";THEN" compiles to "EXIT THEN", so we leave the word right after the first "DROP". Which means that anything that comes after it is never reached. "BMPabort" can also be "tail called" (tail call optimization) - and the futile BRANCH from ELSE to the EXIT is completely futile - and hence optimized away. Another effect of the tail call is that the Return Stack becomes less crowded (since the BRANCH to BMPabort doesn't require a return address).

Compare these two variants to see the full effect:

: foo drop ;
: bar dup if drop else foo then ;

     0| branch                              2   foo
     1| drop                                0
     2| exit                                0
     3| branch                              9   bar
     4| dup                                 0
     5| 0branch                             7
     6| drop                                0
     7| branch                              8
     8| branch                              0   foo
     9| exit                                0

: foo drop ;
: bar dup if drop ;then foo ;

     0| branch                              2   foo
     1| drop                                0
     2| exit                                0
     3| branch                              8   bar
     4| dup                                 0
     5| 0branch                             7
     6| drop                                0
     7| exit                                0
     8| branch                              0   foo

Now, both will compile properly - and are completely valid. There is nothing wrong with either variant. It's just that one of them is slightly faster and shorter.

Hans Bezemer

[The Beez]

Oops! "which is four instructions instead of one" - no, it's four instructions instead of three. "i -" are still compiled. Sorry!

Hans Bezemer

[Frizzus]

Hi, I'm back with my proper division problem.

I tried to do a version with static arrays and fewer variables.
Most words are working correctly, except ".most_divisors".

I used your "no variable" version as help, but it seems that my stack is shambled, and I don't know why.

I'll take a look at the 4th optimization example a little bit later.

Loïc





include lib/anstools.4th

\ All number used will be positive integers

20000 array divisors

( is n1 a proper divisor of n2 )
: proper_divisor?  ( n1 n2 -- bool )

    mod 0=
;

: proper_divisors_of ( n -- index_max )     \ n
    0                                       \ n 0
    over 1 do                               \ n 0 n 1 -> n 0
        over i proper_divisor? if           \ n 0 n i -> n 0
            i over divisors th !            \ n 0 i 0 -> n 0
            1+                              \ n 0 1 + -> n 1
        then                                \ n 1 or n 0
    loop nip 1-                            \ the last index used in divisors array
;


: .divisors ( n -- )                                \ n
    ." The proper divisors of " dup . ." are : {"   \ n n -> n

    proper_divisors_of                              \ n -> imax
    dup 1+ 0 ?do                                    \ imax imax 1 + 0 -> imax imax+1 0 -> imax
        divisors i th @ .                           \ imax i -> imax @i -> imax
        dup i <> if ." , " then                     \ imax imax i -> imax
    loop drop                                       \ imax ->
    ." }" cr
;

: .most_divisors ( n -- )
    \ md = number who has most divisors
    \ ndmd = number of divisors for md
    \ nbi = number of divisors for the current iteration
    1 1 rot                                         \ md ndmd n
    dup 1 ?do                                       \ md ndmd n n 1  -> md ndmd n
        i proper_divisors_of 1+                   \ md ndmd n i -> md ndmd n ndi
        swap rot 2dup > if                          \ md ndmd n ndi -> md ndmd ndi n -> md n ndi ndmd -> md n ndi ndmd ndi ndmd -> md n ndi ndmd
            \ dup .
            \ over .
            drop swap rot drop i rot                   \ md n ndi -> md ndi n -> n ndi md -> n ndi i -> n ndmd md -> md ndmd n
        else
            ." else "
            nip swap                          \ md n ndi ndmd -> md ndmd n
        then
    loop
    ." From 1 to " . ." The numbers with the most divisors is " swap . ." ( " . ." divisors )" cr
;
\ need a value for the current number with most divisors "md"
\ need a value for the number of divisors of md "ndmd"
\ For each number from 1 to n
\ Check proper divisor of i
\ compare ndmd with the number of proper divisors of i
\ if ndi > ndmd => ndi become ndmd and i become md



6 .divisors

100 .divisors

20000 .most_divisors

[The Beez]

Hi Loïc!

Ok, I tell you how I went on doing this:

• I copied your listing to an editor and began debugging - WITHOUT looking at my original, "variable less" source;
• I thought by myself "Why is he dragging that "20000" on the front of the stack?"
• The point is: you can't reach very far in the stack. Two items is fine, three can be done, four is essentially "unreachable";
• Since you're not doing anything with that 20000 until the very last sequence, I put it on the Return Stack;
• That simplified the thing SIGNIFICANTLY. 2OS was the current count, TOS was the challenging count - which translates nicely to OVER OVER (2DUP);
• Now, the challenging count must be larger than the original one: CHALLENGE > ORIGINAL => ORIGINAL < CHALLENGE;
• The latter is the order of the stack items. You could do "SWAP >" - but why? The expression renders an identical result;
• Now, if the challenging count wins, we have to discard the old "dividend #divisors" pair. We have to preserve the challenging count, though;
• Possible variants: ">R DROP DROP R> I SWAP" (note we have to restore the Return stack, before executing "I");
• Possible variants: "NIP NIP I SWAP" ( note NIP compiles to SWAP DROP);
• Possible variants: "I SWAP 2NIP" (at least visually it is the shortest code);
• If the challenging count loses, we just DROP it. Get the range from the Return stack. Fertig!

Now the fun part is, this is the code I came up with:

: .most_divisors ( n -- )
    \ md = number who has most divisors
    \ ndmd = number of divisors for md
    \ nbi = number of divisors for the current iteration

    dup >r
    1 0 rot                                      \ md ndmd n

    1 ?do                                        \ md ndmd n n 1  -> md ndmd n

      i proper_divisors_of                       \ md ndmd n i -> md ndmd n ndi

      over over < if i swap 2nip else drop then

    loop r>

    ." From 1 to " . ." The numbers with the most divisors is " swap . ." ( " . ." divisors )" cr
;

Which is almost identical to my original version! Now, how can I get closer to your intention? I think, by keeping the count on the data stack. And this is that version:

    1 0 >r over r> swap
    1 ?do
      i proper_divisors_of

      over over < if i swap 2nip else drop then

    loop rot

Now - how did I get about this? We start off with the range - and then add the "dividend #divisors" pair, so this is the stack:

  RANGE DIVIDEND #DIVISORS

For the DO..LOOP we need that range one more time, so this is what we want:

  RANGE DIVIDEND #DIVISORS RANGE

There is a program in the package called STACKOPT.4TH which can help you to figure this out:

$ pp4th -x stackopt.4th rdn rdnr
- Trying a 1 word solution..
No solutions.
- Trying a 2 word solution..
No solutions.
- Trying a 3 word solution..
No solutions.
- Trying a 4 word solution..
>r over r> swap 

$

That's what we plugged in - and that's how we got the current version. This is a trick I have to make a video on - figure out which stack order is the most optimal for your program, and then use STACKOPT.4TH to reshuffle the stack accordingly. Which is what I did here.

Why didn't I try to make your original program to work? Because you started on the wrong foot. And if you continue on that path, it's like quicksand - you'll only sink deeper in what we call "stack acrobatics" in a desperate attempt to get the items in the order you need THAT PARTICULAR MOMENT. Believe me - that's not the way. If the needs of your routine radically change halfway, reshuffle the stack (STACKOPT!) and continue. However, that rarely happens to me, because at that time I already created a new word. Like this:

                                       ( orig chal div -- orig' chal')
: ?dividend >r over over < if r> swap 2nip else drop rdrop then ;

: .most_divisors ( n -- )

  1 0 >r over r> swap 1 ?do i proper_divisors_of i ?dividend loop rot

  ." From 1 to " . ." The numbers with the most divisors is " swap . ." ( " . ." divisors )" cr
;

So instead of having to bother myself with an unknown stack diagram halfway a long routine, I have one single word to bother with - having only three single parameters. And the thing I split it off from collapses to a single line with two easily understandable words. The question mark that begins ?DIVIDEND indicates a decision is made there. If it'd finish with a question mark (like DIVIDEND?) it would indicate it returns a boolean, BTW.

So again - reduce the number of stack items you have to deal with to the ABSOLUTE MINIMUM to keep it manageable. That way the program remains maintainable - and even readable.

Hans Bezemer

[The Beez]

Oops! That's not the correct stack diagram:  ( orig chal div -- orig' chal')

This is the correct stackdiagram  ( div_org #divs_org #divs_chal div_chal -- div' chal')

Hans Bezemer

[The Beez]

BTW, if you REALLY want the most optimal solution for the "range" parameter, this is it:

: .most_divisors ( n -- )

  >r 1 0 r@ 1 ?do i proper_divisors_of i ?dividend loop swap r>

  ." From 1 to " . ." The numbers with the most divisors is " . ." ( " . ." divisors )" cr
;

If you want the ultimate Forth solution, split off the presentation:

                                       ( div_org #divs_org #divs_chal div_chal -- div' #divs')

: ?dividend >r over over < if r> swap 2nip else drop rdrop then ;

: most_divisors >r 1 0 r@ 1 ?do i proper_divisors_of i ?dividend loop swap r> ;
                                       ( range -- #divisors dividend range)
: .most_divisors                       ( #divisors dividend range --)
  most_divisors ." From 1 to " . ." The numbers with the most divisors is " .

  ." ( " . ." divisors )" cr
;

Two one-liners and one word to tie it all together.

Hans Bezemer

[The Beez]

I got a problem with stack diagrams today: ( #divisors dividend range --) must be: ( range --)

[The Beez]

Ok Loïc!

I tried one more time - and I think I got it. In short, you got lost in the stack acrobatics. Lots of your code is close - but no cigar! ;-)

: .most_divisors ( n -- )
    \ md = number who has most divisors
    \ ndmd = number of divisors for md
    \ nbi = number of divisors for the current iteration

    1 0 rot                            \ div #divs range
    dup 1 ?do                          \ div #divs range                    
      i proper_divisors_of ( 1+)       \ div #divs range #chal
      rot 2dup > if   ( swap rot 2dup) \ div range #chal #divs f
        drop rot drop ( drop swap rot) \ range #chal
        i swap rot    ( drop i rot )   \ div #chal range
      else                             \ div range #chal #divs
        nip swap                       \ div #divs range

      then
    loop
    ." From 1 to " . ." The numbers with the most divisors is " swap . ." ( " . ." divisors )" cr
;

Okay, where are the differences:

1. proper_divisors needs no 1+ (why?);
2. ROT already makes #divisors pop up behind the challenger. No need for a SWAP - the only thing it does is bring the useless "range" up to the front;
3. Challenger wins: You lose track after the first DROP - again, the only thing your code does is bring the useless "range" up to the front;
4. After that - you lose game, set and match. "Challenger loses" is perfect, though.
   

Hans  Bezemer

[Frizzus]

Hi there, I understood why I got lost in the stack. I misunderstood ROT. I thought it was switching the 1st and the 3rd elements, and so everything I did couldn't work. And the reason why I added 1+ after proper_divisors_of is because proper_divisors_of does not return the number of divisors, but the index of the last divisors found by the word. For the number 100, the proper divisors are : 1, 2, 4, 5, 10, 20, 25, 50 The last divisor found is located on the index 7, and so by adding 1 I find 8, which is the number of divisors found. I will get another exercise to try to use the return stack, STACKOPT.4TH and try to split more of my code. I need some fresh air x).