> Hi Russell,
>
> I think I understand what the problem is now. I believe you are trying to show
> that my algorithm was invented by others before me and you have taken umbrage at
> my copyright notice. I do not doubt that there are/were other people with far
> superior maths skills than mine and that they have probably already invented 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 (which
> 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 code as
> a simple way to show how efficiently a square root could be calculated in the
> real world without the need to resort to multiply, divide and even some more
> complex maths. This was done at my expense by giving away knowledge that had
> 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 taking
> 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 own
> projects. I have not tried to patent my algorithm just copyright my presentation
> of it.
>
> Furthermore, it is all well and good seeing a complex mathematical description
> of the algorithm presented in a book but books have been known to have printing
> 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 being
> 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 provided
> will produce integer square roots for all integers between 0 and 65535
> inclusive. It will compare these with the square roots produced by the standard
> C maths library and show any errors by pre-pending a "*" to the output (this 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 the
> 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
.....smplxRemoveMEallotrope.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:
> > ?
> > en.wikipedia.org/wiki/NEC_ÂµPD7220
> > ?
> > 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:
> > ?
> > ?citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.178.3957&rep=rep1&type=pdf???
> > ?
> > 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.
> > ?
> > 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:
> > ?
> > 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.?
> > ?
> > 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
> >
> > ?
> > ?
>
> --
>
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
>
http://mailman.mit.edu/mailman/listinfo/piclist