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

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


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.

• 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.
– pmg
Jun 27, 2020 at 10:39

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