fractional division

Go To Last Post
27 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.
Last Edited: Tue. Mar 20, 2018 - 11:02 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MikeRD03 wrote:
Is there something out there?

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

 

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

awneil wrote:
You realise that AVR 'C' compilers do support floating-point ... ?
One of them even does fixed point multiplication/division (and the source of how it does it is "open").

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

http://www.cplusplus.com/reference/cstdlib/div/ wrote:
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.
But this just gives you that structure. Awneil's link go GNU is better.

 

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.

Paul van der Hoeven.
Bunch of old projects with AVR's:
http://www.hoevendesign.com

Last Edited: Mon. Mar 19, 2018 - 11:25 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

but OP specifically requested not quotient & remainder. 

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

awneil wrote:
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. 

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Last Edited: Mon. Mar 19, 2018 - 01:28 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

Last Edited: Mon. Mar 19, 2018 - 02:20 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Presumably ?

 

1001 / 100 = 10.01

 

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
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.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.......

When in the dark remember-the future looks brighter than ever.

Last Edited: Mon. Mar 19, 2018 - 03:55 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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. :)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

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

theusch wrote:
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?

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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 ?) 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

 

Jim Wagner Oregon Research Electronics, Consulting Div. Tangent, OR, USA http://www.orelectronics.net

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MikeRD03 wrote:
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?

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

awneil wrote:
In what way is a remainder not "real" ?

theusch wrote:
Perhaps OP can give a couple example sets of starting 8-bit values and the desired results. But that would be somewhat imaginary.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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...

 

IEEE 754r Half Floating Point Format.svg

That's even going wild and throwing in a sign bit! As it says "there are 11 bits of significand precision (log10(211) ≈ 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!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
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...

 

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanx ka7ehk for clearing it up - I am looking for fixed point division. I have numbers 2.6 in format. Two bit integer and rest for fractional part. Best would be a routine where the fixed point location is changable.

Last Edited: Mon. Mar 19, 2018 - 08:03 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MikeRD03 wrote:

Thanx ka7ehk for clearing it up - I am looking for fixed point division. I have numbers 2.6 in format. Two bit integer and rest for fractional part. Best would be a routine where the fixed point location is changable.

 

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. 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

@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 1000000000000000, and the divisor becomes 0000001100000000

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:

1010111000000000 / 0000000001010100 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.

"Experience is what enables you to recognise a mistake the second time you make it."

"Good judgement comes from experience.  Experience comes from bad judgement."

"Wisdom is always wont to arrive late, and to be a little approximate on first possession."

"When you hear hoofbeats, think horses, not unicorns."

"Fast.  Cheap.  Good.  Pick two."

"Read a lot.  Write a lot."

"We see a lot of arses on handlebars around here." - [J Ekdahl]

 

Last Edited: Mon. Mar 19, 2018 - 10:19 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Probably it's possible to use the remainder to round to nearest instead of truncate. But maybe it's not worth the effort.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.