Why does this tiny program NOT work??!?

Quote:

> I found in an old book on Forth (about 1984) a small sieve that serves me very

> well as a crude benchmark.

Note, that the definitions you gave do not implement the sieve

algorthim to find prime numbers but does a simple repetitive

divisable test to check if a given number is a prime number.

Throwing in some stack comments, we might find some inconsistencies or

problems:

variable line

: test ( p n -- f ) mod 0= ; \ What a nice nothing telling name.

: print ( p -- p )

\ Note, that print does not consume its argument. Poor style?

dup 5 .r ( p )

if cr drop 4

else 1 -

then

line !

;

: ptest ( p -- )

\ Due to the unecessary unbalanced LOOP-exits, I consider this definition

\ extremely poor Forth code.

dup 2 / 2 ( p p/2 2 )

do ( p )

dup i test ( p f )

if 0 leave ( p 0 )

then ( p )

loop ( p | p 0 )

dup ( p p | p 0 0 )

if ( p )

print ( p )

else ( p 0 )

drop ( p )

then ( p )

drop ( )

;

: prime ( to from -- )

cr

4 line !

do i ptest loop ( )

cr

;

Quote:

> I did some tests with PTEST and got some strange results. 7 works, 5

> Forth-79 and Forth-83. Which definition has changed since then in

> such a way that this thing doesn't work anymore?

I think the problem in this example is the DO loop. Given 5 as argument,

PTEST will execute a 2 2 DO LOOP which will run the full number circle

if not left meanwhile. Fortunately 5 5 TEST will return true and so

this loop is left nearly immediately. The loop in 1 PTEST (0 2 DO LOOP)

will not be left since 1 I TEST will always return false.

Quote:

> Anybody any ideas?

I came up with the following ANS Forth standard program:

: divided? ( n1 n2 -- f ) MOD 0= ;

\ Return true iff n2 divides n1 (n1 is divided by n2).

\ Same result with floored and symmetrical division since arguments are positive.

: prime? ( n -- f )

DUP 1 = IF DROP FALSE EXIT THEN ( n )

DUP 2 divided? IF DROP FALSE EXIT THEN ( n )

3 ( n n1 )

BEGIN ( n n1 )

2DUP DUP * < IF 2DROP TRUE EXIT THEN ( n n1 )

2DUP divided? IF 2DROP FALSE EXIT THEN ( n n1 )

2+

AGAIN ;

\ Note that this algorithm is different from (and more efficient than) the one

\ above.

\ 1) Apart from 2 it tests only odd denominators and

\ 2) it tests only upto (and including) the square-root of the potential

\ prime number, which is sufficient.

\

\ I believe PRIME? is much a better factor than PTEST above, since it does no

\ IO. PRIME? can be reused in definitions like:

\

\ : next-prime ( n -- n' ) BEGIN 1+ DUP prime? UNTIL ;

\ or

\ : prime-twin? ( n -- ) DUP prime? OVER 2+ prime? and ;

: prime ( to from -- ) ?DO I prime? IF I . THEN LOOP ;

Ulrich

--

Ulrich Hoffmann, Uni Kiel WWW: http://www.informatik.uni-kiel.de/~uho/

Preusserstr 1-9, D-24105 Kiel, Germany Tel: +49 431 560426 Fax: 566143