Assignment 6 - Euclid's Algorithm

1. Getting Started

   Please refer to this page for information on how to work on your assignment.

2. Task of this exercise

   Although historically Euclid's Algorithm was implemented by substracting the smaller number from the larger one, the famous version of the algorithm has one improvement: it computes the remainder of the division of two numbers instead of their difference. The task is to update the below program accordingly and to do some further changes of the input-output behaviour.

3. Test the original program

   Test the currently implement algorithm with inputs 1000 and 2. Scroll down the window to inspect the output.

4. The Changes in Detail

   Read the program and understand what is going on. Then do the following changes:

   • Replace the substraction by the computation of the remainder. Look the correct operation up at the Introduction to Java Script to find the correct symbol. Note that you must change the operation for these two statements: x = x - y; and y = y - x; in the source code.
   • Update the condition of the while loop approprately. For the moment it checks whether x is different from y. But since the remainder operation does not make x and y equal, but one of them to 0, you have to check that both x and y are greater than 0.
   • Update the test before computing the value of endtext. This test has to ask whether x == 0 or y == 0 but not whether x == y.
   • Update the way the output is passed on to the variable endtext. Since one of the variables is 0, you can use "(x+y)" instead of x. Note that you need the brackets since otherwise JavaScript would not use the sum but just the concatenation of the printout of the numbers. So for instance 37 + 12 would give 3712 instead of 49.
   • For convenience the program should not have to be reloaded each time you are running it. So you can take as a boolean condition the output of a confirm command. This command has a parameter. Use the content of the endtext variable plus a phrase which tells to click "OK" for continuing the program. So write something like:

     do … while(confirm(endtext + " Press 'OK' to continue"));
     

     at the end of the do-while loop. Delete the command outputting an alert afterwards.
5. Test your program

   Run the whole program and test it. Compare it on the inputs 1000 and 2 with the old program. Scroll down to check the protocol output printed during the computation. Is it faster than the old one?

   You can hand in the program after checking its correctness by showing it to the lecturer.