Clarification for problem 4.6 - Compute x/y

#1

Hi, I am stuck for some days trying to understand the algorithm behind the problem 4.6 (Java version).
Sorry if this sounds to be a basic question but unfortunately I didn’t understand the principle adopted.

I’m trying to understand the paragraph:

  • “A better approach is to try and get more work done in each iteration. For example, we can compute the largest k such that 2^k * y <= x, subtract 2^k * y from x, and add 2^k to the quotient. For example, if x = (1011)2 and y = (10)2, then k = 2, since 2 * 2^2 <= 11 and 2 * 2^3 > 11. We subtract (1000)2 from (1011)2 to get (11)2, add 2^k = 2^2 = (100)2 to the quotient, and continue by updating x to (11)2”

I’m trying to replicate this logic step by step but I must be missing something …:

  1. We’re trying to divide 11/2 so x=11 and y=2

  2. The paragraph states that 2^k * y <= x, so I’m doing the following:
    for k=0, 2^0 * 2 = 2       2 <= 11 (true)
    for k=1, 2^1 * 2 = 4       4 <= 11 (true)
    for k=2, 2^2 * 2 = 8       8 <= 11 (true) <-- The largest value of k is 2
    for k=3, 2^3 * 2 = 16    16 <= 11 (false)

  3. "We subtract (1000)2 (decimal 8) from (1011)2 (decimal 11)"
    8-11=-3 (11)2 <-- Probably the negative sign is being discarded, result = 3

  4. "add 2^k = 2^2 = (100)2 to the quotient…"
    I “think” the quotient is k and k=2, so I need to perform:
    2^k + k => 2^2 + 2 => 4 + 2 = 6, for sure there is something wrong here because the value is 6

  5. The last phrase is “and continue by updating x to (11)2” … unfortunately I have no idea of what I need to perform here :frowning:

Appreciate any help
Marcos

0 Likes
#2

Consider Step 3 to 5 with some minor modifications
3. It should be remainder=11-8=3
4. 2^k is the quotient from Step 3. So quotient += 2^k (no k!), and accumulate everytime
5. Perform Step 3 and Step 4 on the remainder from previous Step 3 (remainder=3), until remainder is less than y

0 Likes
#3

Hi thank your for your help. But I’m still not able to make it … Let’ say:

Step 3: 11-8 = 3 [Ok understood]
Step 4:
Step 4.1 (first theory)
2^3 <= 11 [true] * 1 time
2^4 <= 11 [false]

 One possible result would be the sum of the quotient obtained in the step 2, 2^2=4 and compute
 the sum of 4+(1 time) = 5. This seems to be wrong ....

Step 4.1 (second theory)
for k=0  2^0=1  1<= 3   [true]
for k=1  2^1=2  2<= 3   [true]
for k=2  2^2=4  4<= 3   [false]

Another possible result would be the sum of the quotient obtained in the step 2, 2^2=4 and 
compute 4+k => 4+1=5. Don't know if this is right too ....

If I try to apply the same process for another expression like 130/7 I’ll get:

Step 1: We’re trying to divide 130/7 so x=130 and y=7

Step 2: The initial quotient will be obtained with 2^k * y <= x, so:
for k=0, 2^0 * 7 = 7 7 <= 130 (true)
for k=1, 2^1 * 7 = 14 14 <= 130 (true)
for k=2, 2^2 * 7 = 28 28 <= 130 (true)
for k=3, 2^3 * 7 = 56 56 <= 130 (true)
for k=3, 2^4 * 7 = 112 112 <= 130 (true) <-- The largest value of k is 6
for k=3, 2^5 * 7 = 224 224 <= 130 (false)

Step 3: We subtract 130-112 = 18 [Ok]

Step 4: I’ll try the second theory
Step 4.1 (second theory)
for k=0 2^0=1 1 <= 18 [true]
for k=1 2^1=2 2 <= 18 [true]
for k=2 2^2=4 4 <= 18 [true]
for k=3 2^3=8 8 <= 18 [true]
for k=4 2^4=16 16 <= 18 [true]
for k=5 2^5=32 32 <= 18 [false]

Could someone shed some light? I’m really missing something from the explanation…

Thank you very much!

0 Likes
#4

I’m stuck on the same problem, did you figure it out?

0 Likes
#5 
Okay I figured it out

marcoshass I would suggest going through examples with smaller numbers, here I'll go through 11/2

First they show us a brute force, then a better technique and then lastly a way to optimize that technique to avoid O(n^2) runtime. I will skip the brute force and for now ignore the optimization part.

Compute X/Y, where X=11 Y=2

1.) Find largest k s.t, (2^k)*y <= X
In english, Using left shifts, make the denominator as large as possible without surpassing the numerator.
In this case, we have to do 2*(2^k), where k = 2. This  gives us 8. Any further left shifts and the number would be bigger than X.

2.) X = X - (2^k)*Y
In our case, X = 11 - (2^(2))*(2) = 11 - 8 = 3 

3) result += 2^(k)
In our case, result started at 0 and is now at 0+2^(2) = 4

How do we know we're done? Well, X will keep decreasing in every iteration, once X gets below Y, in integer division the result would always be zero so that's when we stop. If you had something like 11/3, you would have 2 iterations.

Once you understand this part, the remaining parts should be easier.

Also if you think about what division actually means, X/Y = q means that I can remove q Ys from X. ie 10/2 = 5 means that I can remove 2 5s from 10.

In the brute force solution we were doing this linearly, just removing them one at a time. In the optimized solution, instead of using subtraction, we’re using left shift

Hope that helps!

0 Likes
#6

Hi thatguy thank you very much for your help!

Unfortunately I’m still struggling really hard to figure out how the theory behind this solution works … Below I’ll try to demonstrate where I’m stuck:

Let’s take for example a bigger division, such as x = 100 and y = 3. The first part is really simple, I just have to find 2^k*2 that’s less than or equal to 100. I understood this part, the authors used left shift because they tried to find the largest k without too many iterations.

for k=0 => 2^0*2 = 2 <= 100
for k=1 => 2^1*2 = 4 <= 100
for k=2 => 2^2*2 = 8 <= 100
for k=3 => 2^3*2 = 16 <= 100
for k=4 => 2^4*2 = 32 <= 100
for k=5 => 2^5*2 = 64 <= 100
for k=6 => 2^6*2 = 128 <= 100 => [False, get the previous k]

So we found k=5, and if we make 100 - (2^5*2) => 100-64 = “36” We will get thirty six.
From beyond this point I didn’t understand what needs to be done … Clearly we have to do something with the “36” remaining but I’m still unsure what to do :frowning:

Appreciate any help!

0 Likes
#7

Hi marcoshass here’s how it could be done with x = 100 and y = 3

Theory:
The key thing to understand is how to mathematically represent a series of left shifts. For example if I left shift y once, it will be 2y, another left shift and it will be 4y, then 8y, etc. I could also write out these left shifts as (2^k)y where k is the number of left shifts. This form makes it easier to iterate over the values 2y, 4y, 8y, etc.

Example:

First iteration
X=100, Y=3
finding largest k s.t (2^k)*y <= x
for k=5 =>(2^5)(3) = 96
X = 100-96 = 4
We’ve just discovered that we can increase our original denominator by a factor of 2^5 while still having X/Y be greater than 1. However, 100-96=4 and 4>3, as long as X>Y, it’s possible to remove at least one more X from Y.

Next iteration
X=4, Y=3
finding largest k s.t (2^k)*y <= x
for k=0 => (2^0)(3) = 3
X=4 - 3 = 1
Now we know for the remaining part, it’s possible to remove (2^0) X from Y.

Calculating the result:
In each iteration we should be accumulating the result which is a similar idea as the brute force solution; we want to know how many times can we remove an entire X from Y.
In the first iteration we determined that we could increase X by a factor of 2^5 and in the second iteration it was 2^0.
2^5 + 2^0 = 32 + 1 = 33.

Let me know if that makes sense.

0 Likes