From: RussellMc <apptechnz@gmail.com>
To: Microcontroller discussion list - Public. <piclist@mit.edu>
CC: ApptechNZ <apptechnz@gmail.com>
Sender: "piclist-bounces@mit.edu" <piclist-bounces@mit.edu>
Date: Wed, 23 Sep 2020 03:54:16 -0700
Subject: Re: [AVR] square on AVR
Thread-Topic: [AVR] square on AVR
Thread-Index: AdaRmc8Ptnc1DLKHQWSQsJ+amtU+SA==
Message-ID:
 <CACZQxzM=K3RHkHwWXECG7u-Bu2MeqaooQ2irXbVEphfyuPdTfQ@mail.gmail.com>
References:
 <jeNVUT-MJm2s1816cafY6zWnTP_hSKOUh12Jiu6cHWgYXt4nFSNawBANsqphFe5WUCtL69GjTE9I1HdnaM-7BdO6uj9wqIjsoZrPJbdynsA=@protonmail.com>
	<20200917143553.1f650e132099b5782f4d0416@tom.com>
	<e27321e4-e82e-17ce-a7b1-164819fb885e@gmail.com>
	<20200918103123.4c19706e1106c492a8a11695@tom.com>
	<CACZQxzNQd4Q9xXkwgd39uMAdxotR9TfFOY8_DTNF+BLzyhmF4w@mail.gmail.com>
	<alpine.BSF.2.21.9999.2009212327550.94713@nickel.allotrope.net>
In-Reply-To: <alpine.BSF.2.21.9999.2009212327550.94713@nickel.allotrope.net>
Reply-To: Microcontroller discussion list - Public. <piclist@mit.edu>
Accept-Language: en-US
X-MS-Exchange-Organization-SenderIdResult: Pass
X-MS-Exchange-Organization-PRD: mit.edu
X-MS-TNEF-Correlator:
received-spf: Pass (protection.outlook.com: domain of gmail.com designates
	209.85.218.47 as permitted sender) receiver=protection.outlook.com;
	client-ip=209.85.218.47; helo=mail-ej1-f47.google.com;
dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com;
 s=20161025;
	h=mime-version:references:in-reply-to:from:date:message-id:subject:to	:cc;
 bh=2LhPU38mPA4aa96FhKVtHIUo2GZ25sQ/PBpI+154vLA=;
	b=Wcn+mOtNjZMfXlcS2+lj0FJJ7xGUrjGTFAYUj3kZX4/KRynvi2lrQC49uVp3WXch32
	to92JCF7GnHygTOFmh4vO25qFxlwgDTMkMqXcOm6O4Pp/YuBTJS9rGJ1F/3M2ux+G1ZM
	tzxdyef3411nWGejLptO2WTp9vzuvy4Ewqba/oDoNvtAw/FNGn+Gbp9juU9u0rxamWs8
	Qt0iimbXYnyU8wJ1LZ+p3oqJZBqrE3WBrfOxaqOkFdVBMVb/Kp3pEUMarwpwIQ1BeW38
	IU5PzV00pK6mIqeB6sEAec7yAPalgEuLNjc8IUyCw0e9xUMoa+hb07yXqFEqibi3PL6q	AQcw==
authentication-results: spf=pass (sender IP is 209.85.218.47)
	smtp.mailfrom=gmail.com; mit.edu; dkim=pass (signature was verified)
	header.d=gmail.com; mit.edu;	dmarc=pass action=none header.from=gmail.com; 
errors-to: piclist-bounces@mit.edu
list-id: "Microcontroller discussion list - Public." <piclist.mit.edu>
list-post: <mailto:piclist@mit.edu>
x-beenthere: piclist@mit.edu
x-mailman-version: 2.1.6
x-received: by 2002:a17:906:5f96:: with SMTP id
	a22mr10013345eju.335.1600858493750; 	Wed, 23 Sep 2020 03:54:53 -0700 (PDT)
x-topics: [AVR]
x-content-filtered-by: Mailman/MimeDel 2.1.6
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0

On Tue, 22 Sep 2020 at 10:52, sergio <smplx@allotrope.net> wrote:

> Hi Russel,
> I may not be as highly competent as your friend but ESA considered me
> competent enough to work on several components of their Hermes poject.
>


> I'll defer to both of you :-)


Ken has sent me four related emails subsequently.

I'll paste them below - possibly lightly edited.

__________________

Yes  - when it comes to arithmetic algorithms there's quite a depth of
historical knowledge to draw on.  For instance, the "modern" CORDIC
algorithms date from 1956  - but were based on earlier work going as far
back as the early 1600's.

Professor Chu made no claim of originality so I can only assume that "his"
square root algorithm was reasonably well known at the time he wrote his
book.  Unfortunately he provided no reference as to its origins.

Someone like Gary J Tee would probably know the history of such things (if
he's still with us).

The ENIAC used the "sum of odd's" algorithm.  It's one of my favourite
arithmetic algorithms as it is so easy to prove to derive/prove.  Get a pen
and paper and draw a small square in the lower left corner.  Now enlarge
the square by drawing one of equal size above, one to the right, and one to
fill in the corner.  You now have four squares.  Keep enlarging the square
in the same manner  - two squares above, two to the right, and one to fill
in the corner (giving 9 squares) and so on for 16, 25... squares.  In every
case you create a perfect square by adding the next highest odd number of
squares  - and the number of squares vertically or horizontally is the
square root of the total number of squares.

Some of the older digital calculators in my collection include a square
root function.  It would be interesting to know the underlying algorithms.

My interest in fast integer square root algorithms came about in the early
80's when I wrote a graphics library in Z80 assembler to support the NEC
uPD7220 graphics processor in the CPM-based Epson QX-10 computer.  The 7220
was arguably the first dedicated GPU and included Bresenham's line and
circle drawing algorithms in hardware.  By the standards of its day it was
blazingly fast.  I still have the 7220 device from that machine  - a
beautiful object in white ceramic:

https://en.wikipedia.org/wiki/NEC_%C2%B5PD7220

Over the subsequent years I have coded (and exhaustively tested) examples
of most of the (many) square root algorithms.

Your colleague may also like to check out a square root algorithm by Ken
Turkowski published in the Apple Technical Report No 96 titled "Fixed Point
Square Root" dated 2 October 1994:


https://citeseerx.ist.psu.edu/viewdoc/download?doi=3D10.1.1.178.3957&rep=3D=
rep1&type=3Dpdf


There was also quite a good writeup on integer square root algorithms in
one of the Dr Dobb's journals in (I think) the late 80's, and several more
articles on the subject over subsequent years.

_______________________________________________

*If you want the code for this please advise and I'll check that Ken is
happy for me to supply it. I imagine he will be.*

Attached is a version of the Chu square root algorithm for the Intel x86
architecture.

This version returns a rounded 16-bit result for a 16-bit integer argument.

The test harness is written in Pascal but the algorithm is coded in x86
assembler.

The date stamp on the file suggests that I coded it in 1997.  I had
previously coded it for Z80, M6800, 8051, and M68000 architectures.

_______________________________________________

This is a book by Jack Crenshaw that I have found useful from time to time.

http://fmipa.umri.ac.id/wp-content/uploads/2016/03/Jack-W.-Crenshaw-Math-to=
olkit-for-real-time-programming.9781929629091.35924.pdf

It doesn't necessarily give the best (fastest and/or most accurate)
available algorithm in every case but it generally gives you a good start
for something that works.
_______________________________________________

Another (largely forgotten) square root algorithm was described (in German)
by August Toepler in the 1865:

http://rechnerlexikon.de/files/PolytJournal1866-Toepler.pdf

It uses attributes of both the "sum-of-odds" and the iterative
"high-school" digit-pairing algorithms.

Here is a reasonably straightforward example of its application.

http://user.mendelu.cz/marik/mechmat/sqrt-toepler/

This is the only square root algorithm that I am aware of that I have (so
far) not coded.  Actually that's not quite true  - there is also a
"Japanese" algorithm which I have been told about but have not
researched. From what little I do know I think it is a variant of Toeplers
method.

Here is a bit of background on Toepler (although the article omits mention
of his square root algorithm).

https://en.wikipedia.org/wiki/August_Toepler


_______________________________________________







>
>
--=20
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist
.