Q2. Using the optimized Division on method (See document below question), solve

Question

Q2. Using the optimized Division on method (See document below question), solve the following multiplication problems. Assume 4 bit registers, and an 8 bit ALU. Show the steps performed as done in the supplemental hand out.

a) 48 / 4 =

b) 80 / 8 =

Steps for Refined Multiplication

Initialize:

Product = all 0’s

Set Low bits of Product to be the value of the multiplier

Steps

0.If the 0th bit of the product is a 1, add Multiplicand to the High bits of Product.

1.Shift the Product to the right

2.Repeat 0 and 1 until the original multiplier bits are shifted out of the Product field.

Ex:

Manual

    1010 (10) x         1001 (9 )

                        1010           

         0000

                    0000

               +    1010     

                    1011010       (90)

Refined Multiplier

Multiplicand: 1010 Multiplier:      1001

Product:       1001 1010

               Multiplicand    Product        Notes

Initialize     1010            0000 1001

Step 1.0 1010   1010 1001 0th product bit = 1 (0000 + 1010 = 1010) Step 1.1 1010   0101 0100 Shift right 1

Step 2.0       1010            0101 0100      0th product bit = 0

Step 2.1       1010            0010 1010      Shift right 1

Step 3.0       1010            0010 1010      0th product bit = 0

Step 3.1       1010            0001 0101      Shift right 1

Step 4.0 1010   1011 0101 0th product bit = 1 (0001 + 1010 = 1011) Step 4.1 1010   0101 1010 Shift right 1

Product: 0101 1010

Steps for Optimized Divider

Initialize:

                  Remainder= Dividend

Steps

0.Subtract the divisor from the high order bits of the remainder. If positive, replace the high order bits with the result, add a 1 to the right of the remainder. If negative, add a 0 to the right of the remainder.

1.Shift the Remainder to the left

2.Repeat 0 and 1 until the original dividend bits are shifted out of the Low order remainder bits field.

Ex:

Manual

          0000 1010            10    1001 | 0101 1010      9 | 90

0100 1

          0001 001

1 001

             0 0000

Optimized Divider

Divisor: 1001

Dividend: 0101 1010

Quotient: 1010

                 Divisor Remainder        Notes

Initialize     1001      0101 1010

Step 1.0       1001      0101 1010 0     0101 – 1001 = ( < 1) add a 0

Step 1.1       1001      1011 0100      Shift left 1

Step 2.0       1001      0010 0100 1 1011 – 1001 = 0010 (> 1) add a 1, replace high bits

Step 2.1       1001      0100 1001      Shift left 1

Step 3.0       1001      0100 1001 0     0100 – 1001 = ( < 1) add a 0

Step 3.1       1001      1001 0010      Shift left 1

Step 4.0       1001      0000 0010 1    1001 – 1001 =0000 (> 1) add a 1, replace high bits

Step 4.1       1001      0000 0101      Shift left 1

Step 5.0       1001      0000 0101 0     0000 – 1001 = ( < 1) add a 0

Step 5.1       1001      0000 1010      Shift left 1

Quotient: 1010

Explanation / Answer

range 0 -> 768

you may use shifting of 10 bits, which multiplying via 1024, you need to divide via three so your multiplier have to be 1024 / three = 341,

so that you can now use (x * 341) >> 10
(make sure the shift is a signed shift if the use of signed integers), also make certain the shift is an sincerely shift and no longer a chunk ROLL

this can efficaciously divide the price three, and will run at about 1.6 instances the speed as a herbal divide via 3 on a fashionable x86 / x64 CPU.

Of path the simplest cause you could make this optimization while the compiler cant is due to the fact the compiler does not understand the maximum range of X and therefore cannot make this dedication, but you as the programmer can.

sometime it could even be extra useful to move the value into a larger cost and then do the equal issue, ie. if you have an int of full variety you can make it an 64-bit price and then do the multiply and shift in preference to dividing by way of three.

I had to try this lately to hurry up photo processing, i had to locate the average of 3 colour channels, every color channel with a byte range (0 - 255). red green and blue.

before everything i simply genuinely used:

avg = (r + g + b) / three;

(So r + g + b has a maximum of 768 and no less than zero, due to the fact each channel is a byte 0 - 255)

After tens of millions of iterations the complete operation took 36 milliseconds.

I modified the road to:

avg = (r + g + b) * 341 >> 10;

And that took it right down to 22 milliseconds, its exceptional what can be executed with a little ingenuity.

This speed up passed off in C# despite the fact that I had optimisations became on and turned into walking this system natively without debugging data and now not thru the IDE.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.