Hello, I am looking for a division routine for two 8bit numbers that outputs real fractional binary numbers - not ony a remainder. Is there something out there?

Mike

Author

Message

Hello, I am looking for a division routine for two 8bit numbers that outputs real fractional binary numbers - not ony a remainder. Is there something out there?

Mike

This topic has a solution. Jump to the solution.

Last Edited: Tue. Mar 20, 2018 - 11:02 AM

Level: Moderator

Joined: Mon. Jul 18, 2005

Posts: 91888 View posts

Location: (using avr-gcc in) Finchingfield, Essex, England

Have you tried search for Atmel application notes? I'm not saying there definitely IS one but Atmel are pretty good and do have notes about how to use the facilities of most of their silicon features. Just google what you are looking for and add "application note"

EDIT: not sure if they are relevant but so far I have seen mentions of AVR200 and AVR201

Last Edited: Mon. Mar 19, 2018 - 09:15 AM

Level: 10k+ Postman

Joined: Fri. Jul 1, 2005

Posts: 14845 View posts

Location: Basingstoke, Hampshire, UK

Is there something out there?

You realise that AVR 'C' compilers *do *support floating-point ... ?

Level: Moderator

Joined: Mon. Jul 18, 2005

Posts: 91888 View posts

Location: (using avr-gcc in) Finchingfield, Essex, England

You realise that AVR 'C' compilers do support floating-point ... ?

Level: 10k+ Postman

Joined: Fri. Jul 1, 2005

Posts: 14845 View posts

Location: Basingstoke, Hampshire, UK

Indeed it does: https://gcc.gnu.org/wiki/avr-gcc#Fixed-Point_Support

Integral division Returns the integral quotient and remainder of the division of numer by denom ( numer/denom ) as a structure of type div_t, ldiv_t or lldiv_t, which has two members: quot and rem.

You can also do some hand scaling:

If you shift the numer 8 bits to the left (into a 16 bit value) and you divide by the denom. then the result will have your 8 bit output and 8 bit fractional value.

You can shift any number of bits as you like, it's a tradeoff between the biggest number that will fit and resolution.

It's a good thing to do this a few times by hand to get to know how it works.

Then use the fixed point lib.

Last Edited: Mon. Mar 19, 2018 - 11:25 AM

Level: 10k+ Postman

Joined: Fri. Jul 1, 2005

Posts: 14845 View posts

Location: Basingstoke, Hampshire, UK

but OP specifically requested **not **quotient & remainder.

but OP specifically requested not quotient & remainder.

??? The way I read it, OP wants >>not<< just remainder.

Perhaps OP can give a couple example sets of starting 8-bit values and the desired results. But that would be somewhat imaginary. OP wants the real results -- not the imaginary ones.

Last Edited: Mon. Mar 19, 2018 - 01:28 PM

I have a guess. And if my guess is correct, then a possible approach?

Let's take two small numbers such as 9/4. Conventional division gives a quotient of 2 and a remainder of 1. You could use / and % , or div() and get the same.

I think OP wants whole and fractional parts for the result. (OP will need to clarify the widths, and the language.)

If C, then the straightforward way is floating point. Given the mention of 8-bit, perhaps too heavy (too large a footprint) for OP's needs?

Anyway, extend the numerator to 16 bits. Then, for 9/4, the numerator becomes 0x0900. Then divide by 4 using 16/16 division if the routine is handy, or the slightly more efficient 16/8. Now the result of that is 0x0240. The high 8 bits are the whole and the lower 8 bits are the fractional.

Last Edited: Mon. Mar 19, 2018 - 02:20 PM

Level: Moderator

Joined: Mon. Jul 18, 2005

Posts: 91888 View posts

Location: (using avr-gcc in) Finchingfield, Essex, England

Presumably ?

1001 / 100 = 10.01

and it's the .01 he's looking for? (which I guess is the 40 bit in 0x0240)

and it's the .01 he's looking for? (which I guess is the 40 bit in 0x0240)

I'm guessing that or similar. But OP said "8 bit" and your example numbers are ambiguous as 1 is the remainder.

Level: 10k+ Postman

Joined: Fri. Jul 1, 2005

Posts: 14845 View posts

Location: Basingstoke, Hampshire, UK

The way I read it initially was that OP wanted a number with a fractional part - so the 10.01 in Cliff's example.

But I see it could equally be read as "*only* the fractional part" - so 0.01.

Probably also other ways, too.

perhaps he wants an arbitrary length fractional result:

ex: 27/41 = 0.1010100010010101110110101000100101011101101010001001010111011....real fractional binary numbers??

8/11= 0.1011101000 1011101000 1011101000 1011101000 1011101000.......

Last Edited: Mon. Mar 19, 2018 - 03:55 PM

I forgot to mention - I am looking for a routine in assembler. Of course in C this ist no problem. Compiler cares for it.

I know the application notes but these examples only have division with remainder. But I need division for real math. :)

Sigh -- have you read the responses? All are speculation, as** you haven't really told us what you are looking for**.

Perhaps OP can give a couple example sets of starting 8-bit values and the desired results.

If you really want IEE754 floating point, then of course there are routines in ASM out there. Lift from a compiled program if needed. But if IEEE754 is desired then why the mention of 8 bit?

So for

8bit numbers that outputs real fractional binary numbers

You will need to tell us which floating point format you want the routine to use!

If you also want the output to be 8 bit it can't be done (don't make sense).

There are 16 bit formats but not competently used. There are a lot of code for 32 IEEE754

Why do you want 8 bit? (speed, RAM size or ?)

Mike wrote:

outputs real fractional binary numbers

There was nothing about 8-bit output. Mike, you have two fundamental choices:

(A) Fixed point. This can work if the two original 8-bit numbers have a very limited range with respect to each other. Then you know something about the maximum size of the whole part of the answer. As a result, you can assign a specific number of bits to the integer part and deal with the4 fractional part how-ever you like. The down-side of doing this is that you may need to hand optimize the division routine to fit the precise format (whole part, fractional part) to suit your needs. This process can be relatively fast (compared to floating point). AVR200 and AVR201 are your go-to references on this.

(B) Floating point. Floating point can handle a very wide range of dividend and divisor. Works best when you have less control over the relative values of the two numbers. Floating point division is a standard part of C (though you may need to add a specific library for this capability). Disadvantage is that it CAN be pretty slow and it is relatively large (in code space). Problem for you is that floating point division is pretty much out of the question in assembler.

Being stuck in assembler does not give you much wiggle room.

Jim

Level: 10k+ Postman

Joined: Fri. Jul 1, 2005

Posts: 14845 View posts

Location: Basingstoke, Hampshire, UK

I need division for real math.

In what way is a remainder not "real" ?

Again, have you not read the replies? Can you not see that nobody is sure what you're actually asking for?

In what way is a remainder not "real" ?

Perhaps OP can give a couple example sets of starting 8-bit values and the desired results. But that would be somewhatimaginary.

Level: Moderator

Joined: Mon. Jul 18, 2005

Posts: 91888 View posts

Location: (using avr-gcc in) Finchingfield, Essex, England

Just to note that if you go for some "float" format then without infinite length some things cannot be represented. Consider the decimal system we all know and love then try to express 1/3 in it. When you switch to "binary fractions" one of the commonly cited "problem numbers" is 1/10th. You would need an infinite number of binary fractional bits to represent that just as you need an infinite number of decimals for 0.33333333333....

So at some stage you have to make a compromise and accept some kind of "rounding". You have to choose where you want to draw that line. A very common format in small micros is 32bit IEEE754 that uses one bit for sign, 8 bits for the exponent and 23 bits for the fractional part (though it's always "normalised" so the presence of a 24th bit that is always 1 is assumed). See the diagram alongside this: https://en.wikipedia.org/wiki/IE...

You can't really do this in 8 bits and even in 16 bit you'd have to make a lot of compromises. Perhaps you are willing to forgo "sign" to save 1 bit but in what remains you would probably want 5 or 6 for the exponent so you are only left with 10 or 11 bits for the mantissa. That is not much accuracy (in decimal terms). Even when you get to 32 bits IEEE754 with the 23/24 bits of mantissa it's only really good for about 7.5 decimal digits.

Actually good old Wikipedia has this: https://en.wikipedia.org/wiki/Ha...

That's even going wild and throwing in a sign bit! As it says "there are 11 bits of significand precision (log_{10}(2^{11}) ≈ 3.311 decimal digits" so if you tried to represent 123.456 you would get somewhere around 123.4 or maybe 123.5 - no hope of holding the 56.

That's why C compilers on small micros are almost all convinced that 32 bit IEEE754 is the way to go. Big computers (and some 8 bit ones even if you are lucky with your C compiler) will do 64 bit IEEE which gives something like 16 decimal digits of precision.

As you are only about the millionth person to come to this you will be pleased to hear there's a lot of (32 bit) IEEE754 code for micros around. For an easy life just lift the open source out of the avr-gcc C compiler!

Level: 10k+ Postman

Joined: Fri. Jul 1, 2005

Posts: 14845 View posts

Location: Basingstoke, Hampshire, UK

As you are only about the millionth person to come to this you will be pleased to hear there's a lot of (32 bit) IEEE754 code for micros around.

Now if only there were a simple service or website that would find such stuff for us ...

Oh, wait: http://www.lmgtfy.com?q=IEEE+754+avr+assembler

And right at the top of the list is:

Cornell University Electrical Engineering 4760 Short Floating Point mathematical functions in GCC and assembler

https://people.ece.cornell.edu/l...

Last Edited: Mon. Mar 19, 2018 - 08:03 PM

I believe post #6 has answered your question a lot of posts ago. You can use a standard integer division routine, just shift the dividend first by whatever decimal places you need to have. For example, 10/3 (numbers in binary):

1010 : 11 shift by 4 to get 4 decimal places -> 10100000 : 11 = 110101

So the result in binary is 11.0101, that is, 3 + 1/4 + 1/16 = 3.3125 in decimal.

This reply has been marked as the solution. #24

@El Tangas has the right idea, although since you've specified 2.6 for both dividend and divisor, you'll want to promote to 16-bit, and shift the dividend left by 8, and the divisor left by 2 (8-**6**).

We can't take his example of 10/3, because 10 doesn't fit in 2.6. Instead, let's take 2/3. In 2.6, that's 10.000000/11.000000, which without the radix point is 10000000/11000000.

Promoting and shifting, the dividend becomes **10000000**00000000, and the divisor becomes 000000**11000000**00

Doing a simple 16-bit divide, we get 00101010, which interpreted as 2.6 is 00.101010, or 1/2 + 1/8 + 1/32 = 0.65625 in decimal, the 2.6 truncation of 0.6666666666 (2/3).

Here's an arbitrary example of Euler's number e (2.718281828) divided by 0.33333333.

In 2.6, e is 10.101110, and 0.33333333 is 00.010101. Those are of course truncated, and the real values back in decimal is are 2.71875 and 0.328125.

Now promoting and shifting:

**10101110**00000000 / 000000**00010101**00 for a quotient of 1000010010, which becomes 1000.010010. In decimal, that's 8.28125, which is close to the real value of 2.71875 / 0.03125 = 8.285714286, and pretty close to the original decimal quotient of 8.154845567. The error is due to truncation in the original operands, as well as truncation in the quotient.

Note, however, that it is also a 2.6 overflow, as 8 cannot be represented in 2.6. You could maintain 10.6 values for intermediate results, and only truncate to 2.6 when necessary.

The general technique is as @El Tangas has shown. For x.y, You shift the dividend left by y bits w.r.t. the divisor. You can shift them both by some other number of bits to ensure that maintain precision, as I've shown above by shifting each by another 2 bits. You could do the same for 24-bit or 32 bit arithmetic, and then either keep the intermediate results or carve off the x.y as needed.

EDIT: Better numbers for the example.

Last Edited: Mon. Mar 19, 2018 - 10:19 PM

Ok, I understand. So by shifting I can use the standard remainder routine, forget the remainder and shift back everything in place. Sounds resonable. :) Thanx!

Mike

Last Edited: Tue. Mar 20, 2018 - 11:00 AM

About rounding :

If you have negative numbers it common to use sign magnitude and not 2s complement

So for division the same routine is the same, just also deal with the sign bit.