Example 3. Square Root

There are many ways to take the square root of an integer. The special routine here was first discovered by Wil Baden. Wil used this routine as a programming challenge while attending a FORML Conference in Taiwan, 1984.

This algorithm is based on the fact that the square of n+1 is equal to the sum of the square of n plus 2n+1. You start with an 0 on the stack and add to it 1, 3, 5, 7, etc., until the sum is greater than the integer you wished to take the root. That number when you stopped is the square root.
<pre>
: SQRT ( n1 -- n2, n2**2<=n1 )
0 ( initial root )
SWAP 0 ( set n1 as the limit )
DO 1 + DUP ( refresh root )
2* 1 + ( 2n+1 )
+LOOP ( add 2n+1 to sum, loop if )
; ( less than n1, else done )
</pre>
The definite loop structure:

( limit index ) DO <repeat-clasue> ( inc ) +LOOP

is very similar to the DO...LOOP sructure in repeating the repeat-clause. The difference is that +LOOP increments the index by the number on the top of the data stack. It thus allow the loop index to be incremented or decremented by an arbitrary amount computed at the run time. +LOOP terminates the loop when the incremented index is equal to or greater then the limit.

Wil uses +LOOP in an unconventional way. Here the index is used as an accumulator, adding up the sequence of (2n+1) until the sum exceeds n1. At this point, n2 left on the stack is the square root of n1.


Exercise 2. Newton's method to find the square root is a very common method used in computers. If r1 is an approximation to the square root of n, then a better approximation is:

r2 = ( r1 + n/r1 ) /2

See if you can write a program to find the square root this way.

Exercise 3. Cube and power of 4 of integers can run out of the single interger range very quickly. It is therefore not a bad idea to find the cubic roots or power of 4 roots by raising consecutive integers to the 3rd or 4th power and compare them to the integer you want to take the root. Write new instruction CubicRoot to find the cubic root of any positive integer. Try the same for the root of 4th power as well.

При всем уважении к языку Forth, нет ни времени ни желания изучать синтаксис и методологию языка для решение единожды вставшей задачи.