That Microchip application note on math operations for 8 bit assembly is a must read. They have a really nice division routine I've used, highly compact. I've extended it myself to 32 bit division and it's still relatively short. Though, I much prefer the 16 bit devices over the 8 bit devices so I haven't used those routines much. I only use the 8 bit devices for the most simple of tasks, which has not been often.

That's one thing (among many) that can be said for the 16 bit devices, they use a hardware divider. That's typcially something transparent when writing code in a higer level language, but for assembly, it makes things much simpler. I'm probably unusual in that I actually code 16 bit devices in assembly. Most people probably use C which eliminates the need to deal with complex math algorithms or hardware accumulators.

 

When caught in a pinch with very limited PIC hardware I've done division by successive subtraction, it's very compact in code.

to get X = A / B;

X = 0
while(A>=B)
{
A -= B
X++
}

 

I have not read your post but something you must be aware of: Hardware design such as block diagrams and timing diagrams must not be drawn after the design has been completed.

Similarly, software algorithms must not be written out after the code has been written. This is putting the carriage before the horse. Algorithms must dictate how the code is to be written. Not the other way around. If the algorithm does not make sense to begin with, the code would be a hopeless failure....

Actually I start with the basic concept and a pencil and paper, before
even thinking about the code. It seems as if I am working backwards
is because I am trying to "formalize" it after the fact. I appreciate your
efforts to guide me. I'll see what I can get into some civilized form
as to the basic algorithm.

 

When caught in a pinch with very limited PIC hardware I've done division by successive subtraction, it's very compact in code.

to get X = A / B;

X = 0
while(A>=B)
{
A -= B
X++
}

Interesting approach. I don't know C language, I think I see counting
how many times B can be subtracted from A. If I am correct,
this illustrates my problem with writing the algorithms, I'll be danged if I
could write so that others could understand.

 

It took me a while to wrap my head around what you were trying to do here. Your original post stated:

;16 BIT DIVIDEND (XXXXXXXX XXXXXXXX)                                  *
;8 BIT INVERSE OF DIVISOR (1/DIVISOR)(.XXXXXXXX)                      *
;                                                                     *
;RESULT IS 16 BITS TO THE LEFT OF DECIMAL POINT, 8 BITS TO RIGHT      *
;OF THE DECIMAL POINT                                                 *
;                                                                     *
;RESULT FORMAT XXXXXXXX   XXXXXXXX   .XXXXXXXX                        *
;             HIGH BYTE   LOW BYTE   DECIMAL BYTE

The (1/DIVISOR)(.XXXXXXXX) is what threw me getting your intent and how I would interpret that. Here's my view:

Calling this a "division" problem is a misnomer (poor name) as there is nothing intrinsic to division going on here. This is a multiplication problem.

As a straight multiplication routine, 2 bytes times 1 byte to yield 3 bytes. (3 bytes is the maximum since 0xFF * 0xFFFF = 0xFEFF01 which is the largest result and it fits in 3 bytes).

Going forward I am going to call
;16 BIT DIVIDEND A

;8 BIT INVERSE OF DIVISOR B

;RESULT FORMAT C

Where C = A * B

The placement of the binary point is also somewhat arbitrary and as a coder you are free to place it where you find it most useful. As you wrote this out above, you "assumed" B would always be of the form X/256 which is why you could say it takes the form .XXXXXXXX

So if you do that to B you need do the same to C (to balance the algebraic equation). However, this has no effect on how the calculation is performed, just how the quantities are viewed.

Does any of this conflict with your goal for the routine?

 

Something else I forget to point out. Anyone can write code, in the same way anyone can talk gibberish.

The difficult task is proper and effective communication.

If you cannot communicate effectively in plain words what you are attempting to accomplish then you will have difficulty writing correct code.

Formulating a clear, concise, step by step procedure to implement the algorithm is much more important and difficult than writing code (in any programming language). Writing code is the easy part once the algorithm has been laid out.

 

I showed how to do multiplication. Now I will describe how to do division.
Division in binary follows exactly the same procedure one would perform for long division on paper. (Does anyone know how to do long division anymore?)

Suppose we wish to divide 2345 by 89.
We begin with the most significant digit of the dividend = 2
We ask, does 89 go into 2? (i.e. is 89 less than 2?)
No. We left shift the dividend = 23
Does 89 go into 23?
No. We left shift the dividend = 234
Does 89 go into 234?
Yes. How many times? 2 times
We write 2 into the quotient and calculate the remainder = 234 - 178 = 56

We left shift the remainder and add the next digit from the dividend = 565
Does 89 go into 565?
Yes, 6 times. We left shift the quotient and add the new multiplier = 26
We calculate the new remainder = 565 - 534 = 31

The result of 2345/89 = 26 with remainder = 31

I will leave it up to you as an exercise to write out the algorithm for binary division.

 

Here's my view:

Calling this a "division" problem is a misnomer (poor name) as there is nothing intrinsic to division going on here. This is a multiplication problem.

I know this, and it pains me because I don't really know what to call it
since I (maybe mistakenly) feel that shifting a binary number to the
right is in essence division by 2 to the nth place. I want to say
"multiplication by decimal binary (.XXXX)" but, combining the phrases
"decimal" and "binary" seems wrong also. Maybe the word I am thinking
of is "mantissa", but this doesn't seem correct either. What is the word
or phrase that is equivalent to "decimal point", in base 10, for binary?
EDIT: Oh heck, I just seen the answer in your post. The phrase is "binary point".
EDIT: Maybe multiplication of a binary number and a fractional binary number?

Going forward I am going to call
;16 BIT DIVIDEND A

;8 BIT INVERSE OF DIVISOR B

;RESULT FORMAT C

Where C = A * B

Does any of this conflict with your goal for the routine?

Equation to be solved:

C=A/B

Also True:

C=A * (1/B)

Are we on the same page?

Maybe this will help to explain it.
If I made a mistake writing this it may make
the problem worse.

Division by multiplication of dividend
and inverse value of divisor using
binary numbers

Starting values:
            Binary value of dividend is of the form: XXXXXXXX
            Divisor is inverted (1/Divisor) and result is in binary
            of the form:  .XXXXXXXX (note the "decimal point")

Solution will be of the binary form:  XXXXXXXX.YYYYYYYY


1.  Inverted value of divisor is saved as [DIVISOR].

2.   Dividend is shifted 1 place to the right and saved as [DIVIDEND].

3.   Most significant bit (MSB) of [DIVISOR] is checked.

4.   If MSB is set (1), save value of [DIVIDEND] as an interim value.

5.   If MSB from step 2 is clear (0), shift [DIVIDEND] 1 place to the right
      and save as [DIVIDEND].
 
6.  Shift [DIVISOR] 1 place to the left and save as [DIVISOR].

7.   Repeat from step 3 until all bits of the original value of inverted divisor
      have been checked.

8.  When all bits of the original value of inverted divisor have been checked,
     the solution will be the sum of all of the interim values saved in step 3.

 

Something else I forget to point out. Anyone can write code, in the same way anyone can talk gibberish.

The difficult task is proper and effective communication.

If you cannot communicate effectively in plain words what you are attempting to accomplish then you will have difficulty writing correct code.

Formulating a clear, concise, step by step procedure to implement the algorithm is much more important and difficult than writing code (in any programming language). Writing code is the easy part once the algorithm has been laid out.

This is so true. It also takes practice.

Please review/critique attachment in post #28.



Where do I sign up for "gibbersh 101"?
Nevermind, I think I may have that covered.

 

The reciprocal of a divisor is 1/DIVISOR. This is still a division.
How are you going to compute 1/DIVISOR?

 

The reciprocal of a divisor is 1/DIVISOR. This is still a division.
How are you going to compute 1/DIVISOR?

I considered that. That is for another day. For the project I
had in mind for this routine, 1/DIVISOR will be a constant, the
Dividend/Multiplicand whatever is the proper term will be variable.
Some time in the future I'll develop that aspect, after this is proven/disproven.
One step at a time.

Thanks.

 

Ok.Then scrap the idea of division being the inverse of multiplication.
Just go ahead and do the division in the first place.

 

There are many ways and tricks to simplify integer arithmetic, for example, how to turn a division into a multiplication. I had promised other readers of AAC that I would put together a collection of some of my tricks. I have not found the time to do this... I'm just too busy answering more interesting problems like yours.

 

Multiplication or division by a constant is much easier, there's even a site that will generate the code:
http://www.piclist.com/techref/piclist/codegen/constdivmul.htm

I mostly agree with scrapping the idea of calculating the reciprocal and then multiplying, except in the special case where you have spare program space and are going to use the same divisor multiple times in a row (I'm not sure how many times it needs to be to give a speed advantage, I'm guessing about 6, multiplication is faster than division).

 

I'm just too busy answering more interesting problems like yours.

You are too kind sir.

Multiplication or division by a constant is much easier, there's even a site that will generate the code:
http://www.piclist.com/techref/piclist/codegen/constdivmul.htm

I have used that exact site before. I would work out an example
then see if I my answer matched the answer given by the code
generator before using the code.

I mostly agree with scrapping the idea of calculating the reciprocal and then multiplying, except in the special case where you have spare program space and are going to use the same divisor multiple times in a row (I'm not sure how many times it needs to be to give a speed advantage, I'm guessing about 6, multiplication is faster than division).

Ok.Then scrap the idea of division being the inverse of multiplication.
Just go ahead and do the division in the first place.

2 votes for scrapping. Anyone else?

If some knows of a fatal flaw in the logic/process please point it out so I can
add a warning to all my examples before someone unwittingly uses
anything as an example. Ugly/inefficient code I wouldn't like, but flawed
logic/process for the unforwarned could be devastating to others. Otherwise
I will leave everything as it stands.

Thanks.

 

Binary division takes about the same time as multiplication because the steps are similar.
Many MCUs have hardware multiply and divide that can simplify the code tremendously.

 

2 votes for scrapping. Anyone else?

If some knows of a fatal flaw in the logic/process please point it out so I can
add a warning to all my examples before someone unwittingly uses
anything as an example. Ugly/inefficient code I wouldn't like, but flawed
logic/process for the unforwarned could be devastating to others. Otherwise
I will leave everything as it stands.

I'm firmly still on the fence. In a previous post you mentioned "Equation to be solved: C=A/B." But you don't give any further information such as the expected range of values for A or B (and thus C).

Usually there are "tricks" and shortcuts you can take that both add speed and accuracy to simple integer calculations, such as when you sum a number of samples to make an average try to use a power of two samples (2,4,8,16,32, etc). That way, when you go to do the division you can just use a (few) shift instruction(s).

I had the occasion where I needed to calculate Y = MX + B for a system to approximate an exponential response for a 10 bit in/10 bit out system. After inspecting the M and B for the intervals I needed it was obvious a better equation would be Y = X/M2 - B2, as in every case M was < 1 and B was <0. By using division and subtraction I was able to use an array of unsigned integers to define the lines. I also sneaked some extra resolution into the calculations by NOT doing the summation shift as described in the previous paragraph.

So long story short: it's best to know all the information before doing such coding.

Also, if you let us know how the data is collected we should be able to show you how to calculate the accuracy and resolution of the measurement system.

 

...
2 votes for scrapping. Anyone else?
...

Me.

...
Binary division takes about the same time as multiplication because the steps are similar.
Many MCUs have hardware multiply and divide that can simplify the code tremendously.

That's good advice. Going from a PIC 16F to 18F would be a big benefit. In every datasheet for a PIC 18F micro there is a chapter on the 18F "hardware multiplier", it lists the official number of program instructions and time (cycles) needed to do multiply and divide for PIC 16F and 18F;

device    task                  insts    cycles (max)

PIC 16F   8x8 mult unsigned     13       69
PIC 18F   8x8 mult unsigned     1        1
PIC 16F   8x8 mult signed       33       91
PIC 18F   8x8 mult signed       6        6

PIC 16F   16x16 div unsigned    21       242
PIC 18F   16x16 div unsigned    28       28
PIC 16F   16x16 div signed      52       254
PIC 18F   16x16 div signed      35       40

...
Interesting approach. I don't know C language, I think I see counting
how many times B can be subtracted from A.
...

You are correct, that is what it is doing. It is a very simple way to do divide, or multiply;
successive subtraction = divide
successive addition = multiply

Depending on the task it can be relatively efficient too. I did one that was an RPM meter (tacho) that received an input signal as a uS period, and needed to turn on a LED >X RPM. The calc of uS period to RPM is 60000000 / period and since the PIC was small and did not have room in ROM for a 32bit division routine I just used a 32bit successive subtraction. As the RPM was always low (<100) it was an efficient enough way to do the task.

 

I'm firmly still on the fence. In a previous post you mentioned "Equation to be solved: C=A/B." But you don't give any further information such as the expected range of values for A or B (and thus C).

Information provided to satisfy your curiousity.

Provided in binary format for convenience.

Range of values:
C: b 0000 0000 0000 0000.0000 0001 - b 1111 1111 1111 1111.1111 1111 (note binary point)
A: b 0000 0000 0000 0001 - b 1111 1111 1111 1111
B: b 0000 0001 - b 1111 1111

Resolution (of C): ≈.004 (1/255) (b 0.0000 0001)

Thanks

 

I really don't think in binary.
I do find hex more useful as you can see bytes with less counting.

For: C = A/B

Range of inputs A & B:
1 >= A <= 0xFFFF (65535) ( 2 bytes)

1 >= B <= 0xFF (255) ( 1 byte)

C min = 1 / 255 = 0.0039216 = 0x0000.01 ( 3 bytes)

C max = 65535 / 1 = 65535 = 0xFFFF.00 ( 3 bytes)

OK, I see two things you could do here. First is to hide the binary point by multiplying both sides of the equation (C=A/B) by 0x100, and let A' be A*0x100 and C' = C*0x100.

Now the max range for A' and C' are:

A' <= 0xFFFF00

C' <= 0xFFFFFF

Note the binary points are gone for the calculation.

You may also want a rounded off division. You can do that by checking if the remainder of the division is half or more of the divisor. Or, since we are doing integer division, you can also add half the divisor to the dividend and automatically compute a rounded result.

Using rounding with the multiplying for the binary point couldn't be simpler as the lowest byte of A' is always zero, so you can just copy in B and shift it one bit.

You still have a binary point hidden in the result, and that may be an issue if you are going to convert the result to decimal to display it. It gets messy.

The way I have dealt with this in the past is to pick the units I am calculation with to be as helpful as possible. When I had a task to display a current from 0.01 to 99.9 mA I choose as my units 100mA, so a value of 1 meant 00.1 mA. So the number could be converted by a simple 2-byte to ASCII routine, then insert a "." into the resulting string where need be.