Tuesday 24 February 2015

Remainder on division - methodology

So how do we go about creating a program on the fx-50F which can calculate the remainder on dividing one integer by another? Let's go back to the example of dividing 4593 by 7. We can write this number as

4593=4000+500+90+3=4x1000+5x100+9x10+3x1

Suppose we want to calculate the remainder of 90 on division by 7. We find that 90=12x7+6 and so the remainder is 6. Alternatively we could have seen that 9=1x7+2 and 10=1x7+3 and 2x3=6. This means that we could have found the remainder we wanted by multiplying the remainders of dividing 9 and 10 by 7. A similar rule applies for addition. Suppose we want the remainder when 590 is divided by 7. This is 2 since 590=84x7+2. However, 500=71x7+3 and, as we have just seen, 90=12x7+6 and 3+6=9 and 9=1x7+2. The moral of this is that we don't have to divide the complete number 4593 by 7 but divide it in parts and work with remainders.

So how do we proceed in a way which makes it easy for a programmable calculator? Let's start with the right-most digit 3 and record the power of 10, namely 0, that goes with it. 10 to the power 0 is 1 and 1 divided by 7 leaves remainder 1 (since 1=0x7+1). 3 divided by 7 leaves remainder 3 (again since 3=0x7+3). Multiplying remainders gives 3x1=3.

Now before going on to the next digit to the left, 9, we note that the powers of 10 that go with each digit increase by 1 for each new digit we encounter. For example 1000=10x100. So rather than calculate the remainder of 1000 divided by 7 we multiply the remainder of 10 divided by 7 (i.e. 3) and the remainder of 100 divided by 7 (i.e. 2) that we calculated previously. So corresponding to the powers of 10 of 0, 1, 2, 3, ... the remainders are 1, 3, 3x3=9 which is 2, 3x2=6, etc.

Now going on to the next digit 9 we have 9 divided by 7 leaves remainder 2 and as, we have seen, the remainder for 10 divided by 7 is 3 and so 2x3=6. Adding this to the remainder for the first digit gives 6+3=9 and 9 divided by 7 leaves remainder 2.

The next digit is 5 and 5 divided by 7 leaves remainder 5. The factor of 100 divided by 7 leaves remainder 2 and 5x2=10. 10 divided by 7 leaves remainder 3 and adding this to the remainder for our first two digits gives 3+2=5.

Finally, the last digit is 4 and 4 divided by 7 leaves remainder 4. The factor of 1000 divided by 7 leaves remainder 6 (as we discussed above) and 4x6=24. 24 divided by 7 leaves remainder 3 and adding this to the remainder for our first three digits gives 5+3=8 and 8 divided by 7 leaves remainder 1. This is our final result, that is 4593 divided by 7 leaves remainder 1, as expected.

This may seem like a tedious way of going about things, but with a pocket programmable calculator the digits can be entered one by one and the time to compute the intermediate remainders is very quick and hardly interferes with the input process. The advantage is that this keeps the size of the computations down to manageable amounts and allows an integer of indeterminate length to be entered and divided (the limit being only how long before you get bored of keying in digits!).

No comments:

Post a Comment