# 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

•  Subject
• Author
• Posted on
Re: Turn a divide into a multiply
On Sun, 03 Aug 2003 23:06:28 GMT, Jonathan Kirwan

Sorry, that should be 33 cycles per loop, not 38.  So this means

Jon

Re: Turn a divide into a multiply

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

Digital differential analysis and recurrences.

Jon

Re: Turn a divide into a multiply

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"

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

<snip>

:)

Re: Turn a divide into a multiply

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

Re: Turn a divide into a multiply

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

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

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.