3
\$\begingroup\$

I'm doing Project Euler problems as a learning platform for Forth. Currently I'm solving Project Euler Problem 8 which involves a 1000-long string, which I entered directly in the source code.

My questions are:

  1. What options are common for dealing with input?
  2. If I put the locals on the stack, won't that make the loop too full of (otherwise unneeded) stack manipulation words?
  3. Suggestions, criticism, nitpicks are welcome...
: e008-multNdigits ( a n -- p )
    1 swap 0 do swap dup i + c@ [char] 0 - rot * loop nip ;

: euler008
    0 13 locals| length maxproduct |
    s" 731671765313306249192...450"
    ( a 1000 )
    length - 0 do
        dup i + length e008-multNdigits
        dup maxproduct > if to maxproduct else drop then
    loop maxproduct . ;
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Disclaimer: my Forth is extremely rusty.

  • length does not need to be local; is not a variable, it is a constant. Declare it as such:

    13 constant length
    
  • Dealing with input. The stack annotation ( a 1000 ) strongly hints that what follows wants to be the word on its own. Indeed, logic should be separated from IO. Consider, for example, something along the lines of

    : e008 ( a n -- p)
        ....
    ;
    
    s" 731671765313306249192...450"
    euler008
    .
    

    Once the logic and IO are separated, you may use open-file and read-file if you wish.

  • I do not endorse one-liners, especially if they involve loop. Consider

    : e008-multNdigits ( a n -- p )
        1 swap 0
        do
            swap
            dup i +
            c@ [char] 0 -
            rot *
        loop
        nip ;
    

    As a side note, nip is very rarely useful, and usually it is an indication of the suboptimal design. Try to get rid of it. The nipped value, if I am not mistaken, is a base address of the array. I have an impression that its only purpose is to undo a dup in the caller. Try to get rid of both.

  • The line

      dup maxproduct > if to maxproduct else drop then
    

    is a long way to say

      maxproduct max to maxproduct
    
  • Consider having max product at TOS prior to setting up a call to e008-multNdigits. In this case,

      length - 0 do
          dup i + length e008-multNdigits
          max
    

    would suffice, and eliminate the need for the local.


Not Forth-related issues:

  • The algorithm performs 13000 multiplications. A sliding window approach lets you get away with 1000 multiplications and 1000 divisions. Of course an extra care should be taken when 0 is encountered.

  • The product of 13 digits may take as much as 42 bits. A naive multiplication fails on a 32-bit cells.


Finally, Project Euler is not about programming. It is about math. To hone your Forth skills, consider implementing classical algorithms, and benchmark them against conventional implementations.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks a lot for your comments; still working on them. I'm using gforth on a 64-bit Debian: it uses 64-bits cells -- I had checked that earlier. \$\endgroup\$
    – pmg
    Jun 27, 2020 at 10:39
0
\$\begingroup\$

After @vnp's suggestions (input separated from logic, locals removed without too many stack manipulations, use MAX word, maximum product on TOS), the code changed to

s" 731671765313306249192251196744265747423...450"
   2constant e008-input-string

\ stack comment legend
\ a address; w width, p product, l length, M maxproduct

\ multiply w consecutive digits from a
\ uses w internally but keeps it on stack for next loop
: e008-multNdigits ( w a -- w p )
    2dup + 1 rot rot swap         \  ( w 1 w+a a )
    do i c@ [char] 0 - * loop ;   \ keep *ing each digit with the 1

: euler008 ( w a l -- M )
    \ set up stack
    >r >r 0 over rot r> dup rot - r> + swap ( 0 w a-w+l a )
    do i e008-multNdigits rot max swap
    loop drop ;

\ run with, eg: 13 e008-input-string euler008 .
\ or 2 s" 1111111118761111" euler008 . ==> prints 56
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.