Sunday 16 December 2012

gcd by subtraction - the logic

I previously described how it is possible to find the greatest common divisor of two natural numbers by using Euclid's subtraction algorithm. The logic for that algorithm is as follows:-

Label 0
Input A
Input B
If A = B then
   Goto Label 2
EndIf
If B>A then
   Store A in X
   Store B in A
   Store X in B
EndIf
Label 1
Store A-B in C
Store B in X
If X>C then
   Store B in A
   Store C in B
Else
   Store C in A
EndIf
If A is not equal to B then
   Goto Label 1
EndIf
Label 2
Display A
Goto Label 0

This processing carries out the following. The two numbers whose gcd is sought are input as A and B. If A equals B then the gcd(A,B) is simply A (or B) and there is no more work to be done. If B is greater than A, then we swap the values of A and B. Euclid's subtraction algorithm then begins after Label 1. We calculate A-B. If B is greater than A-B then we store B in A and A-B in B otherwise B remains unchanged and we store A-B in A. We repeat the process until A equals B and then we display A and stop the processing. After A is displayed, we then have the otption of returning to the beginning to process another pair of numbers.

Tuesday 11 December 2012

gcd by subtraction

The greatest common divisor (gcd) of two natural numbers is the largest natural number that divides both. For example, the gcd of 72 and 15 is 3 since 3 is the largest number that divides both 72 and 15. We can see this more clearly if determine the prime factors of these two numbers. We have that 72=8x9=2x2x2x3x3 and 15=3x5 and we have only one prime factor, 3, that is common to both.

Euclid came up with a very neat algorithm for finding the gcd of two numbers that is based on subtraction and this algorithm is easy to implement on the fx-50F. Using the above example of 72 and 15 above, the method goes as follows.

Our first pair of numbers is (72, 15) and in each pair we want the first entry to be the larger of the two numbers. To form the next pair we subtract 15 from 72 to give 57 and form the pair (57, 15). We carry on in a similar way obtaining (42,15) and (27, 15). Then subtracting 15 from 27 we get 12 and this is smaller than 15, so they next pair is (15, 12). Then 15 minus 12 is 3 and so we get (12,3), then (9,3), then (6,3) and finally (3,3). When the two pairs of numbers are equal then either number is the gcd of 72 and 15, as we found out above.

I have described the method in more detail in my maths blog.

Thursday 25 October 2012

Is it prime - execution of the program

In a previous post I provided a program for determining whether a number less than 1369 is prime. To show how this works consider the number 431. On running the program the display shows X? This is the number we want to test, so enter 431 and press [EXE]. The display shows Y is 1 indicating that 431 is a prime number (which is the case). Now press [EXE] again and enter 1233 (which is obviously divisible by 3) when the display shows X? On pressing [EXE] the display now shows Y is 0 indicating that 1233 is not prime. Press [EXE] once more and enter 2000 followed by [EXE]. The display now shows Y is 999 and this indicates that the number entered is out of range.

I notice that I haven't included a check to see if the number entered is less than or equal to zero (which would be out of range too) but I leave this as an exercise for the student!

Wednesday 24 October 2012

Is it prime - the program

I discussed the logic for this program in a previous blog. Here is the logic converted into a program for the fx-50F:-


Lbl 0:?→X:If X≥37²:Then 999→Y:Goto 2:IfEnd:X≥11=>Goto 1:
0→Y:X=2=>1→Y:X=3=>1→Y:X=5=>1→Y:X=7=>1→Y:Goto 2:Lbl 1:πX→A:
1→Y:sin(A÷2)=0=>0→Y:sin(A÷3)=0=>0→Y:sin(A÷5)=0=>0→Y:
sin(A÷7)=0=>0→Y:Y=0=>Goto 2:X<121>Goto2:
sin(A÷11)=0=>0→Y:sin(A÷13)=0=>0→Y:sin(A÷17)=0=>0→Y:
sin(A÷19)=0=>0→Y:Y=0=>Goto 2:X<329>Goto2:
sin(A÷23)=0=>0→Y:sin(A÷29)=0=>0→Y:sin(A÷31)=0=>0→Y:
Lbl 2:Y▲Goto 0:

This is pretty much how the program looks when keyed into the calculator in edit mode. Special Program Commands (? → => : Lbl = < ≥ If Then IfEnd ▲ Goto) are input using the [SHIFT] [P-CMD] keys. The cursor key (marked Replay) is used to switch between various screens of commands. Memory variables A, X and Y are input using [ALPHA] [A], [X] etc keys. The ":" Separator Code command is used frequently and can be alternatively input using the [EXE] key.

This program is 264 steps in length.

Tuesday 8 May 2012

Is it prime - comments on the logic

In my previous post I described some logic that could be used to test whether a number is prime. The first bit of the psuedo code checks to see if the number entered, X, is greater than or equal to 372 = 1369. This is the range of this code but it can be altered easily to check numbers much larger than this. It depends on how much memory you have available in your fx-50F calculator. For example, by continuing the test division of X by eight more primes 37, 41, 43, 47, 53, 59, 61 and 67, it would be possible to test numbers up to but not including 712 = 5041.

The next part of the code checks to see if X is less than 11 and, if it is, checks to see if it is one of the primes 2, 3, 5, or 7. If it is Y is set to 1 otherwise Y is 0.

If X is greater than or equal to 11 we can divide X by each of the prime numbers 2, 3, 5, and 7 to see if it is divisible by any of these numbers. As described previously, we use the calculator's sine function for this purpose. Again, if X is divisible by one of these numbers, then Y is set to 0 (i.e. X is not prime) otherwise it is set to 1. If X is less than 121 (=112) then we need not test the number any further.

If X is greater than or equal to 121 we can also try dividing it by the prime numbers 11, 13, 17 and 19. Again, if X is divisible by one of these numbers, then Y is set to 0 (i.e. X is not prime) otherwise it is set to 1. If X is less than 529 (=232) then we need not test the number any further.

Effectively we are bootstraping our way up through the prime numbers and the process is repeated in the remaining steps. As such, it can be extended, within the limits of the calculator, to much larger numbers as described above.

Wednesday 2 May 2012

Is it Prime - the logic

Previously I described how to go about creating an algorithm that could test whether a number is prime. Here is some suitable logic for the fx-50F:-

Label 0
Input X (the number to be tested)
If X is greater than or equal to 37 squared then
   Store 999 in Y (this indicates that X is out of range)
   Goto Label 2
EndIf
If X is greater than or equal to 11 then Goto Label 1
Store 0 in Y (Y is 1 if X is prime, 0 if X is not prime)
If X=2 then store 1 in Y
If X=3 then store 1 in Y
If X=5 then store 1 in Y
If X=7 then store 1 in Y
Goto Label 2
Label 1
Store πX in A
Store 1 in Y
If sin(A/2)=0 then store 0 in Y
If sin(A/3)=0 then store 0 in Y
If sin(A/5)=0 then store 0 in Y
If sin(A/7)=0 then store 0 in Y
If Y=0 then Goto Label 2
If X is less than 121 then Goto Label 2
If sin(A/11)=0 then store 0 in Y
If sin(A/13)=0 then store 0 in Y
If sin(A/17)=0 then store 0 in Y
If sin(A/19)=0 then store 0 in Y
If Y=0 then Goto Label 2
If X is less than 529 then Goto Label 2
If sin(A/23)=0 then store 0 in Y
If sin(A/29)=0 then store 0 in Y
If sin(A/31)=0 then store 0 in Y
Label 2
Display Y
Goto Label 0

Monday 16 April 2012

Is it prime?

I wanted to create an algorithm that could be used to test whether a number is prime or not. I have previously written a program that finds the prime factors of a number and this can be used to determine whether a number is prime or not but it isn't very quick for this purpose. I wanted a faster algorithm that could give a yes/no answer for all positive integers up to about 1000 and could be extended to larger numbers if required.

One issue with the fx-50F calculator is that there is no quotient/remainder function. So if we divide 101 by 7 then we know that the quotient is 14 and the remainder is 3 (i.e 101=14x7+3). If the remainder was 0 then we would have known that 101 was divisible by 7.

One way round this is to use the sine function. We have that sin(πx)=0 if x is an integer and not otherwise (you need to use the fx-50F in radians mode - [SHIFT] [SETUP] [2]). Thus if we let x=101/7=14.428..., then sin(πx)=0.974...whereas if we let x=99/3=33, then sin(πx)=0. So we have a way of determining whether one positive integer is divisible by another.

This forms the basis of the processing. For a given number N we can trial divide N by each of the prime numbers P which are less than some prime M, say. If N is divisible by P then we can set a flag to indicate that N is not prime. Clearly, if N is one of the prime numbers P, then we need to check this and flag it accordingly. This method will be accurate as long as N is is less than M2.

Thursday 29 March 2012