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.

• pmg: 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.

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