Garth [et-all],

I've been using something similar to your HTD routine for years but starting LSbit first, had I thought to do it MSbit first it would have been faster and shorter. What I have now is similar and as short and fast as I can easily make it. If anyone can think of a faster and/or shorter version please post it.

First saving is to convert the lowest four bits directly thus ..

.. this saves cycles, as we don't have four trips through the add loop, and bytes as the table is shorter. Next re-arrange the table so that all the bytes of the same magnitude are together. This saves two DEX instructions and looks like this ..

.. note that the values are all -1 as the next change is to remove the CLC from before the adds. As the carry is always set it is allowed for here.

The only other change is to hold the highest result byte in the Y register while evaluating, this saves a couple of cycles per loop.

The result is ..

That's all I can think of, it runs somewhere between 250 cycles for all bits = 0, and 650 cycles for all 1s.

Cheers,

Lee.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I have a more compact version that does away with the data tables but it costs more cycles to execute.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

I'm surprised not to see the following extremely simple method suggested anywhere: "loop through" the number to be converted, using the 6502's decimal mode to increment the accumulator decimally (from 0) while decrementing the original value hexadecimally (X register). It might not be particularly efficient for large numbers, but the code is short and simple to understand.


The subroutine above performs a hex-to-decimal conversion on the number in the accumulator. It sets the D flag, but leaves the X register unchanged.

_________________
Languages shape the way we think, or don't.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

"Elegance is necessarily unnatural, only achieveable at great expense. If you just do something, it won't be elegant, but if you do it and then see what might be more elegant, and do it again, you might, after an unknown number of iterations, get something that is very elegant."

Many thanks for the improvements, GARTHWILSON. Of course, for serious projects, one would probably not use this algorithm (if that's an appropriate name for it); it's useful, though, if one just needs a short piece of code which does the job in a readable manner.

A better subroutine should certainly save the status register. How would you go about accomplishing that?

_________________
Languages shape the way we think, or don't.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Assuming you're talking about the sum of differences (or what ever it's
called, the differences between succesive squares increase by 2 and are
just the odd numbers, sum the odd numbers till you get your square
and the number of odd numbers you summed is the square root), that's
how HP calculators do it (or did it) (sort of), they use a pseudo division
routine and use that method to find each digit.

Detailed in a famous series of articles by William E Egbert

Personal Calculator Algorithms 1: Square Roots

I think it's here

http://www.hpl.hp.com/hpjournal/pdfs/Is ... 977-05.pdf (5.8MB)

WOW. I was never taught how to solve square roots by hand, but this successive approximation technique is just plain common sense. Nothing magical about it; and, of all the by-hand techniques I have seen in the past, this is the one which makes the most amount of intuitive sense, by far.

Thank you for the link, bogax. That really was educational.

A little googling will find dozens of explanations, damn few of them are
any where near as lucid as Egbert's article he makes it simple.

(note the typical bit by bit fast binary square root is just the same, except
in binary instead of decimal which makes it simpler, how many explanations
of it are as lucid as that article?)

He just does a really good job of explaining it.

You might want to look at the other articles (I guess if they didn't teach
you how to find square roots they probably didn't teach you how to find
eg logarithims ) (damn these personal caclulators )

Personal Calculator Algorithms II: Trigonometric Functions

http://www.hpl.hp.com/hpjournal/pdfs/Is ... 977-06.pdf (4.6MB)

Personal Calculator Algorithms III: Inverse Trigonometric Functions

http://www.hpl.hp.com/hpjournal/pdfs/Is ... 977-11.pdf (8MB)

Personal Calculator Algorithms IV: Logarithmic Functions

http://www.hpl.hp.com/hpjournal/pdfs/Is ... 978-04.pdf (7.8MB)

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I thought this might be Newton's method, but research on the web suggests otherwise. However, upon further reflection, I'm not sure how this might be used, since as r increases, it will attempt to diverge. Solving for r algebraically results in some hairy (in my opinion) math.

For those wondering where this equation came from, it is this:



This is simply the sum-of-odds technique discussed earlier. This is the worst possible performance (O(n)), but it's brutally simple.

The reason I like HP's algorithm better than any of these is that, since display precision is finite, you know a priori when to stop your calculation. E.g., there is no point in proceeding beyond 12 iterations if all you have is a 12-digit display field. And, it's much simpler to reason about than Newton's method.

Which is more or less how EhBASIC does SQR()

Lee.

I found this algorithm years ago and have it programmed into a 6502 circuit I built, and it works pretty well. I think it is called the Babylonia Algorithm. It uses simple math operations, and as long as the numbers are not really large, it converges to fairly accurate values with about 10 to 15 iterations. It also works for very large numbers, but the iteration count must be increased to reach the same level of accuracy.



Here are some results produced by my 6502 program using 15 interations. For comparison sake, I have also included the results from the simple Windows calculator.

Note: My 6502 program has only 14 digits after the decimal point, so the Windows results will be longer, but you can see how accurate this algorithm is through those 14 digits.




As you can see, for resonably sized numbers, the accuracy is quite good for 15 interations. Even in the last example where I input 5 million, the result is still accurate out to 7 decimal places and then deviates from the windows result. But this is easily fixed with a few additional iterations.

Since I am unlikely to ever use my 6502 circuit to crunch large numbers, 15 iterations works good enough for me, so I have never taken the time to figure out how to predict how many iterations you would need in particular number ranges, but that should be fairly easy to determine with a little experimentation.

Oops. After looking at this again, I think it really is the same thing you have above: B/B * ((A/B+B))/2 = ((A+B^2)/2B. Well, anyway, this gives you an idea of how it actually works when implimented.

Thanks for posting the HP method. I am going to take a closer look at it to see if that would be more efficient. If it works better, I will update my 6502 program to use that instead.

.
.



Since it is basically a Newtonian aproximation, you'll do a lot
better with a better initial guess than 1

Most obvious, I guess, would be to halve the number of bits
and use that as an initial guess (since squaring a number
approximately doubles the number of bits)

You could also apply one of the other methods (I'd try Garth's)
to refine that a bit further before you started doing multibyte
divisions.

eg squrt 5000 took me about 10 iterations to get 12 digits with
an initial approximation of 1 but only 4 iterations with an initial
approximation of 64 (64 being the square root of 4096, the
largest power of two that's less than 5000)


And unless you've got hardware division or you're just trying to
reuse a division routine, Lee's way is probably best.

Here's an interesting derivation

http://codebase64.org/doku.php?id=base:fast_sqrt