Re: Turn a divide into a multiply - Page 2

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Re: Turn a divide into a multiply
On Sun, 03 Aug 2003 23:06:28 GMT, Jonathan Kirwan

Quoted text here. Click to load it

Sorry, that should be 33 cycles per loop, not 38.  So this means
about 185us per 32x16 division operation, or thereabouts.

Jon


Re: Turn a divide into a multiply
Quoted text here. Click to load it

This strikes me as an odd statement, since the whole point of
Bresenham's algorithm (which comes (approximately) from an era
when LSI meant having a whole four bit counter in one package)
is that it avoids division, ie if it uses division, it's not
Bresenham's

(and this thread is not the only place I've noticed this anomaly)

what is it evolving language? (I suppose you think a byte is 8 bits ;)


And as an aside/question,
isn't there a term applied to these stepwise ratiometric integer
calculations (other than Bresenham style or what ever)?
(there is but it escapes me)


bogax

Re: Turn a divide into a multiply

Quoted text here. Click to load it

Digital differential analysis and recurrences.

Jon


Re: Turn a divide into a multiply

Quoted text here. Click to load it

The OP doesn't know the difference between  Bresenham and incremental
algorithms. I told him he needed to about 20 posts ago in this subthread.


Re: Turn a divide into a multiply
Neil...

I've never used the 8051, but have synthesized division using
multiplication. Can you specify number of bits for divisor and
dividend for me?

Is there a multiply operation that will handle divisor * quotient
as a single operation? What are timings for multiplication
operations? What are maximum multiplier/multiplicand/product sizes?

Is there a hard time requirement for each division or is it
necessary only to achive a sufficiently small average?
--
Morris Dovey
West Des Moines, Iowa USA
We've slightly trimmed the long signature. Click to see the full one.
Re: Turn a divide into a multiply
On Sun, 3 Aug 2003 00:01:57 -0700, "Neil Bradley"

Quoted text here. Click to load it

Zapped it into a simulator tonight, shaved another cycle, and
just tested the 32x16 divide routine using the algorithm I
posted here in C.  Applied a variety of inputs and it always
beats 150us on your 18MHz system and always produces the right
results.  Typically runs in about 144us.  Could be faster with
a-priori information on your inputs, too.

Jon


Re: Turn a divide into a multiply

Quoted text here. Click to load it

<snip>

Quoted text here. Click to load it

:)


Re: Turn a divide into a multiply
Quoted text here. Click to load it

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

Re: Turn a divide into a multiply
Quoted text here. Click to load it
direction.
300usec
End
a

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?



Re: Turn a divide into a multiply
Quoted text here. Click to load it

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

--
Aerosystem Designs
------------------
We've slightly trimmed the long signature. Click to see the full one.
Re: Turn a divide into a multiply
Quoted text here. Click to load it

I jump in late, so maybe re-telling something one of the 40 posts
before did, but

If # of milliseconds is not growing endlessly, why not have a
table of 1/(# of ms) ?
=>
step = abs(DACstart-DACend)*reztab[# of milliseconds]

Getting this table is kinda tricky as you must ignore overflows.
But you can start and see what your compiler (gcc e.g. often uses
reciprokal) gives you for certain values.

---
42Bastian
Do not email to snipped-for-privacy@yahoo.com, it's a spam-only account :-)
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline