Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!swrinde!ucsd!ucbvax!SUN.COM!wmb From: wmb@SUN.COM (Mitch Bradley) Newsgroups: comp.lang.forth Subject: Re: Mathematical routines Message-ID: <9001132254.AA02328@jade.berkeley.edu> Date: 12 Jan 90 08:27:34 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: Forth Interest Group International List Organization: The Internet Lines: 38 Here's a "brute force" square root using binary search. It probably takes more iterations than Newton's method, but the inner loop is pretty simple (only shifts and multiplies) and it might end up being as fast or faster overall. : dsqrt ( d -- n ) \ Note that the square root must fit in a single # 1 65535 ( d low high ) 17 0 do 2over 2over + u2/ ( d d guess ) >r r@ r@ u* d< if ( d low high ) ( r: guess ) drop r> ( d low high' ) else ( d low high ) ( r: guess ) swap drop r> swap ( d low' high ) then ( d low' high' ) loop ( d low high ) 2swap 2drop + u2/ ; The only catch is, the (ancient) version of MVP-FORTH that I have doesn't have U2/ . It should be easy enough to implement; it's just a right shift by 1. (My copy of MVP doesn't have SHIFT either, but presumably your processor has a shift instruction). By the way, here's a neat square root solution for single numbers which is attributed to George Perry: : sqrt ( n -- sqrt ) 1 ( n 1 ) \ Initial guess 10 0 do ( n guess ) \ 20 is enough for 32 bits, 10 for 16 bits 2dup / ( n guess n/guess ) + 2/ ( n newguess ) \ Average old guess and n/oldguess loop ( n sqrt ) nip ( sqrt ) ; (No guarantees about either of these solutions) Mitch