Project Euler 8: find the maximum product of 13 consecutive digits

Question

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 . ;

Answer 1

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.

Answer 2

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