> On Sat, 12 Sep 2020 00:48:16 +0000
> madscientistatlarge .....madscientistatlargeKILLspam.....protonmail.com wrote:
>
> > Sorry, that should be square root (time for a nap). It would be on
> > an atmega2560 AVR, running at 16MHZ.
>
> 16-bit sounds easily within reason to me. My go-to integer square root
> implementation is a binary search: “for each bit from N−1 downto 0, try
> turning it on, square that number, if the square is ≤ the input then
> keep the bit, otherwise clear it”. There may be better ones, but I’ve
> found this to be something that can be implemented in an extremely
> tight loop, in assembly if necessary, quite easily (or unrolled if you
> want to absolutely max out performance). It looks like the 2560 has a
> hardware multiplier—I assume probably 8×8→16—which should make this
> doable in just a few dozen cycles, out of a budget of 40,000!
>
> 20-bit, you’d just have to synthesize the larger multiplication
> operation. It is also possible to rip the SQRT into pieces and do some
> subtractions so you don’t have to deal with all 20 bits on every cycle.
>
> Doing it in C, YMMV, especially if you do larger-than-CPU-native-size
> multiplies. Assembly should be fine though.
>
> This is all assuming you want a floored integer output and don’t care
> about the fractional part!
>
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> Christopher Head
>
> -----------------
>
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> I found search results eventually on the web.  The successive
> approximation looks pretty fast, if done in assembler which shouldn't be
> too hard for me.  I've manually compiled small pieces of code for a 6502 in
> a apple][, and a z80, had a course on motorola 68K assembler and had no
> problem with a 20 page program (based on a 2 page pascal program we were
> told to redo in assembler).  In the 68K program I wrote code for longer
> multiplication by spliing the numbers, doing 4 multiplies and adding.  On
> the 68k code I only had one error, off by one which I thought I might have,
> and found a bug in the compiler for one of the many compare functions, I
> used another one that reacted to the flags in the same way to get around
> it. People thought I was crazy typing in comments before I had it working.
> That was a couple of decades ago but I think I can learn a new assembler
> for such a small piece of code pretty easily, Especially since I found
> examples on the web. Risc instruction set would likely be a bit harder for
> me but should be doable by me.  I also calculated 40,000 as total available
> cycles, obviously there's other code but it's simple in this case so C
> should be fast enough outside the square root calculation.
>
> This is the first project I've done in awhile but I've had plenty of time
> to tweak the design of the other hardware.  I'd like to do it this way to
> cut EMI, I'll hopefully be doing some ham radio before long so I'd like to
> keep the bench somewhat quite (Yes, I know I spelled it wrong, having
> trouble finding the correct spelling, I am terrible at spelling).  Not
> putting a high power pwm signal on external unshielded cables should help
> with that, as well as helping with whatever else I'm working on.  There
> will be 4 of these signals, at up to 240 Watts each so obviously it could
> really radiate!  Each channel will be adjusted 100 times per second. I'm
> designing myself a "universal" soldering/desolering station that I can use
> with any 4 irons by putting a new connector on them with a serial eeprom in
> the connector to tell the station what the specs are for a particular
> iron.  This will be fun.  I will write it all up and ideally put it on the
> web.
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Friday, September 11, 2020 8:10 PM, Christopher Head <cheadspam_OUTchead.ca>
> wrote:
>
> > On Sat, 12 Sep 2020 00:48:16 +0000
> > madscientistatlarge @spam@madscientistatlargeKILLspamprotonmail.com wrote:
> >
> > > Sorry, that should be square root (time for a nap). It would be on
> > > an atmega2560 AVR, running at 16MHZ.
> >
> > 16-bit sounds easily within reason to me. My go-to integer square root
> > implementation is a binary search: “for each bit from N−1 downto 0, try
> > turning it on, square that number, if the square is ≤ the input then
> > keep the bit, otherwise clear it”. There may be better ones, but I’ve
> > found this to be something that can be implemented in an extremely
> > tight loop, in assembly if necessary, quite easily (or unrolled if you
> > want to absolutely max out performance). It looks like the 2560 has a
> > hardware multiplier—I assume probably 8×8→16—which should make this
> > doable in just a few dozen cycles, out of a budget of 40,000!
> >
> > 20-bit, you’d just have to synthesize the larger multiplication
> > operation. It is also possible to rip the SQRT into pieces and do some
> > subtractions so you don’t have to deal with all 20 bits on every cycle.
> >
> > Doing it in C, YMMV, especially if you do larger-than-CPU-native-size
> > multiplies. Assembly should be fine though.
> >
> > This is all assuming you want a floored integer output and don’t care
> > about the fractional part!
> >
> >
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> >
> > Christopher Head
> >
> > -----------------
> >
> > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > View/change your membership options at
> > http://mailman.mit.edu/mailman/listinfo/piclist
>
>
>
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>

> How fast is  the input changing? if only slowly wrt the sampling rate you
> made be able to speed things up by using an estimate based on the current
> value. 400 times per second with a 16MHz clock sounds quite do-able to me,
> unless the processor is doing a lot of other stuff as well.
> if you have spare memory, you can speed things up with a lookup table to
> get you close also.
>
> Richard P
>
> On Sat, 12 Sep 2020 at 14:49, madscientistatlarge <
> RemoveMEmadscientistatlargeTakeThisOuTprotonmail.com> wrote:
>
> > I found search results eventually on the web.  The successive
> > approximation looks pretty fast, if done in assembler which shouldn't be
> > too hard for me.  I've manually compiled small pieces of code for a 6502
> in
> > a apple][, and a z80, had a course on motorola 68K assembler and had no
> > problem with a 20 page program (based on a 2 page pascal program we were
> > told to redo in assembler).  In the 68K program I wrote code for longer
> > multiplication by spliing the numbers, doing 4 multiplies and adding.  On
> > the 68k code I only had one error, off by one which I thought I might
> have,
> > and found a bug in the compiler for one of the many compare functions, I
> > used another one that reacted to the flags in the same way to get around
> > it. People thought I was crazy typing in comments before I had it
> working.
> > That was a couple of decades ago but I think I can learn a new assembler
> > for such a small piece of code pretty easily, Especially since I found
> > examples on the web. Risc instruction set would likely be a bit harder
> for
> > me but should be doable by me.  I also calculated 40,000 as total
> available
> > cycles, obviously there's other code but it's simple in this case so C
> > should be fast enough outside the square root calculation.
> >
> > This is the first project I've done in awhile but I've had plenty of time
> > to tweak the design of the other hardware.  I'd like to do it this way to
> > cut EMI, I'll hopefully be doing some ham radio before long so I'd like
> to
> > keep the bench somewhat quite (Yes, I know I spelled it wrong, having
> > trouble finding the correct spelling, I am terrible at spelling).  Not
> > putting a high power pwm signal on external unshielded cables should help
> > with that, as well as helping with whatever else I'm working on.  There
> > will be 4 of these signals, at up to 240 Watts each so obviously it could
> > really radiate!  Each channel will be adjusted 100 times per second. I'm
> > designing myself a "universal" soldering/desolering station that I can
> use
> > with any 4 irons by putting a new connector on them with a serial eeprom
> in
> > the connector to tell the station what the specs are for a particular
> > iron.  This will be fun.  I will write it all up and ideally put it on
> the
> > web.
> >
> >
> > Sent with ProtonMail Secure Email.
> >
> > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > On Friday, September 11, 2020 8:10 PM, Christopher Head <spamBeGonecheadspamBeGonechead.ca>
> > wrote:
> >
> > > On Sat, 12 Sep 2020 00:48:16 +0000
> > > madscientistatlarge TakeThisOuTmadscientistatlargeEraseMEspam_OUTprotonmail.com wrote:
> > >
> > > > Sorry, that should be square root (time for a nap). It would be on
> > > > an atmega2560 AVR, running at 16MHZ.
> > >
> > > 16-bit sounds easily within reason to me. My go-to integer square root
> > > implementation is a binary search: “for each bit from N−1 downto 0, try
> > > turning it on, square that number, if the square is ≤ the input then
> > > keep the bit, otherwise clear it”. There may be better ones, but I’ve
> > > found this to be something that can be implemented in an extremely
> > > tight loop, in assembly if necessary, quite easily (or unrolled if you
> > > want to absolutely max out performance). It looks like the 2560 has a
> > > hardware multiplier—I assume probably 8×8→16—which should make this
> > > doable in just a few dozen cycles, out of a budget of 40,000!
> > >
> > > 20-bit, you’d just have to synthesize the larger multiplication
> > > operation. It is also possible to rip the SQRT into pieces and do some
> > > subtractions so you don’t have to deal with all 20 bits on every cycle.
> > >
> > > Doing it in C, YMMV, especially if you do larger-than-CPU-native-size
> > > multiplies. Assembly should be fine though.
> > >
> > > This is all assuming you want a floored integer output and don’t care
> > > about the fractional part!
> > >
> > >
> >
> -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> > >
> > > Christopher Head
> > >
> > > -----------------
> > >
> > > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > > View/change your membership options at
> > > mailman.mit.edu/mailman/listinfo/piclist
> >
> >
> >
> > --
> > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > View/change your membership options at
> > mailman.mit.edu/mailman/listinfo/piclist
> >
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>

> How fast is the input changing? if only slowly wrt the sampling rate you
> made be able to speed things up by using an estimate based on the current
> value. 400 times per second with a 16MHz clock sounds quite do-able to me,
> unless the processor is doing a lot of other stuff as well.
> if you have spare memory, you can speed things up with a lookup table to
> get you close also.
>
> Richard P
>
> On Sat, 12 Sep 2020 at 14:49, madscientistatlarge <
> madscientistatlargeEraseME.....protonmail.com> wrote:
>
> > I found search results eventually on the web. The successive
> > approximation looks pretty fast, if done in assembler which shouldn't be
> > too hard for me. I've manually compiled small pieces of code for a 6502 in
> > a apple][, and a z80, had a course on motorola 68K assembler and had no
> > problem with a 20 page program (based on a 2 page pascal program we were
> > told to redo in assembler). In the 68K program I wrote code for longer
> > multiplication by spliing the numbers, doing 4 multiplies and adding. On
> > the 68k code I only had one error, off by one which I thought I might have,
> > and found a bug in the compiler for one of the many compare functions, I
> > used another one that reacted to the flags in the same way to get around
> > it. People thought I was crazy typing in comments before I had it working.
> > That was a couple of decades ago but I think I can learn a new assembler
> > for such a small piece of code pretty easily, Especially since I found
> > examples on the web. Risc instruction set would likely be a bit harder for
> > me but should be doable by me. I also calculated 40,000 as total available
> > cycles, obviously there's other code but it's simple in this case so C
> > should be fast enough outside the square root calculation.
> > This is the first project I've done in awhile but I've had plenty of time
> > to tweak the design of the other hardware. I'd like to do it this way to
> > cut EMI, I'll hopefully be doing some ham radio before long so I'd like to
> > keep the bench somewhat quite (Yes, I know I spelled it wrong, having
> > trouble finding the correct spelling, I am terrible at spelling). Not
> > putting a high power pwm signal on external unshielded cables should help
> > with that, as well as helping with whatever else I'm working on. There
> > will be 4 of these signals, at up to 240 Watts each so obviously it could
> > really radiate! Each channel will be adjusted 100 times per second. I'm
> > designing myself a "universal" soldering/desolering station that I can use
> > with any 4 irons by putting a new connector on them with a serial eeprom in
> > the connector to tell the station what the specs are for a particular
> > iron. This will be fun. I will write it all up and ideally put it on the
> > web.
> > Sent with ProtonMail Secure Email.
> > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > On Friday, September 11, 2020 8:10 PM, Christopher Head EraseMEcheadchead.ca
> > wrote:
> >
> > > On Sat, 12 Sep 2020 00:48:16 +0000
> > > madscientistatlarge RemoveMEmadscientistatlargeEraseMEEraseMEprotonmail.com wrote:
> > >
> > > > Sorry, that should be square root (time for a nap). It would be on
> > > > an atmega2560 AVR, running at 16MHZ.
> > >
> > > 16-bit sounds easily within reason to me. My go-to integer square root
> > > implementation is a binary search: “for each bit from N−1 downto 0, try
> > > turning it on, square that number, if the square is ≤ the input then
> > > keep the bit, otherwise clear it”. There may be better ones, but I’ve
> > > found this to be something that can be implemented in an extremely
> > > tight loop, in assembly if necessary, quite easily (or unrolled if you
> > > want to absolutely max out performance). It looks like the 2560 has a
> > > hardware multiplier—I assume probably 8×8→16—which should make this
> > > doable in just a few dozen cycles, out of a budget of 40,000!
> > > 20-bit, you’d just have to synthesize the larger multiplication
> > > operation. It is also possible to rip the SQRT into pieces and do some
> > > subtractions so you don’t have to deal with all 20 bits on every cycle.
> > > Doing it in C, YMMV, especially if you do larger-than-CPU-native-size
> > > multiplies. Assembly should be fine though.
> > > This is all assuming you want a floored integer output and don’t care
> > > about the fractional part!
> >
> > > Christopher Head
> > >
> > > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > > View/change your membership options at
> > > mailman.mit.edu/mailman/listinfo/piclist
> >
> > --
> > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > View/change your membership options at
> > http://mailman.mit.edu/mailman/listinfo/piclist
>
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> If the power required for your setpoint doesn't vary too much then the v^2
> nonlinearity can be treated as a linear function of slope 2v and you don't
> even need to perform a square root for your PID loop.
>
> On Sat, Sep 12, 2020, 2:38 AM Richard Prosser <RemoveMErhprosserTakeThisOuTspamgmail.com wrote:
>
> > How fast is the input changing? if only slowly wrt the sampling rate you
> > made be able to speed things up by using an estimate based on the current
> > value. 400 times per second with a 16MHz clock sounds quite do-able to me,
> > unless the processor is doing a lot of other stuff as well.
> > if you have spare memory, you can speed things up with a lookup table to
> > get you close also.
> > Richard P
> > On Sat, 12 Sep 2020 at 14:49, madscientistatlarge <
> > EraseMEmadscientistatlargespamspamBeGoneprotonmail.com> wrote:
> >
> > > I found search results eventually on the web. The successive
> > > approximation looks pretty fast, if done in assembler which shouldn't be
> > > too hard for me. I've manually compiled small pieces of code for a 6502
> > > in
> > > a apple][, and a z80, had a course on motorola 68K assembler and had no
> > > problem with a 20 page program (based on a 2 page pascal program we were
> > > told to redo in assembler). In the 68K program I wrote code for longer
> > > multiplication by spliing the numbers, doing 4 multiplies and adding. On
> > > the 68k code I only had one error, off by one which I thought I might
> > > have,
> > > and found a bug in the compiler for one of the many compare functions, I
> > > used another one that reacted to the flags in the same way to get around
> > > it. People thought I was crazy typing in comments before I had it
> > > working.
> > > That was a couple of decades ago but I think I can learn a new assembler
> > > for such a small piece of code pretty easily, Especially since I found
> > > examples on the web. Risc instruction set would likely be a bit harder
> > > for
> > > me but should be doable by me. I also calculated 40,000 as total
> > > available
> > > cycles, obviously there's other code but it's simple in this case so C
> > > should be fast enough outside the square root calculation.
> > > This is the first project I've done in awhile but I've had plenty of time
> > > to tweak the design of the other hardware. I'd like to do it this way to
> > > cut EMI, I'll hopefully be doing some ham radio before long so I'd like
> > > to
> > > keep the bench somewhat quite (Yes, I know I spelled it wrong, having
> > > trouble finding the correct spelling, I am terrible at spelling). Not
> > > putting a high power pwm signal on external unshielded cables should help
> > > with that, as well as helping with whatever else I'm working on. There
> > > will be 4 of these signals, at up to 240 Watts each so obviously it could
> > > really radiate! Each channel will be adjusted 100 times per second. I'm
> > > designing myself a "universal" soldering/desolering station that I can
> > > use
> > > with any 4 irons by putting a new connector on them with a serial eeprom
> > > in
> > > the connector to tell the station what the specs are for a particular
> > > iron. This will be fun. I will write it all up and ideally put it on
> > > the
> > > web.
> > > Sent with ProtonMail Secure Email.
> > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> > > On Friday, September 11, 2020 8:10 PM, Christopher Head RemoveMEcheadKILLspamchead.ca
> > > wrote:
> > >
> > > > On Sat, 12 Sep 2020 00:48:16 +0000
> > > > madscientistatlarge madscientistatlargeSTOPspamspam_OUTprotonmail.com wrote:
> > > >
> > > > > Sorry, that should be square root (time for a nap). It would be on
> > > > > an atmega2560 AVR, running at 16MHZ.
> > > >
> > > > 16-bit sounds easily within reason to me. My go-to integer square root
> > > > implementation is a binary search: “for each bit from N−1 downto 0, try
> > > > turning it on, square that number, if the square is ≤ the input then
> > > > keep the bit, otherwise clear it”. There may be better ones, but I’ve
> > > > found this to be something that can be implemented in an extremely
> > > > tight loop, in assembly if necessary, quite easily (or unrolled if you
> > > > want to absolutely max out performance). It looks like the 2560 has a
> > > > hardware multiplier—I assume probably 8×8→16—which should make this
> > > > doable in just a few dozen cycles, out of a budget of 40,000!
> > > > 20-bit, you’d just have to synthesize the larger multiplication
> > > > operation. It is also possible to rip the SQRT into pieces and do some
> > > > subtractions so you don’t have to deal with all 20 bits on every cycle.
> > > > Doing it in C, YMMV, especially if you do larger-than-CPU-native-size
> > > > multiplies. Assembly should be fine though.
> > > > This is all assuming you want a floored integer output and don’t care
> > > > about the fractional part!
> >
> > > > Christopher Head
> > > >
> > > > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > > > View/change your membership options at
> > > > mailman.mit.edu/mailman/listinfo/piclist
> > >
> > > --
> > > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > > View/change your membership options at
> > > mailman.mit.edu/mailman/listinfo/piclist
> >
> > --
> > http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> > View/change your membership options at
> > http://mailman.mit.edu/mailman/listinfo/piclist
>
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> You could eliminate the DAC and emulate the SEPIC converter in
> software with the AVR.
>
>     Just to complicate things a little...
>
>     Regards,
>     Mark Jordan
>
> On 12-Sep-20 05:44, madscientistatlarge wrote:
>
> > A DAC will control a SEPIC dc-dc converter, and I'll use external ADC to measure the thermocouple voltage after amplification. I'll use the AVR ADC to monitor currents and voltages for fault indication (i.e. open heater)
>
> --
>
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> > I could use the last value as a starting value for the square root.
> > Obviously the iron temperature won't be changing terribly fast, so
> > that's a good suggestion.
>
> Indeed, a single iteration of Newton-Raphson should be all you need.
>
> In the case of square root, all you need to do is divide the current input
> by the previous sqaure root, and then average that result with the previous
> square root to get the new square root.
>
> The "rule of thumb" with this method is that the number of correct bits
> in the answer is basically doubled on each iteration. So as long as the
> temperature hasn't changed enough to invalidate half of the bits in the
> current answer, you're good to go.
>
> Even at startup, when the "previous answer" is simply taken as some fixed
> nonzero value (e.g., 2), this will converge within a few cycles to the
> correct answer.
>
> -- Dave Tweed
>
> --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> You can find one in source code of DOOM.
> which was running on 66MHz x86, supply a 3D battle field.
>
>
> On Sat, 12 Sep 2020 00:48:16 +0000
> madscientistatlarge <EraseMEmadscientistatlargeEraseMEprotonmail.com> wrote:
>
>> Sorry, that should be square root (time for a nap).  It would be on
>> an atmega2560 AVR, running at 16MHZ.
>>
>>
>> Sent with ProtonMail Secure Email.
>>
>>
>>
>> --
>> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
>> View/change your membership options at
>> http://mailman.mit.edu/mailman/listinfo/piclist
>

> > On Sep 18, 2020, at 6:24 AM, RussellMc spamBeGoneapptechnzKILLspamgmail.com wrote:
> > A friend, who is a highly competent coder says:
> > I have long used a fast integer square root algorithm which is very similar
> > to binary division.
> > I came across it in a book titled Digital Computer Design Fundamentals by
> > Yaohan Chu published by McGraw Hill in 1962. It predates ISBN's but has a
> > Library of Congress Catalog card number 62-11193. The author was a
> > professor in the Department of Electrical Engineering at the University of
> > Maryland. The square root algorithm is described starting on page 43
> > (section 1-10).
> > I still have the book - it was a "discard" from the U of A Engineering
> > Library when I was doing my Masters. It's a fascinating read covering the
> > technologies of the time.
>
> Looks like a scanned copy of the book is available here:https://babel.hathitrust.org/cgi/pt?id=uc1.$b720948&view=1up&seq=8
>
> Thanks for sharing, Russell. Very interesting reading. This is going to cause me to waste a few hours, I can tell :)
>
> Chris Smolinski
> Black Cat Systems
> Westminster, MD USA
> https://www.blackcatsystems.com
>
>
> -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> A friend, who is a highly competent coder says:
>
> I have long used a fast integer square root algorithm which is very similar
> to binary division.
>
> I came across it in a book titled Digital Computer Design Fundamentals by
> Yaohan Chu published by McGraw Hill in 1962.  It predates ISBN's but has a
> Library of Congress Catalog card number 62-11193.   The author was a
> professor in the Department of Electrical Engineering at the University of
> Maryland.  The square root algorithm is described starting on page 43
> (section 1-10).
>
> I still have the book  - it was a "discard" from the U of A Engineering
> Library when I was doing my Masters.  It's a fascinating read covering the
> technologies of the time.
>
> Copies may be found here:
>
> Amazon $4.25
>
> https://www.amazon.com/Digital-Computer-Design-Fundamentals-Yaohan/dp/0070108005
>
> ABEbooks
>
> https://www.abebooks.com/servlet/SearchResults?sts=t&cm_sp=SearchF-_-home-_-Results&an=yaohan+chu&tn=digital+computer+design+fundamentals&kn=&isbn=
>
>
>
>    Russell
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist
>

> On Tue, 22 Sep 2020 at 10:52, sergio <TakeThisOuTsmplx.....TakeThisOuTallotrope.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:
> ?
> ?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
>
>
> _______________________________________________
>
>
>
> ?
>
> ?
>
>
>

> A friend, who is a highly competent coder says:
>
> I have long used a fast integer square root algorithm which is very similar
> to binary division.
>
> I came across it in a book titled Digital Computer Design Fundamentals by
> Yaohan Chu published by McGraw Hill in 1962.  It predates ISBN's but has a
> Library of Congress Catalog card number 62-11193.   The author was a
> professor in the Department of Electrical Engineering at the University of
> Maryland.  The square root algorithm is described starting on page 43
> (section 1-10).
>
> I still have the book  - it was a "discard" from the U of A Engineering
> Library when I was doing my Masters.  It's a fascinating read covering the
> technologies of the time.
>
> Copies may be found here:
>
> Amazon $4.25
>
> www.amazon.com/Digital-Computer-Design-Fundamentals-Yaohan/dp/0070108005
>
> ABEbooks
>
> www.abebooks.com/servlet/SearchResults?sts=t&cm_sp=SearchF-_-home-_-Results&an=yaohan+chu&tn=digital+computer+design+fundamentals&kn=&isbn=
>
>
>
>     Russell
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> 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

> On Wed, 23 Sep 2020, madscientistatlarge wrote:
>
> > If you freely provide information on an open email list you have just waived
> > any POTENTIAL copyright claims. A lawyer would be happy to confirm this.
> > Your' inability to find something on the web or in a library hardly proves
> > that it is "original" in any way. There are plenty of things I've found at
> > a college library that are totally lacking from the web. Further, not
> > finding it at X number of libraries hardly proves it's not out there!
>
> You seem to be confusing patents with copyrights. Disclosure can hinder
> getting a patent (e.g., on an algorithm), but Sergio is perfectly within
> his rights to assert his copyright on his specific implementation of the
> algorithm(s) -- i.e., the source code.
>
> -- Dave Tweed
>
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

>
>
> On Wed, 23 Sep 2020, madscientistatlarge wrote:
>
> > If you freely provide information on an open email list you have
> > just waived any POTENTIAL copyright claims.  A lawyer would be
> > happy to confirm this. Your' inability to find something on the web
> > or in a library hardly proves that it is "original" in any way.
> > There are plenty of things I've found at a college library that are
> > totally lacking from the web.  Further, not finding it at X number
> > of libraries hardly proves it's not out there!
>
> Actually the act of writing something, whether it is music, litriture
> or software acquires copyright when it is created by the author. You
> don't give it away by showing somebody.
>
> Furthermore I'm getting really tired of all this. Good luck in the
> future because I'm certainly not inclined to waste my time trying to
> help again.
>
> Regards
> Sergio Masci
> --
> http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
> View/change your membership options at
> http://mailman.mit.edu/mailman/listinfo/piclist

> ________    *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 (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=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.
>
>
> 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 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
>
>
> _______________________________________________
>
>
>
>
>
>
>
>>
>>