Re: Turn a divide into a multiply

Have you considered a tweaked Bresenham algorithm?

Using the x axis as time, you could compute the next DAC reload value on the fly every millisecond with this approach, removing the 'jaggies' and eliminating the floating point entirely.

Kelly

Instead of dividing for every step, create multi-byte fractions and just add each step.

-- #include _ Kevin D Quitt USA 91387-4454 96.37% of all statistics are made up Per the FCA, this address may not be added to any commercial mail list

timer

direction.

It's an external 16 bit SPI DAC (yes, it's a bloody $18 part!) and we're using the entire 16 bit range... unfortunately. ;-(

It will have a few rounding errors, however the DAC has 2-3 bits of precision that we don't care about, so it gets absorbed. Timing is critical, but it isn't *THAT* critical, and even a .8 fixed point step is within the range of acceptability.

Unfortunately, it's not high enough resolution by itself.

-->Neil

You only need 16.0 and some rounding control as you sequence.

There is at least one 16 by 8 bit divide with remainder to be found on

Says it runs in 232us average, 276 worst case at 12MHz.

You can run a Bresenham algorithm on the slope of the remainder to determine if your DAC (inc/dec)rement is the quotient or quotient +1.

There would be no cumulative error. You need to understand the difference between a Bresenham algorithm and a simple incremental algorithm using fractions.

direction.

End

I'm not familiar with that processor. Have you considered unrolling the divide loop, to kill off the housekeeping and branches back and forth?

Do you HAVE to have a linear ramp, or would an exponential ramp work as well?

Like at this

#include #include #include

int main(int argc, char* argv[]) {

using namespace std;

assert(argc == 4);

int starty = atoi(argv[1]); int endy = atoi(argv[2]); int dx = atoi(argv[3]);

int dy = endy - starty; int qy = dy / dx; int ry = abs(dy % dx); int oy = starty;

int d = 2 * ry - dx; int d0 = 2 * ry; int d1 = 2 * (ry - dx); int o1 = qy + (dy > 0 ? 1 : -1);

for(int i = 1; i

Yes. See the non-restoring divide algorithm provided by nospam in another posting.

If you can reorganise the data, you may be able to use simple bit shifts to scale, multiply and divide by 2^n. I use this technique a lot to save compute time and is very fast in either C or asm...

Chris

The beauty of this algorithm is that you need an integer division only. The fractional part is handled by the Bresenham-like error-accumulation part of the loop. Why do you need 16.8 precision for this?

Andras Tantos

Not familiar w your processor but ... If you've got the memory space... will a lookup table work?

FWIW Chris.

Ok, here is an answer : DAC ramping fro many value to any value in discrete time steps, working in all cases, WITHOUT ANY DIVISION and with only multiplications by two, integers only of course !!! Derived from the Bresenham algorithm :

#include "stdafx.h" #define abs(x) ((x)>=0 ? (x) : -(x)) #define sign(x) ((x)>=0 ? 1 : -1)

int main(int argc, char* argv[]) { int xa; int ya; int xb; int yb;

xa=0; //start time xb=10;//stop time ya=100;//start dac value yb=2340;//stop dac value

int dx,dy,x,y,s1,s2,e,temp,swap,i; int xprec;

xprec=xa-1;

dy=abs(yb-ya); dx=abs(xb-xa); s1=sign(xb-xa); s2=sign(yb-ya); x=xa; y=ya; if (dy>dx) { temp=dx; dx=dy; dy=temp; swap=1; } else swap=0; e=2*dy-dx; for(i=1;i=0) { if (swap==1) x+=s1; else y+=s2; e-=2*dx; } if (swap==1) y+=s2; else x+=s1; e+=2*dy; } x++; printf("DAC value at t=%3d : %3d\n",x,y);

return 0; }

Exemples of output :

10 time steps, DAC from 2340 to 2337 DAC value at t= 0 : 2340 DAC value at t= 1 : 2340 DAC value at t= 2 : 2339 DAC value at t= 3 : 2339 DAC value at t= 4 : 2339 DAC value at t= 5 : 2338 DAC value at t= 6 : 2338 DAC value at t= 7 : 2338 DAC value at t= 8 : 2338 DAC value at t= 9 : 2337 DAC value at t= 11 : 2337

Nice, isn't it ?

Robert Lacoste - ALCIOM : The mixed signals experts

"Neil Bradley" a écrit dans le message de news: snipped-for-privacy@corp.supernews.com...

killing

CPU

Hmm. Some notes:

(1) Where did "t=10" go in the second group?

(2) The 'while(e>=0)' can be replaced with 'if(e>=0)', as it either takes place, or not, but a single subtraction is always sufficient for 'e'.

(3) The problem with the algorithm is that the for() loop will continue over and over and over for long stretches before (x!=xprec), when the DAC values are widely separated (which may often be the case) as compared with the time tick. The loop continues until 'x' changes and this may be a while.

And worse, still, it will happen just about every time, too. Once you pay the price, you pay it again and again.

I don't think this will save the OP anything over the single division at the beginning that he's stuck with, now. The looping is worse, I suspect, than the problem it is supposed to solve.

This is why I didn't comment earlier about his problem. I recognized that this isn't just a simple hack of Bresenham, to fix the slow timing. Bresenham flips everything in the first 45 degrees, switching independent variables around. This is great for drawing pixels and it avoids the need for division because of limiting the range to TAN(angle)

Neil, it's a modification of Bresenham to repress output while the dependent variable remains unchanged. Brute force and probably what Kelly was hinting at. It will loop once for each DAC count it is skipping past. And you will pay that loop for each time step. It will probably eat up your CPU time more than the single division at the outset, unless your DAC values have a rather limited range of change.

Jon

(4) At t=1 in your first group, the DAC output value is 212. This is a step of 112. At t=2, the DAC value is 436 -- a step of 224. It's smoother, later on. A similar thing happens at the end, as well. This is a natural consequence of Bresenham, but it's a little odd for a DAC drive.

:)

Yeah, I noticed that when I coded it up. But using up cumulatively MORE time over a period of time is OK. And it's really not that bad - about 10-20usec each step. I just need faster response, so this is just what the doctor ordered for my particular application.

-->Neil

Well, if I understand your "10-20us" statement, it's per iteration. If you are stepping from DAC=200 to DAC=3000 in say

Just keep it in mind.

Jon

time

It's using 30usec every millisecond since my timer resolution is set to 1ms. So it may eat up a lot of CPU time, but it'll be over a long period.

-->Neil