Searching \ for '[AVR] square on AVR' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=square+avr
Search entire site for: 'square on AVR'.

Exact match. Not showing close matches.
PICList Thread
'[AVR] square on AVR'
2020\09\08@074553 by Chris Smolinski

flavicon
face

> On Sep 18, 2020, at 6:24 AM, RussellMc <spam_OUTapptechnzTakeThisOuTspamgmail.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
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\11@204835 by madscientistatlarge n/a

flavicon
face
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
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\11@221018 by Christopher Head

flavicon
face
part 1 1359 bytes content-type:text/plain; charset="utf-8" (decoded base64)

On Sat, 12 Sep 2020 00:48:16 +0000
madscientistatlarge <.....madscientistatlargeKILLspamspam@spam@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

part 2 197 bytes content-type:text/plain; name="ATT00001.txt"
(decoded base64)

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\11@224702 by madscientistatlarge n/a

flavicon
face

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 <cheadspamKILLspamchead.ca> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@023750 by Richard Prosser

picon face

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 <
EraseMEmadscientistatlargespam_OUTspamTakeThisOuTprotonmail.com> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@032915 by Sean Breheny

face picon face

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 <KILLspamrhprosserKILLspamspamgmail.com wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@044413 by madscientistatlarge n/a

flavicon
face

I'm using an overly conservative time constant of 0.1 seconds.  Most of the other microprocessor load will be the PID routine.  If necessary I'll use the lookup table.  It will also be sampling temperature 100 times/S on 4 channels.  I'll also have to convert thermocouple voltage to temperature, I'll use a lookup table with linear interpolation for that most likely.  I'm sure I'll have plenty of memory to spare.  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.  Binary search for Square root after that, the higher value bits should not change very ocasionally.

It will also be checking for button presses, decoding rotary encoder, and displaying on an LCD module.  I'm using schmitt trigers with 2 resisters and a cap to debounce as it makes life simpler and the capacitor discharge current when the switch closes through a small resistor should avoid dry switching issues, same method for the rotary encoders. The capacitor will charge through the discharge resistor and a charge resistor, the recharge time will be long enough that the scmitt trigger only outputs one transition.

I won't be building the whole thing till next month, fixed income and I'll also be laying out a couple of boards.  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)  I have some nice beefy current sense resistors I'll amplify the voltage for the current measurement (5 milliohm) on the low side, depending on deals I can find I may use other resistors, I'll have to use a different value of current sense resistor for the switching controller (that'll prevent problems if the heater shorts some how.  I'll be prototyping a single channel on the bench for circuit verification/debugging.  During testing I'll use an AVR output to monitor the idle time and make sure I have enough headroom (i.e. I'll monitor that pin with my scope).

Working on this has made my brain happy, I like complexity, and steep learning curves.  I'll probably put the desin out as a torrent until I can get a Web page up (still have to get a domain), fortunately I know someone who's does websites professionally who can help me with any problems/confusion about HTML etc.  I'll probably run the site on a raspberry pi.  Fortunately I'm blessed with gigabit symetric internet.  I'll actually be using an Arduino board, if necessary I can use another compiler as I do have a JTAG tool I could program it with.

Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, September 12, 2020 12:51 AM, Richard Prosser <RemoveMErhprosserspamTakeThisOuTgmail.com> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@045539 by madscientistatlarge n/a

flavicon
face

Another great suggestion, I'll try that when I'm prototyping.

I do have a tendency to over engineer stuff, My last electronics job was for a company that made an absolute gravimeter that measured local gravity to 13 significant figures, sensitive enough to detect an elevation change of about 1/8 inch or be driven crazy if there's a floor about where it's setup with people moving.  To make it any more precise would actually require knowing the air pressure at about 100 altitudes.  It had to be compensated for the moon and tides even when inland.  We sold them for about $500K.  That was a very fun job, I got to work on high vacuum chambers and we used a rubidium oscillator for the time measurement and an iodine absorption locked laser.  They trained me in several things for backup, and because I often had good suggestions.  I'm an all around science geek.


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, September 12, 2020 1:28 AM, Sean Breheny <RemoveMEshb7spam_OUTspamKILLspamcornell.edu> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@082833 by enkitec

picon face


    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
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@084724 by madscientistatlarge n/a

flavicon
face

That had occured to me, but the switching frequency would be low and require large capacitors and inductors.  Mine will run the switcher at 500KHZ which makes the power supply parts smaller.  Also it would be much less robust if I did it that way.  DACs aren't that expensive for 10-12 bits.  I want somewhat fine drive adjustment for better temperature control, which would require a much lower frequency to get the resolution.


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, September 12, 2020 6:28 AM, <spamBeGoneenkitecSTOPspamspamEraseMEgmail.com> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\12@110745 by Dave Tweed

face
flavicon
face
> 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
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\12@113603 by madscientistatlarge n/a

flavicon
face

That was an excellent suggestion.  I would say I wanted to take the square root of the power calculated with PID, because I'm varying the DC voltage to the heater.  If I did it with PWN the duty cycle would be directly proportional to the power and hence no square root.  I'll only be monitoring the current and converter output voltage for fault protection, hence noise won't be a problem.  I'll be putting the thermocouple amplifier/ digitizer in it's own box inside, And I'll put the switching converters in another.  I'll finally be using some of my altoids tins.  FYI, I'll be using an HP server supply to provide 12V for the other rails.  As I said they can be had for less than $20 on ebay, and the SMbus will also provide potentially valuable data.  They also provide a nice 12V output when "off" that I can use to keep the AVR going.  I'll probably display the time even when it's "off", with a real power switch on the back for issues.

I'll also set it for an adjustable auto off period, I've left way to many irons on accidentally, which makes it hard to maintain the tips and cooks them up nicely.  I will be using mostly tin/lead solder which helps but no iron likes cooking for hours without tending.  At my last real electronics job the first thing I always did to the soldering station was turn the heat down 50 Deg F, and then clean and retin the tip.  I made the fastest and best solder joint of anyone in that small company, including someone who'd done assembly work.  My through hole soldering always had some solder on the pad on top of the board.  Some people don't realize that taking the time to take care of tools saves you more time than the maintenance took.  Not to mention that running the iron 50 Deg F warmer eats tips much faster and makes the surface oxidize faster.

When I was in middle school summers were boring (3 miles from a tiny town), I desoldered a lot of parts off old boards and that taught me a great deal, especially since the nearest radio shack was 30 minutes away in a car.


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Saturday, September 12, 2020 9:07 AM, Dave Tweed <KILLspampicspamBeGonespamdtweed.com> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\17@035751 by Mike

picon face
The Doom square root is a very clever bit of code, but it relies on the 32bit floating point format which you probably won't be using on an AVR if speed is important.

Mike

On 17/09/2020 07:35, Zona wrote:
{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\18@062528 by RussellMc

face picon face
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
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\19@155530 by madscientistatlarge n/a

flavicon
face

That link is a free download, Iff you belong to a member institution which I sadly do not.


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, September 18, 2020 5:45 AM, Chris Smolinski <@spam@csmolinski@spam@spamspam_OUTblackcatsystems.com> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\21@113157 by sergio

flavicon
face
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 have looked at the book you mentioned, in particular the square root algorithm, and it essentially describes what my C code does. I wish I'd known about this book 20 years ago, it would have saved me a few hours of work.

Regards
Sergio Masci

On Fri, 18 Sep 2020, RussellMc wrote:

{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@065458 by RussellMc

face picon face
On Tue, 22 Sep 2020 at 10:52, sergio <.....smplxspam_OUTspamallotrope.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=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


_______________________________________________







>
>
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@065458 by sergio

flavicon
face

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:

{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@103546 by Byron Jeff

flavicon
face
It's available in an online digital library:

https://catalog.hathitrust.org/Record/008299070

Click the Full View link to get a reader on the entire book. Section
mentioned below starts on page 63 of that document.

BAJ

On Fri, Sep 18, 2020 at 10:24:40PM +1200, RussellMc wrote:
{Quote hidden}

-- Byron A. Jeff
Associate Professor: Department of Computer Science and Information Technology
College of Information and Mathematical Sciences
Clayton State University
http://faculty.clayton.edu/bjeff
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@141327 by madscientistatlarge n/a

flavicon
face

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!


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, September 23, 2020 7:45 AM, sergio <TakeThisOuTsmplxKILLspamspamspamallotrope.net> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\23@141327 by sergio

flavicon
face


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
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@160246 by Dave Tweed

face
flavicon
face
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
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@162247 by madscientistatlarge n/a

flavicon
face

After further thought, I realized I'd made that confusion.  Good to have it on the list.


Sent with ProtonMail Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, September 23, 2020 2:02 PM, Dave Tweed <RemoveMEpicspamspamBeGonedtweed.com> wrote:

{Quote hidden}

--
http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist

2020\09\23@162956 by RussellMc

face picon face
On Thu, 24 Sep 2020 at 01:55, sergio <spamBeGonesmplx@spam@spamspam_OUTallotrope.net> wrote:

> ... I think I understand what the problem is now. I believe you are
> trying to show
> that ...


I'm afraid that you have completely misunderstood my intentions.

My apologies if I've managed to convey my response differently or less
clearly than I intended.

When I saw your original comments I knew that Ken would be interested and
forwarded a copy of the list email to him.
As interest was expressed in his prior response that I posted (with
reference to a useful book from long ago) I thought it appropriate to
forward his subsequent enthusiastic responses to me.

He and you are probably 'of a kind' in developing advanced algorithms and
working on developing more sophisticated versions as much for the pleasure
of the pursuit as anything else.
Ken responded with typical enthusiasm and the series of emails that I
forwarded show his ongoing interest over a period of 6 days (one on 18
September then 4 on 23 September ! (NZT).
I did not look at your code but presumably Ken did. Your code is copyright
as of right, so adding a copyright indication makes no difference.
I cannot speak for him with utter certainty but would be essentially
certain that you had sparked his interest and desire to show what he had
found in following a similar path to you in developing his algorithms. He's
not the sort of person who takes umbrage at the successes of others.

As I said previously - I defer to both of you in this area.



             Russell


>
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\23@162956 by Zona

flavicon
face
Hobbies and dream let us label the same.
Dont let the unbearable reality destroy our original intention.

>From Far East.
Zona.
On Wed, 23 Sep 2020 19:48:13 +0100 (BST)
sergio <TakeThisOuTsmplxspamspamallotrope.net> wrote:

{Quote hidden}

-- BR.
----
Zona <zanoEraseMEspamtom.com>
-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\24@063511 by RussellMc

face picon face
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 >= r
           x = x - r
           r = 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).



{Quote hidden}

-- http://www.piclist.com/techref/piclist PIC/SX FAQ & list archive
View/change your membership options at
mailman.mit.edu/mailman/listinfo/piclist
.

2020\09\24@105019 by Vicent Colomar Prats

picon face
part 1 2745 bytes content-type:text/plain; charset="utf-8" (decoded base64)

Hello Russel,

I tried the algorithm you presented and it is not working like you explain.
I tried it with DECIMAL numbers. The algorithm works, but what it does is:
in each loop wich is true, it increments the integer result of the square
root by 1. So you have to add an other variable for the result. I do not
know how to get de decimal part out of it yet. I do not understand what is
the purpose of " insert a 0 into r to the left of least significant bit"
This should be the algorithm:

> input n
> x=5*n
> r=5
> integer_result=0
> while (x >= r)
>   integer_result = integer_result+1
>   x = x-r
>   r = r+10
> endwhile


Tried it with Excel formulae, as you can see there is no extra variable but
you can count the number of ture iterations in yellow/orange:
[image: 2020-09-24.png]
[image: 2020-09-24 (1).png]
[image: 2020-09-24 (2).png]
 I will give it a try later for the fractional part and with binary
numbers.

Missatge de RussellMc <RemoveMEapptechnzEraseMEspamspam_OUTgmail.com> del dia dj., 24 de set. 2020 a
les 12:38:

> 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 >= r
>             x = x - r
>             r = 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).
>
>
>
>
>

part 2 16452 bytes content-type:image/png; name="2020-09-24.png" (decode)


part 3 16440 bytes content-type:image/png; name="2020-09-24 (1).png" (decode)


part 4 16285 bytes content-type:image/png; name="2020-09-24 (2).png" (decode)


part 5 197 bytes content-type:text/plain; name="ATT00001.txt" (decode)

2020\09\24@111442 by Vicent Colomar Prats

picon face
part 1 3747 bytes content-type:text/plain; charset="utf-8" (decoded base64)

Also found this on Wikipedia:
en.wikipedia.org/wiki/Methods_of_computing_square_roots

This is the algorithm (referenced as Mr. Woo Abacus method:

int32_t isqrt(int32_t num) {
   assert(("sqrt input should be non-negative", num > 0));
   int32_t res = 0;
   int32_t bit = 1 << 30; // The second-to-top bit is set.
                          // Same as ((unsigned) INT32_MAX + 1) / 2.

   // "bit" starts at the highest power of four <= the argument.
   while (bit > num)
       bit >>= 2;

   while (bit != 0) {
       if (num >= res + bit) {
           num -= res + bit;
           res = (res >> 1) + bit;
       } else
           res >>= 1;
       bit >>= 2;
   }
   return res;}

Not tested yet the difference in cycles with previous algorithm.


Missatge de Vicent Colomar Prats <@spam@vicentecolomarRemoveMEspamEraseMEgmail.com> del dia dj., 24
de set. 2020 a les 16:50:

> Hello Russel,
>
> I tried the algorithm you presented and it is not working like you
> explain. I tried it with DECIMAL numbers. The algorithm works, but what it
> does is: in each loop wich is true, it increments the integer result of the
> square root by 1. So you have to add an other variable for the result. I do
> not know how to get de decimal part out of it yet. I do not understand what
> is the purpose of " insert a 0 into r to the left of least significant bit"
> This should be the algorithm:
>
>> input n
>> x=5*n
>> r=5
>> integer_result=0
>> while (x >= r)
>>   integer_result = integer_result+1
>>   x = x-r
>>   r = r+10
>> endwhile
>
>
> Tried it with Excel formulae, as you can see there is no extra variable
> but you can count the number of ture iterations in yellow/orange:
> [image: 2020-09-24.png]
> [image: 2020-09-24 (1).png]
> [image: 2020-09-24 (2).png]
>   I will give it a try later for the fractional part and with binary
> numbers.
>
> Missatge de RussellMc <EraseMEapptechnzspam@spam@gmail.com> del dia dj., 24 de set. 2020
> a les 12:38:
>
>> 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 >= r
>>             x = x - r
>>             r = 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).
>>
>>
>>
>>
>>

part 2 16452 bytes content-type:image/png; name="2020-09-24.png" (decode)


part 3 16440 bytes content-type:image/png; name="2020-09-24 (1).png" (decode)


part 4 16285 bytes content-type:image/png; name="2020-09-24 (2).png" (decode)


part 5 197 bytes content-type:text/plain; name="ATT00001.txt" (decode)

2020\09\24@141046 by Vicent Colomar Prats

picon face
part 1 4251 bytes content-type:text/plain; charset="utf-8" (decoded base64)

Tried both methods.

Conclusion: 5*n algorithm (or whatever it is called) it is only good with
small 8 bit numbers. Whenever the number is big the Mr Woo algorithm runs
in less time. When it is related to 16 bit or greater, 5*n turns terribly
slow.

Missatge de Vicent Colomar Prats <@spam@vicentecolomarspam_OUTspam.....gmail.com> del dia dj., 24
de set. 2020 a les 17:14:

> Also found this on Wikipedia:
> en.wikipedia.org/wiki/Methods_of_computing_square_roots
>
> This is the algorithm (referenced as Mr. Woo Abacus method:
>
> int32_t isqrt(int32_t num) {
>     assert(("sqrt input should be non-negative", num > 0));
>     int32_t res = 0;
>     int32_t bit = 1 << 30; // The second-to-top bit is set.
>                            // Same as ((unsigned) INT32_MAX + 1) / 2.
>
>     // "bit" starts at the highest power of four <= the argument.
>     while (bit > num)
>         bit >>= 2;
>
>     while (bit != 0) {
>         if (num >= res + bit) {
>             num -= res + bit;
>             res = (res >> 1) + bit;
>         } else
>             res >>= 1;
>         bit >>= 2;
>     }
>     return res;}
>
> Not tested yet the difference in cycles with previous algorithm.
>
>
> Missatge de Vicent Colomar Prats <spamBeGonevicentecolomarEraseMEspamgmail.com> del dia dj.,
> 24 de set. 2020 a les 16:50:
>
>> Hello Russel,
>>
>> I tried the algorithm you presented and it is not working like you
>> explain. I tried it with DECIMAL numbers. The algorithm works, but what it
>> does is: in each loop wich is true, it increments the integer result of the
>> square root by 1. So you have to add an other variable for the result. I do
>> not know how to get de decimal part out of it yet. I do not understand what
>> is the purpose of " insert a 0 into r to the left of least significant bit"
>> This should be the algorithm:
>>
>>> input n
>>> x=5*n
>>> r=5
>>> integer_result=0
>>> while (x >= r)
>>>   integer_result = integer_result+1
>>>   x = x-r
>>>   r = r+10
>>> endwhile
>>
>>
>> Tried it with Excel formulae, as you can see there is no extra variable
>> but you can count the number of ture iterations in yellow/orange:
>> [image: 2020-09-24.png]
>> [image: 2020-09-24 (1).png]
>> [image: 2020-09-24 (2).png]
>>   I will give it a try later for the fractional part and with binary
>> numbers.
>>
>> Missatge de RussellMc <apptechnzspamBeGonespamgmail.com> del dia dj., 24 de set. 2020
>> a les 12:38:
>>
>>> 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 >= r
>>>             x = x - r
>>>             r = 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).
>>>
>>>
>>>
>>>
>>>

part 2 16452 bytes content-type:image/png; name="2020-09-24.png" (decode)


part 3 16440 bytes content-type:image/png; name="2020-09-24 (1).png" (decode)


part 4 16285 bytes content-type:image/png; name="2020-09-24 (2).png" (decode)


part 5 197 bytes content-type:text/plain; name="ATT00001.txt" (decode)

More... (looser matching)
- Last day of these posts
- In 2020 , 2021 only
- Today
- New search...