[A83] Re: Pythagorean's theorem


[Prev][Next][Index][Thread]

[A83] Re: Pythagorean's theorem



----- Original Message ----- 
From: "David Phillips" <david@acz.org>
To: <assembly-83@lists.ticalc.org>
Sent: Saturday, August 09, 2003 1:10 PM
Subject: [A83] Re: Pythagorean's theorem
[...]

> The square root lookup table can also be 512 bytes.  Store 256 16-bit
> numbers.  Each number is the minimum square value for the root at that
> position:
> 
> [0] 0
> [1] 1
> [2] 4
> [3] 9
> ...
> 
> The above table would always round down.  The table can be calculated to
> round normally.  To find a square root, start at the beginning of the table.
> Loop until the current number is greater than the square value.  The
> previous index is the square root.

A table is not required. One can compute the squares on-the fly simply by 
adding consecutive odd numbers:

  0 + 1 = 1
  1 + 3 = 4
  4 + 5 = 9
  9 + 7 = 16

While this algorithm is simple, it is also slow. An algorithm that computes 
one bit of the result per step, i.e. a binary version of the long-hand square
root algorithm, will be faster on average but will also be harder to program.

-- Norbert




Follow-Ups: References: