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: Thu, 24 Sep 2020 03:34:30 -0700
Subject: Re: [AVR] square on AVR
Thread-Topic: [AVR] square on AVR
Thread-Index: AdaSYEFuN9HpxKLSTnC8YLDFyjCJvQ==
Message-ID:
 <CACZQxzO=PSOrcGJ3X_G3xp9huaQCxOrGNP2RBiYT6yydKgdW2g@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>
	<CACZQxzM=K3RHkHwWXECG7u-Bu2MeqaooQ2irXbVEphfyuPdTfQ@mail.gmail.com>
In-Reply-To:
 <CACZQxzM=K3RHkHwWXECG7u-Bu2MeqaooQ2irXbVEphfyuPdTfQ@mail.gmail.com>
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.49 as permitted sender) receiver=protection.outlook.com;
	client-ip=209.85.218.49; helo=mail-ej1-f49.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=BKVM/s+wjhd49HGX1yOBiPQQHlHSQKCAjlU9OlOdYMg=;
	b=EtRRMZo9HC73OOw407sTu17t9lvWrHVjyuJpzxo4wPi/V6WYtuOB70/HwpKImDTDYv
	/BLQZs9i+1ZmHUUd9RGSICs0VezYcoF57SycWAPQC7vrHVS2C6T8IOaSoMfOj0AvscVA
	c/c1S+80kDGRqZzOO1CG51AuFx+MqbK/suEhmQArZFFk52vZFODCrTcJp9XpKagYN2oX
	Qsq4WmXMqftn8h87Kr360bemZeteTg7iY+bmIyQVWgUXKlRjdzUiavbB6WwBIcw3trhF
	yOsQldKcPHpJ0dPRtnKqGwY14PuDjIvq8Diq2hmp0HuAQ9JBax+zepOVUE22cDFKkc9k	GCAA==
authentication-results: spf=pass (sender IP is 209.85.218.49)
	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:33ca:: with SMTP id
	w10mr306514eja.438.1600943708104; 	Thu, 24 Sep 2020 03:35:08 -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

More useful (hopefully) material from Ken:

The method I have seen referred to as the "Japanese" method is as follows:

    given that you want the square root of value n

    set variable x to 5n (the multiplication can be done "cheaply" via 3
add's using a temporary variable)
    set variable r to 5

    repeat as required:

        if x >=3D r
            x =3D x - r
            r =3D r + 10

        else
            append two 0's to lsd end of x (i.e. multiply x by 100)
            insert a 0 into r to the left of least significant digit

For each pass of the loop you get one further least significant digit for
variable r and its value approaches the square root of n with increasing
accuracy.

Note that the least significant digit of r is always 5.

I haven't studied it too closely (nor have I coded it) but my feeling is
that the algorithm depends on the fact that for any number in the range 0
to 100, the square root is in the range 0 to 10.  I'm not sure if there's
any way to know when n is an exact square (so that you can bail out of the
loop as soon as the last non-zero digit is generated for r).

The initial multiplication of n by 5 seems to be a hallmark of this
algorithm.  I have seen that for other square root algorithms not
identified as the "Japanese" method, and my suspicion is that they are in
fact the same algorithm going by a different name.

Obviously this algorithm is based on a decimal (say BCD) representation.
It's not clear to me how a binary version would work (nor indeed if it is
even possible).



> ________    *OLDER BELOW HERE - INCLUDED FOR COMPLETENESS  *__________
>
> 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 (i=
f
> 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 p=
en
> 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 squar=
e
> in the same manner  - two squares above, two to the right, and one to fil=
l
> in the corner (giving 9 squares) and so on for 16, 25... squares.  In eve=
ry
> 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 earl=
y
> 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 72=
20
> was arguably the first dedicated GPU and included Bresenham's line and
> circle drawing algorithms in hardware.  By the standards of its day it wa=
s
> 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=
=3Drep1&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 mor=
e
> 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 argumen=
t.
>
> 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 tim=
e.
>
>
> http://fmipa.umri.ac.id/wp-content/uploads/2016/03/Jack-W.-Crenshaw-Math-=
toolkit-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 Toepler=
s
> method.
>
> Here is a bit of background on Toepler (although the article omits mentio=
n
> 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
.