Author Topic: Coding Challenges  (Read 12306 times)

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4952
Coding Challenges
« Reply #50 on: November 17, 2006, 04:57:02 PM »
I'm gonna prod this thread a little since it seems to have been forgotten about.

I'm gonna answer the last bonus part to question #12. I figure if the bonus hasn't been answered by now then it's no longer up for grabs.  :o

The main part of question #12 is to find a way to divide by some odd constant b, when we know the number we are dividing is a multiple of b. The bonus is to extend this method to handle the case when b is even.

Suppose b is even. Then b = (2^k) * (b'), where b' is odd, and k >= 1. That is, we take out all the factors of 2 from b, until there are none left.

Now, a/b = a / ((2^k)*(b')).

Note: a/b = (a / (2^k)) / (b') = (a / (b')) / (2^k).
What that last line says, is that we may either divide by 2^k first, and then by b', or we can divide by b' first, and then by 2^k. They are equivalent.

Also note that since b' is odd, and if b divides a where b = (2^k) * (b'), then both b' divides a and 2^k divides a. Thus in either case, the remainder after division is 0. What this is saying, is that the answer to question #12 can be applied to do the division by b'. It's also easy to see that we can divide by 2^k without worrying about inexact division.

I'm sure you've all figured by now, shift 'a' right k places to perform the division by 2^k. Use the method that's the answer to question #12 to perform the division by b'. We can do these in any order by the above. We now have a/b.

The total cost of performing this, is the cost of performing the division by b', which according to the challenge rules is no slower than a divide instruction, plus the cost of performing the shift instruction. It might end up being more than the cost of a divide instruction, but not by much. On older architectures where the divide instruction is much slower than most other instructions, this should be faster.

I should mention that to perform the shift to divide by 2^k, we need to know if we are working with signed or unsigned values (for the value 'a' anyways). The first bonus is showing the other part, division by an odd b can be done correctly without knowing if signed or unsigned values are being used. Note that the bonus was for the original question, and not for the second bonus asked later, where b can be even.

I will provide hints to the answer upon request (but in this thread only, not by PM).

And Whitehead, sure you don't want to answer at least part of question #13? I'm pretty sure you've got the answer to most of it.