- #1

- 15

- 0

Both conceptually and computationally it is easier to see that

2.5 * 5.2 = 13

than it is to see

13 / 5.2 = 2.5

In programming too: division loops take more CPU resources than multiplication loops.

Why is this?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter devinedj
- Start date

- #1

- 15

- 0

Both conceptually and computationally it is easier to see that

2.5 * 5.2 = 13

than it is to see

13 / 5.2 = 2.5

In programming too: division loops take more CPU resources than multiplication loops.

Why is this?

- #2

- 806

- 23

- #3

coolul007

Gold Member

- 265

- 7

- #4

jbriggs444

Science Advisor

Homework Helper

- 9,743

- 4,350

In the naive implementation, both loops have roughly the same complexity.

For multiplication you test a bit, conditionally add and then shift.

For division you subtract, test the result, conditionally set a bit and then shift.

On average, that means one subtraction per bit position for division and one half of an addition per bit position for multiplication.

However, there are better algorithms than the naive ones. The guys that do this stuff for a living have very clever tricks at their disposal.

- #5

coolul007

Gold Member

- 265

- 7

In the naive implementation, both loops have roughly the same complexity.

For multiplication you test a bit, conditionally add and then shift.

For division you subtract, test the result, conditionally set a bit and then shift.

On average, that means one subtraction per bit position for division and one half of an addition per bit position for multiplication.

However, there are better algorithms than the naive ones. The guys that do this stuff for a living have very clever tricks at their disposal.

I am speaking of hardware cpu implementation, not algorithm software implementation. Unfortunately all we have is adders. They shift and add. if there is a clever guy out there he could be a billionaire. subtraction involves complementing and then adding, a two step process.

- #6

rcgldr

Homework Helper

- 8,749

- 553

Multiplication doesn't have to be iterative, all the sub-products can be generated in parallel, and then all the sub-products are added. Computers can have circuits that directly implement subtract without using complement. For division, even if there is a complement, it's only done once. As far as I know, division is an iterative process, although tables for the most significant bits can be used to speed up the process. Taking the inverse (1/x) of a number (which can be optimized) and multiplying can be faster. Wiki articles:I am speaking of hardware cpu implementation, not algorithm software implementation. Unfortunately all we have is adders. They shift and add. if there is a clever guy out there he could be a billionaire. subtraction involves complementing and then adding, a two step process.

http://en.wikipedia.org/wiki/Binary_multiplier

http://en.wikipedia.org/wiki/Binary_numeral_system#Division

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

- #7

coolul007

Gold Member

- 265

- 7

Multiplication doesn't have to be iterative, all the sub-products can be generated in parallel, and then all the sub-products are added. Computers can have circuits that directly implement subtract without using complement. For division, even if there is a complement, it's only done once. As far as I know, division is an iterative process, although tables for the most significant bits can be used to speed up the process. Taking the inverse (1/x) of a number (which can be optimized) and multiplying can be faster. Wiki articles:

http://en.wikipedia.org/wiki/Binary_multiplier

http://en.wikipedia.org/wiki/Binary_numeral_system#Division

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

Read the article, first sentence, "it uses binary adders", binary adders are the building blocks of hardware mathematics.

- #8

rcgldr

Homework Helper

- 8,749

- 553

- #9

coolul007

Gold Member

- 265

- 7

"Subtractors are usually implemented within a binary adder for only a small cost when using the standard two's complement notation, by providing an addition/subtraction selector to the carry-in and to invert the second operand."

I suspect there is no implementation of this in cpu's as there are no references listed.

- #10

rcgldr

Homework Helper

- 8,749

- 553

I don't know how

I suspect there is no implementation of this in cpu's as there are no references listed.

One way to optimize subtract would be to do a ones complement (just inverters on the adder inputs) instead of twos complement to avoid carry propagation on the twos complement operation, then use a full adder on the least significant bit with the carry input bit set to 1, so that the increment part of a two's complement was done as part of the add.

The main point is that multiplication can be implemented as a single but long propagation cycle through a series of sets of gates, while I think division will always require iteration (inverse (1/x) requires some iteration, but less).

Last edited:

- #11

mathwonk

Science Advisor

Homework Helper

2020 Award

- 11,134

- 1,329

- #12

- 483

- 3

Multiplication doesn't have to be iterative, all the sub-products can be generated in parallel, and then all the sub-products are added. Computers can have circuits that directly implement subtract without using complement. For division, even if there is a complement, it's only done once. As far as I know, division is an iterative process, although tables for the most significant bits can be used to speed up the process. Taking the inverse (1/x) of a number (which can be optimized) and multiplying can be faster. Wiki articles:

http://en.wikipedia.org/wiki/Binary_multiplier

http://en.wikipedia.org/wiki/Binary_numeral_system#Division

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

You are right, division is harder. It is hard to explain why. This guy does a pretty good job. I think basically the reason is that you can multiply in parallel but you can't divide in parallel. It's possible to split multiplications into independent steps done in parallel then add the results, but with division each step affects the next so parallelism isn't possible. Or something like that. Memory has faded.

- #13

coolul007

Gold Member

- 265

- 7

Here is a method I discovered several years ago for doing "parallel" division. It is easily implemented in binary hardware, but I doubt it ever will be:

www.ulieulieulie.com/longdiv.html [Broken]

www.ulieulieulie.com/longdiv.html [Broken]

Last edited by a moderator:

- #14

- 30

- 0

Both conceptually and computationally it is easier to see that

2.5 * 5.2 = 13

than it is to see

13 / 5.2 = 2.5

In programming too: division loops take more CPU resources than multiplication loops.

Why is this?

I think (from personal experience) is that to do division you need to be familiar with your multiplication.

- #15

- 773

- 0

Humans are very comfortable with integers and don't deal with decimals nearly as well. Multiplication amongst the integers is closed, division amongst the integers is not. Meaning that you don't have to think about decimals and fractions

- #16

- 2,010

- 288

Here is a method I discovered several years ago for doing "parallel" division. It is easily implemented in binary hardware, but I doubt it ever will be:

www.ulieulieulie.com/longdiv.html [Broken]

The fastest way calculate (x/y) if both numbers are large AFAIK, is to compute (1/y) with newtons method:

if z = (1/y), then f(z) = 1/z -y = 0, and you get

[tex] z_{n+1} = z_n - \frac { f(z_n)} {f'(z_n)} = 2 z_n - y {z_n}^2 [/tex]

z_0 can be a single precision computation of (1/y) by ordinary division.

this contains only two multiplications for each step.

Since the number of digits with each step of the iteration doubles, there won't be many steps, and the full precision is only needed for the last step, the one before that can be 1/2 precisoion, before that 1/4 etc. this takes about as long as 4 full-precision multiplications.

The multiplications can be done with fast fourier transforms wich takes only only O(N log n loglog n) steps for a number with N digits.

Including the final multiplication, division will be about 5 times as slow as multiplying

Last edited by a moderator:

- #17

- 1,679

- 3

Share:

- Replies
- 1

- Views
- 2K