From: sergio <smplx@allotrope.net>
To: Microcontroller discussion list - Public. <piclist@mit.edu>
Sender: "piclist-bounces@mit.edu" <piclist-bounces@mit.edu>
Date: Wed, 23 Sep 2020 06:45:46 -0700
Subject: Re: [AVR] square on AVR
Thread-Topic: [AVR] square on AVR
Thread-Index: AdaRsra76ZQNRkxASCi/cweoNdLsmw==
Message-ID: <alpine.BSF.2.21.9999.2009231444520.1822@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: None (protection.outlook.com: allotrope.net does not designate
	permitted sender hosts)
dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=mitprod.onmicrosoft.com; s=selector2-mitprod-onmicrosoft-com;
	h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck;
	bh=7o1+oWqcmH3HOhmnBbDboO43XRnzz6eG2zznziVp1jU=;
	b=bf50/l86LbXPIv2wxNcPoSDVtuGIL0NWz2VJZ0GQVNgzhVRmsPWE+80RP41wofhFMyUO0bLPX018AGHat5qdjZW+kkfnsAhkkJI4bSPpvQgnFaGr5HjzX6QzI+ANtPDQsAAL7wcHRVxoKTAKkuvh86l0laiAaEy92tumntTsZIw=
authentication-results: spf=none (sender IP is 82.69.45.61)
	smtp.mailfrom=allotrope.net; mit.edu; dkim=none (message not signed)
	header.d=none; mit.edu; dmarc=none action=none header.from=allotrope.net;
user-agent: Alpine 2.21.9999 (BSF 287 2018-06-16)
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-topics: [AVR]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0


Hi Russell,

I think I understand what the problem is now. I believe you are trying to s=
how
that my algorithm was invented by others before me and you have taken umbra=
ge at
my copyright notice. I do not doubt that there are/were other people with f=
ar
superior maths skills than mine and that they have probably already invente=
d the
algorithm that I have presented. However, despite my repeated searches over=
 the
years, I have not found it anywhere on the net. The closest I have come (wh=
ich
was after I presented my code) was by Martin Guy. The book you mentioned by
Yaohan Chu does pre-date my algorithm and does describe it mathematically. =
It
does not however present it in a simple ready to run form.

I could see the way this thread was heading and I decided to present my cod=
e as
a simple way to show how efficiently a square root could be calculated in t=
he
real world without the need to resort to multiply, divide and even some mor=
e
complex maths. This was done at my expense by giving away knowledge that ha=
d
cost me money to acquire. The copyright notice is an attempt to hinder the
copy/paste brigade - those people that build their websites by simply takin=
g
other people's work and presenting it as their own. It is my hope that real
coders on the piclist will see my algorithm and re-implement it in their ow=
n
projects. I have not tried to patent my algorithm just copyright my present=
ation
of it.

Furthermore, it is all well and good seeing a complex mathematical descript=
ion
of the algorithm presented in a book but books have been known to have prin=
ting
errors and if any are present then the reader would be presented with a lot=
 of
work to try to understand why their implementation did not work. However be=
ing
presented with the algorithm in an executable form it is trivial to verify =
that
it works correctly for ALL input (OK you need to compile it but anyone that=
 can
program an MCU is surely capable of a simple compile). The code I have prov=
ided
will produce integer square roots for all integers between 0 and 65535
inclusive. It will compare these with the square roots produced by the stan=
dard
C maths library and show any errors by pre-pending a "*" to the output (thi=
s can
quickly be found using grep).

BTW the code presented by Martin Guy uses multiply and needs the top bit of=
 the
integer for the sign. For a 16 bit number this would reduce the range of th=
e
input to 0..32767 (15 bits).

FRIENDLY Regards
Sergio Masci


On Wed, 23 Sep 2020, RussellMc wrote:

> 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 poje=
ct.
>=20
> ?
>       I'll defer to both of you :-)
>=20
> ?
> Ken has sent me four related emails subsequently.
>=20
> I'll paste them below - possibly lightly edited.
>=20
> __________________
>=20
> Yes? - when it comes to arithmetic algorithms there's quite a depth of
> historical knowledge to draw on.? For instance, the "modern" CORDIC algor=
ithms
> 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.? Ke=
ep
> 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 square=
s
> vertically or horizontally is the square root of the total number of squa=
res.
> ?
> Some of the older digital calculators in my collection include a square r=
oot
> 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 stand=
ards
> 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 Poi=
nt
> 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 more
> articles on the subject?over subsequent years.??
>=20
> _______________________________________________
>=20
> If you want the code for this please advise and I'll check that Ken is ha=
ppy
> for me to supply it. I imagine he will be.
>=20
> 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 previ=
ously
> coded it for Z80, M6800, 8051, and M68000 architectures.
>=20
> _______________________________________________
>=20
> 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) avail=
able
> algorithm in every case but it?generally gives you a good start for somet=
hing
> that works.?
> _______________________________________________
>=20
> Another (largely forgotten) square root algorithm was described (in Germa=
n) 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-scho=
ol"
> 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 mentio=
n
> of?his square root algorithm).
> ?
> https://en.wikipedia.org/wiki/August_Toepler
>=20
>=20
> _______________________________________________
>=20
>=20
>=20
> ?
>=20
> ?
>=20
>=20
>
--=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
.