Embedded Systems Conference
Breaking News
Newest First | Oldest First | Threaded View
<<   <   Page 2 / 3   >   >>
Max The Magnificent
User Rank
Re: Rounding towards positive infinity
Max The Magnificent   10/26/2013 5:58:30 PM
@josyb: To obtain the same behaviour...

Wonderful -- thanks for this (now I'll try to wrap my brain around it :-)

User Rank
Bresenham algorithm
pviry750   10/26/2013 11:09:21 AM

You're in effect drawing a straight line in a discontinous space, the coordinates being time and color value. The standard way to do this efficiently is the Bresenham algorithm. The idea is to incrementally compute the current error between the next integer color value (y coordinate) and the next "ideal" color value, and when this error becomes too large to update the current color value accordingly. Here is the code for the inner loop (excerpt from the wikipedia page) :
for x from x0 to x1
         error := error + deltaerr
         if error ≥ 0.5 then
             y := y + 1
             error := error - 1.0

Note that there is no integer division in the loop, hence no room for rounding errors. And it's efficient: never more than a comparison and two additions at each iteration.

User Rank
Rounding towards positive infinity
josyb   10/26/2013 7:03:14 AM

To obtain the same behaviour, rounding away from zero when dividing positive numbers as you get when dividing negative numbers:

if ( modcolor > 0 )   modcolor = (modcolor + howmany - 1) / howmany ;

else modcolor /= howmany ;

You can write this in a single line perhaps generating less code (as only one division operation is specified):

modcolor = (modcolor + (modcolor > 0 ? howmany - 1 : 0)) / howmany ;

This trick can also be modified for rounding half away from zero:

if (modcolor < 0) {

  sign = 1 ;

  modcolor = -modcolor ;


else sign = 0 ;

modcolor = (modcolor + (howmany / 2) - 1) / howmany ;

if (sign = 1) modcolor = -modcolor ;

If you want e.g. 1.5 to be rounded to 2 you can leave out the '-1'



Max The Magnificent
User Rank
Re: Alternative implementation
Max The Magnificent   10/25/2013 5:53:17 PM
@Garcia: Please, give me feedback once you try this

      I will do so

If I can help you with other chunk of C code, just let me know ;-)

      Don't worry ... you can count on it LOL

Max The Magnificent
User Rank
Re: Time based interrupts?
Max The Magnificent   10/25/2013 5:52:15 PM
@DrFPGA: If I were using the controller to do something else at the same time, then I would look at using a timer and interrupts as you suggest ... but in this case all I'm doing is controlling the LEDs, so I'm just using the basic Arduine delay() function.

User Rank
Re: Alternative implementation
Garcia-Lasheras   10/25/2013 5:42:26 PM
@Max: "I cannot wait to go home and try your solution thsi evening..."

Please, give me feedback once you try this -- if I can help you with other chunk of C code, just let me know ;-)

User Rank
Time based interrupts?
DrFPGA   10/25/2013 4:43:48 PM
If you think of doing this in the time domaine does it become easier? Every so many milliseconds you generate an interrupt to process colors. Check where you are and where you want to be and take a step in the direction you need with a fixed sized step. Would that work ok?

Max The Magnificent
User Rank
Re: Fixed-Point arithmetic
Max The Magnificent   10/25/2013 3:40:24 PM
@Alvie: Sometimes using Fixed-Point arithmetic can help with these issues...

It all sounds so simple the way you say it LOL

Actually, you are correct in that I had completely neglected to consider using something like a 10.6 fixed-point representation. For some tasks this would be very appropriate -- but for my current application I think I'll stick with the solution from Javi (Garcia).

User Rank
Fixed-Point arithmetic
Alvie   10/25/2013 3:21:18 PM

Sometimes using Fixed-Point arithmetic can help with these issues.

The basics behind FixedPoint are quite simple, and easy to implement in most architectures. Let's have a look at your concrete problem (255/256) and see how we could get a somewhat accurate output from it.

The easiest way to implement this would be to use a 10.6 fixed point, where 10 bits are used for the real part (signed number range would be between +511 and -512), and 6 bits for the "fractionary" part - since 6 bits can represent 64 different values, each bit can represent 1/64, 0.01625. This is your resolution in terms of the fractionary part.

The beauty about fixed-point is that most of the arithmetic is done with the integer representation. This includes addition/subtraction and multiplication.

In order to add two 10.6 fixed-point values, represented by a 16-bit integer, just... add them. The result will also be a 10.6 fixed point value. Same for subtraction. For multiplication, the result will not be 10.6, but rather 20.12 - 32 bits. In order to convert this multiplication back to 10.6, just shift it by 6 bits, and truncate the result (note: if you're dealing with signed numbers, you must do this in a slightly different way, in order to preserve the highest bit signal).

So, let's take a look at your case: 255/256.

First, let's represent them as fixed-point, 10.6 numbers, in binary

   255 => 0011111111.000000

   256 => 0100000000.000000


   1    => 0000000001.000000

In the following explanations, I'll prefix the numbers with "f" if they are representations of fixed-point values, and no prefix for their integer representations.

Now, let's invert f256. This is done by computing (f1/f256), also in fixed-point format. In order to perform this division, we use the integer representations to perform an integer division. But, similarly to the multiplication (which doubles the number of fractionary bits), the division will also change the fractionary bits - not only that, it will indeed remove them.

Let's take a look at a simple (f1/f1) division. This ought to result in f1, of course. If we take a clear look at the f1 representation above, and compute it's integer value, we get 2^6 == 64. If we divide the values using their integer representation, we get 64/64, which gives us 1. But this integer "1" does not represent "f1", it represents "0000000000.000001". So, we just lost a lot of precision (6 bits actually) by performing the division. To fix this, we shift the result by 6 bits to the left, and get the correct value: "0000000001.000000".

Now, another division. Let's divide f3 by f2, the result should be f1.5. The representation of f3 is "0000000011.000000", and f2 is "0000000010.000000". The integer representations are 192 and 128, respectively. If we perform the integer division, we get 1. If we shift this by 6-bits as in previous example, we get "0000000001.000000", which is f1 - not f1.5. So, we just lost all precision !!!

There are a few solutions to overcome this. One of them is to get a few more resolution by extending the numbers to the next representation, which in this case would be 32-bit. Basically, what we will be doing is to transform the equation:

   x  = a / b;


   x =  ( (a * N) / b ) / N

which is equivalent. The "N" value would be ((2^6)-1) in this case - which matches the 6-bit shift we have to perform to correct the division result - if we multiply the first argument by the same "shift amount" we have to perform at the end, we don't need to perform the final shift. We can also use a shift to perform the computation of the first operand.

So, for the case of f3/f2, we will get:

a*N (f3 times N): 0000000011.000000[000000] (integer representation: 12288)

b: [000000]0000000001.000000 (integer representation: 128)

And the result is 96 (12288 / 128). In binary form (and fixed point form) it's : [000000]0000000001.100000.

Integer part is 1, and fractionary part is '100000' in binary, 32 in decimal. If we multiply 32 by the fractionary resolution we computed in first place (0.01625), we get... 0.52, close enough to the "0.5" we need to add to the integer part.

Doing the same for your 255/256 values, we get a nicely looking value (result of (255<<6)/256):


We are very close to f1, and we can also truncate the result. But that would not be wise : the result is way more close to f1 than to f0.

So, we want to do rounding before converting that to an integer (which means shifting by 6 to the right). In order to do so, we add a '1' in the MSB of the to-be-discarded part. We are discarding 6 bits, so we have to add '100000' to the result:



= 0000000001.011111.

Shift by 6 to the right.... gives "1".

So, here's your answer, and a quick, dirty and confuse explanation of fixed point arithmetic :)



Max The Magnificent
User Rank
Re: Alternative implementation
Max The Magnificent   10/25/2013 2:55:31 PM
@Garcia: The more I look at your solution the more I realize just how elegant it is. The part I especially like is the fact that the color value automatically ends up at 0 or 255 without any checking or tweaking (capping). I cannot wait to go home and try your solution thsi evening...

Of course, I'm handling all 64 LEDs each with three color channels, but the way I'm doing it is by means of a plan so cunning we could pin a tail on it and call it a weasel :-)

<<   <   Page 2 / 3   >   >>

Top Comments of the Week
Like Us on Facebook

Datasheets.com Parts Search

185 million searchable parts
(please enter a part number or hit search to begin)
EE Life
Frankenstein's Fix, Teardowns, Sideshows, Design Contests, Reader Content & More
Max Maxfield

March 28 is Arduino Day -- Break Out the Party Hats!
Max Maxfield
Well, here's a bit of a conundrum. I just received an email from my chum David Ashton who hails from the "Unfinished Continent" Down Under. David's message was short and sweet; all he said ...

Bernard Cole

A Book For All Reasons
Bernard Cole
1 Comment
Robert Oshana's recent book "Software Engineering for Embedded Systems (Newnes/Elsevier)," written and edited with Mark Kraeling, is a 'book for all reasons.' At almost 1,200 pages, it ...

Martin Rowe

Leonard Nimoy, We'll Miss you
Martin Rowe
Like many of you, I was saddened to hear the news of Leonard Nimoy's death. His Star Trek character Mr. Spock was an inspiration to many of us who entered technical fields.

Rich Quinnell

Making the Grade in Industrial Design
Rich Quinnell
As every developer knows, there are the paper specifications for a product design, and then there are the real requirements. The paper specs are dry, bland, and rigidly numeric, making ...

Special Video Section
After a four-year absence, Infineon returns to Mobile World ...
A laptop’s 65-watt adapter can be made 6 times smaller and ...
An industry network should have device and data security at ...
The LTC2975 is a four-channel PMBus Power System Manager ...
In this video, a new high speed CMOS output comparator ...
The LT8640 is a 42V, 5A synchronous step-down regulator ...
The LTC2000 high-speed DAC has low noise and excellent ...
How do you protect the load and ensure output continues to ...
General-purpose DACs have applications in instrumentation, ...
Linear Technology demonstrates its latest measurement ...
Demos from Maxim Integrated at Electronica 2014 show ...
Bosch CEO Stefan Finkbeiner shows off latest combo and ...
STMicroelectronics demoed this simple gesture control ...
Keysight shows you what signals lurk in real-time at 510MHz ...
TE Connectivity's clear-plastic, full-size model car shows ...
Why culture makes Linear Tech a winner.
Recently formed Architects of Modern Power consortium ...
Specially modified Corvette C7 Stingray responds to ex Indy ...
Avago’s ACPL-K30T is the first solid-state driver qualified ...
NXP launches its line of multi-gate, multifunction, ...
EE Times Senior Technical Editor Martin Rowe will interview EMC engineer Kenneth Wyatt.
Flash Poll