In my previous post I presented some logic for obtaining the remainder when a number like 4593 is divided by 7. I now want to go through how this logic works.
Some initial values are first stored in memory locations B, C and D and the use of these memories is explained as we go along. The divisor (in our example 7) is input in memory A and remains fixed. Memory D contains the common factor of 10 in our process and the first while loop finds the remainder when 10 is divided by 7 and the result, 3, is stored in D.
The first digit of our number (in our example this is 3) is input after label 1. Essentially this is the main loop of our program. The digits of 4593 are entered reading from right to left and when the last digit has been read, the process is terminated by entering -1 in X.
Each digit is processed as follows. Firstly, the initial while loop determines the remainder on dividing X by A. For the first digit in our example this is the remainder on dividing 3 by 7 (which is 3). Each time we process a new digit of our number 4593 we add to memory C the product of X (the remainder on dividing our digit by 7) and the remainder on dividing the power of 10 by 7 stored in B. For example, for the third digit 5, B at this stage would contain the remainder on dividing 100 by 7, namely 2. We then calculate the remainder on dividing C by A in the following while loop.
Finally, before going on to input the next digit we calculate the remainder on dividing the next power of 10 by A.
When the last digit has been processed, the required remainder in C is displayed.
Friday 27 February 2015
Wednesday 25 February 2015
Remainder on division - the logic
In my previous post I described a method for calculating the remainder on dividing one integer by another. I now give the logic that can
be used to solve this problem on a programmable calculator.
Store 1 in B
Store 0 in C
Store 10 in D
Input A
While D ≥ A
Store D-A in D
WhileEnd
Label 1
Input X
If X=-1 then
Goto Label 2
EndIf
While X ≥ A
Store X-A in X
WhileEnd
Store C+BX in C
While C ≥ A
Store C-A in C
WhileEnd
Store DB in B
While B ≥ A
Store B-A in B
WhileEnd
Goto Label 1
Label 2
Display C
Store 1 in B
Store 0 in C
Store 10 in D
Input A
While D ≥ A
Store D-A in D
WhileEnd
Label 1
Input X
If X=-1 then
Goto Label 2
EndIf
While X ≥ A
Store X-A in X
WhileEnd
Store C+BX in C
While C ≥ A
Store C-A in C
WhileEnd
Store DB in B
While B ≥ A
Store B-A in B
WhileEnd
Goto Label 1
Label 2
Display C
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!).
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!).
Thursday 19 February 2015
Remainder on division
One function that appears to be missing from the fx-50F Plus is finding the remainder when one integer is divided by another. For example, what is the remainder when 4593 is divided by 7, or putting this another way, what is 4593 congruent to modulo 7? The fx-50F does have the ability to calculate fractions and if you key in 4593 [a b/c] 7 [EXE] you obtain 656_1_7 which shows that 4593=656x7+1, that is the remainder when 4593 is divided by 7 is 1. Equivalently 4593 is congruent to 1 modulo 7. You have to be wary that if your divisor is not prime, then you may have to adjust the numerator of your fraction accordingly to obtain the correct remainder. For example, if you enter 4593 [a b/c] 21 [EXE] you obtain 218_5_7. Here the remainder is not 5 but 5x3=15 since the denominator is 7, not 21, in the resulting fraction. You need to multiply the fraction 5/7 top and bottom by 3 to get the correct result, that is 4593=218x21+15.
An alternative method is, of course, to carry out the division in decimals 4593/7=656.1428571. If you then take this number, subtract 656 and multiply by 7 you obtain remainder 1. This seems simple enough. But what happens if you want to do division on very large numbers? It all starts to get a bit messy and inaccurate, partly because of the number of digits that the fx-50F can accurately hold and partly because only ten digits are displayed on the screen.
For example, Edouard Lucas had shown in 1876 that the number 267-1 =147,573,952,589,676,412,927 is not prime but no one knew what its factors were. In 1903 Frank Nelson Cole (1861-1926) famously gave a presentation to the American Mathematical Society where he proceeded to calculate, in silence, 267-1 on side of the blackboard and then, on the other, the result, by hand, of 193,707,721 × 761,838,257,287. Cole, having demonstrated that the two numbers were equal, sat down, not uttering a word. He received a standing ovation!
What I would like to do is to demonstrate that we can show that either of these factors will divide this number by creating a program that will calculate that the remainder on division is zero. Furthermore, this program will cope with a natural number of any length (though, the divisor will have to less than the largest positive integer that the calculator can accurately hold).
An alternative method is, of course, to carry out the division in decimals 4593/7=656.1428571. If you then take this number, subtract 656 and multiply by 7 you obtain remainder 1. This seems simple enough. But what happens if you want to do division on very large numbers? It all starts to get a bit messy and inaccurate, partly because of the number of digits that the fx-50F can accurately hold and partly because only ten digits are displayed on the screen.
For example, Edouard Lucas had shown in 1876 that the number 267-1 =147,573,952,589,676,412,927 is not prime but no one knew what its factors were. In 1903 Frank Nelson Cole (1861-1926) famously gave a presentation to the American Mathematical Society where he proceeded to calculate, in silence, 267-1 on side of the blackboard and then, on the other, the result, by hand, of 193,707,721 × 761,838,257,287. Cole, having demonstrated that the two numbers were equal, sat down, not uttering a word. He received a standing ovation!
What I would like to do is to demonstrate that we can show that either of these factors will divide this number by creating a program that will calculate that the remainder on division is zero. Furthermore, this program will cope with a natural number of any length (though, the divisor will have to less than the largest positive integer that the calculator can accurately hold).
Subscribe to:
Posts (Atom)