0

Code for division by 9 in fixed point.

  1. q = 0;              // quotient
  2. y = (x << 3) - x;   // y = x * 7
  3. while(y) {          // until nothing significant
  4.   q += y;           // add (effectively) binary 0.000111
  5.   y >>= 6;          // realign
  6. }
  7. q >>= 6;            // align

Line 2 through 5 in the FIRST execution of while loop is effectively doing
x*.000111 (in decimal representation x*0.1), what it is trying to achieve in subsequent while loops?

Should it not be again multiplying that with 7 and again shifting instead of doing only shifting to take care of recurrence?

Explanation with respect to plain decimal number multiplication as to what is being achieved with only shifting would be nice.

Detailed code explanation here: Divide by 9 without using division or multiplication operator

Community
  • 1
  • 1
newbie_old
  • 500
  • 5
  • 19
  • It's airway explained in the answer there; why do you need another explanation? – Oliver Charlesworth Jun 02 '15 at 07:36
  • @OliverCharlesworth: I wanted to ask more questions there but it was getting long and so i created this one. I thought the discussion was going to fixed point and that is why this question. – newbie_old Jun 02 '15 at 07:37
  • "*what is being achieved with only shifting*" Is that your actual question? – Eregrith Jun 02 '15 at 07:44
  • @Eregrith: yes and why not multiplying and shifting again? I would also appreciate if multiplication with decimal is given as an example to illustrate the shifting point. – newbie_old Jun 02 '15 at 07:47
  • You need to familiarise yourself with infinite series. For example, (1/4) + (1/4)^2 + (1/4)^3 + (1/4)^4 + (1/4)^5 ... = 1/3. These infinite series correspond to repeating patterns in binary (when the terms are powers of 2). Understand the division by 3 example first and then you will understand division by 9 – samgak Jun 02 '15 at 08:10

2 Answers2

2

Lets denote 7/64 by the letter F. 7/64 is represented in binary as 0.000111 and is very close to 1/9. But very close is not enough. We want to use F to get exactly to 1/9. It is done in the following way

F+ (F/64) + (F/64^2) + (F/64^3) + (F/64^4)+ (F/64^5) + ...

As we add more elements to this sequence the results gets closer to 1/9 Note each element in the sequence is exactly 1/64 from previous element.

A fast way to divide by 64 is >>6

So effectively you want to build a loop which sums this sequence. You start from F and in each iteration do F>>6 and add it to the sum. Eventually (after enough iterations) the sum will be exactly 1/9.

Ok now, you are ready to understand the code. Instead of using F (which is a fraction and cannot be represented in fixed points) the code multiplies F by x. So the sum of the sequence will be X/9 instead of 1/9 Moreover in order to work with fixed points it is better to store 64*X*F and the result would by 64*X/9.

Later after the summation we can divide by 64 to get the X/9

The code stores in the variable y the value of F*x*64

variable q stores the sum of the sequence. In each loop iteration we generate the next element in the sequence by dividing the previous element by 64 (y>>=6)

Finally after the loop we divide the sum by 64 (q>>=6) and get the result X/9.

Regarding you question. We should not multiply by 7 each time or else we will get a sum of the sequence of

F+ (F^2) + (F^3) + (F^4) + (F^5)...

This would yield a result of ~X/(8+1/7) instead of X/9.

DanielHsH
  • 4,287
  • 3
  • 30
  • 36
  • I got your explanation as to the shifting. Just one last doubt you said we are multiplying initially by 64 "The code stores in the variable y the value of F*x*64". I don't see we are multiplying initially by 64. – newbie_old Jun 02 '15 at 08:08
  • I think i understood what you meant. Basically initially in the 0.000111 recurrence we considered only 6 numbers after decimal point which is same as representing everything in q6 format(6 bits reserved for fractional part). So after multiplication we right shift it by 6 so that the result can be represented in q6 format right? I will up vote this as right answer after your comment. – newbie_old Jun 02 '15 at 08:36
  • 1
    I edited my answer to address your remark in the comment. See the Explanation: F*x*64 = (7/64)*x*64 = 7*x = 8*x-x = (x<<3)-x. And yes, you are correct. Each time we add the next six digits after the decimal point. Thus effectively after N iterations we have a more accurate binary representation of 1/9 using 6*N digits after the decimal point – DanielHsH Jun 02 '15 at 08:47
1

Shifting by one to the left multiplies by two, shifting by one to the right divides by two. Why?

Shifting is the action of taking all the bits from your number and moving them n bits to the left/right. For example:

00101010 is 42 in Binary
42 << 2 means "shift 42 2 bits to the left" the result is
10101000 which is 168 in Binary
we multiplied 42 by 4.

42 >> 2 means "shift 42 2 bits to the right" the result is
00001010 which is 10 in binary (Notice the rightmost bits have been discarded)
we divided 42 by 4.

Similarly : (x << 3) is x * 8, so (x << 3) - x is (x * 8) - x => x * 7

Eregrith
  • 4,263
  • 18
  • 39