RichTW:


I have implemented the Goldschmidt Square Root Algorithm for fixed-point numbers, and it works just fine. In addition, a side benefit of the Goldschmidt Square Root Algorithm is that it simultaneously calculates the reciprocal of the square root: 1/sqrt(x). That is really the value that I was wanting because I needed that term in order to solve the Law of Cosines. Squaring the reciprocal of the square root enables division by multiplication of the reciprocal of the divisor.

I have a paper describing the algorithms and how to estimate the initial value of the reciprocal of the square root. It is based on an estimate derived for how the initial value for the floating point algorithm can be derived from the exponent of the floating point value. My initial estimate is based on the most significant bit of the fixed-point value for which I want to calculate the reciprocal of the square root. In my application, I only have to calculate the Law of Cosines twice in each control loop cycle. Therefore, I only looked for an initial value that would limit the number of iterations equally for the ranges in which I binned the input data. I also wanted the accuracy to be about the same for each of these bins, so I biased my estimate to accomplish this.

I'll have to sanitized the paper somewhat to remove some stuff that is not suitable for public disclosure. If the preceding is insufficient to get you started, send me a PM and I'll undertake to sanitize the paper over the next few days.

Added link to article on fixed-point Goldschmidt Square Root Algorithm.

_________________
Michael A.

(BTW squaring can be a bit cheaper than general multiplication, if you're doing it by hand)

It seems that my first attempt does break if the denominator is more than 32767, in which case the first step of producing each bit can shift a set bit out of the numerator. So we can catch that case and handle it specially:

Hi friends! My very first post here (beside the introduction that I wrote in General Discussion).

Back in the late 80s and early 90s I did some C64 coding for pleasure and it was cool to understand what was really happening under the hood of a computer. I managed to learn little ML, and learnt to write (by looking at other people's code) some VIC effects, some scrolling, removing some (easy) protections... just for fun, no money!

In the last few months a desire come out: to switch on my old C= gear and have some fun with it. In the meantime that I can find some room for that gear, I started to have a look at X86 tools and spent some time in trying to find a good suite; I've decided that CBM Prog Studio seems the right one for me.

I am trying to get acquainted to basic ML development and I'm in trouble with Zaks 8-bit restoring division... I just can't get it working. In the book (http://retro.hansotten.nl/uploads/books/Programming_the_6502.pdf) there is only a flowchart, but not the code (fig. 3-19 @ PDF page 92 / book page 86). I tried to write the code on my own, but... it just doesn't work

So I Googled and found a different way to make a restoring division, that's here https://www.ques10.com/p/11096/draw-the-flow-chart-for-restore-division-algorit-1/ and also https://www.youtube.com/watch?v=PzV6gYpVLuc and it works well:



If I try to translate Zaks' flowchart to code, I believe it should look like this:



I understand that non-restoring will be easier and faster, but I'm trying to build my own knowledge and follow the books chapter after chapter; I got stuck on the division and I am kindly asking help to understand what's wrong with my implementation of Zaks' 8-bit restoring division.

Thanks,
Andrea

The book doesn't explain it very clearly.

The algorithm uses three values. Two of them are combined into one double-width value, which starts with 0 in the top half and the dividend in the bottom half. The third value is the divisor, and never changes. When the algorithm is finished, the quotient is in the bottom half of the double-width value (the one that started out as the dividend), and the remainder is in the top half (which started as 0).

It's confusing, as the book talks about subtracting the divisor from the dividend, but you actually subtract from the value that the dividend is being shifted into.

An example should help. Here I am dividing 15 (00001111) by 3 (00000011).


Your code is almost right. You have DVD and Q initialised correctly (although Q will become the remainder, not the quotient). But you're then subtracting the divisor from A, not Q. And you're incrementing Q, not DVD.

You could fix it by adding instructions to load A from Q and store it back:

The quotient will then end up in DVD and the remainder in Q (warning: I haven't tested this). But it's easier to keep Q in A, so you don't have to shuffle it back and forth to memory all the time.

You probably meant Q to be the quotient, but with this algorithm the quotient ends up in the same place as the dividend input. You could rename Q to R for remainder. But with it being stored in A, it never needs to get a name at all.

The CLC before the ADC is not needed as the carry must already be clear or the BCS would have been executed.

_________________
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

Thank you friends, now I understand. IM(very)HO the explanation in the book is very hard to understand, at a point that it seems wrong if one is not very knowledgeable with the topic.

That's true! Thank you for pointing out!



Thak you very much for the explanation! I believe the code could be optimized by using:

rather than:



Right? I've implemented it and it seems to work well - this is the code with more meaningful labels:



Now I see the code from an "understanding it point of view" and I think that some optimization can be made:





... and finally I came on my own to use A and save lot of cycles, just as per your suggestion.

Thank you both once again, now it's much clearer. I am very grateful to you. Time to move on to other exercises in Zaks' book!!!

Andrea