Division Method: Reciprocal Multiplication

feiutm9898 · 2009-05-12 13:55:25

I would like to know if there is any method faster that Reciprocal Multiplication.

I know that we need to know the divisor in advance before proceeding Reciprocal Multiplication.

Please let me know.

Identity · 2009-05-12 20:42:43

What is Reciprocal Multiplication? Can you give an example?

feiutm9898 · 2009-05-12 21:58:03

For example a/b a is integer, b is integer

a/b = a x 1/b , we call this reciprocal multiplication.

bobbym · 2009-05-13 02:31:40

Hi feiutm9898

So you are trying to implement a division routine that doesn't use reciprocal mult. This used to be necessary because many early processors did not have a multiply or divide instruction. Years back, when we were writing our own CAS, we researched this particular problem. The Knuth books are the best place to begin. There might be something slightly faster, but we ended up using the recip. mult method with newtons iteration. It was very fast, but picking an initial value can be a pain (this problem can be solved too).

Last edited by bobbym (2009-05-13 02:34:58)

feiutm9898 · 2009-05-13 13:56:50

Dear bobbym,

Would you mind giving me a example that uses "recip. mult method with newtons iteration"?

For example, 20/4?

bobbym · 2009-05-13 17:56:01

Hi feiutm9898;

I might be able to recreate my rather naive method but this page contains everything I know about it plus a lot more.

http://en.wikipedia.org/wiki/Division_(digital)

Half way down the page you will see how newtons iteration creates a recurrence with quadratic convergence (fancy term - means roughly doubling the number of correct digits per iteration). They may have solved my problem of getting a good initial guess ( If I remember I would use the software divide instruction that C++ provides to prime the recurrence). Newtons method is sensitive to the initial guess so you want to get close. Let me know how much of this you can use.

feiutm9898 · 2009-05-13 19:06:57

Hi,

Thanks for the information.

I found the explanation at http://www.docstoc.com/docs/2844296/ARM-System-Developers-Guide

This book is about embedded processor. Page 225 explains how 'Unsigned 32/32-bit Divide by Newton-Raphson" and it takes >36 cycles.

bobbym · 2009-05-13 19:09:06

Hi feiutm9898;

Thanks for providing me with that. Cool, an implementation in assembly,

Last edited by bobbym (2009-05-13 19:11:10)

robinbolt · 2010-12-07 18:35:46

thnx for telling some thing new... i am a student and want to learn more and more...is there any method faster for division for big amounts???

bobbym · 2010-12-07 18:58:32

Hi robinbolt;

Faster than these:

http://en.wikipedia.org/wiki/Division_(digital)

I do not know of any. Also you would have to work in multiprecision.

And welcome to the forum!

Math Is Fun Forum

#1 2009-05-12 13:55:25

Division Method: Reciprocal Multiplication

#2 2009-05-12 20:42:43

Re: Division Method: Reciprocal Multiplication

#3 2009-05-12 21:58:03

Re: Division Method: Reciprocal Multiplication

#4 2009-05-13 02:31:40

Re: Division Method: Reciprocal Multiplication

#5 2009-05-13 13:56:50

Re: Division Method: Reciprocal Multiplication

#6 2009-05-13 17:56:01

Re: Division Method: Reciprocal Multiplication

#7 2009-05-13 19:06:57

Re: Division Method: Reciprocal Multiplication

#8 2009-05-13 19:09:06

Re: Division Method: Reciprocal Multiplication

#9 2010-12-07 18:35:46

Re: Division Method: Reciprocal Multiplication

#10 2010-12-07 18:58:32

Re: Division Method: Reciprocal Multiplication

Board footer