How to Create a Flowchart for Calculating GCD?

[Arman777]

1. The problem statement, all variables, and given/known data
So we need to make a flowchart of GCD

2. Homework Equations

The Attempt at a Solution

Here my codes but something bothers me,

1-Take two positive integers N and M
2-If N>M go to step 3
3-K=M
4=K=K-1
5-Check, If K=1 go to step 11, otherwise, go to step 6
6-Calculate N%K
7-If N%K is zero go to step 8 otherwise go to step 4
8-Calculate M%K
9-If N%K is zero go to step 10, otherwise, go to step 4
10-Print "GCD is K"
11-Print "GCD is 1"

so here in the second line If M>N then I should write the same steps for that result also ?
Another thing is that K=K-1 and K=M terms bother me but I don't know how else I can find it.
So my logic is taking 2 numbers and then choosing the small one. Then dividing the small number with both numbers by reducing 1 in each step. And when the remaining is zero for both numbers we will now that that number "K" is the GCD

 

[jbriggs444]

Check, If M/K=M go to step 11, otherwise, go to step 6

If you want to terminate the loop when K=1, then you should test whether K=1. Do not obfuscate for no reason.

 

[Arman777]

If you want to terminate the loop when K=1, then you should test whether K=1. Do not obfuscate for no reason.

That makes sense..thanks

 

[PeroK]

Before you started your code, did you try a few examples to see how you would go about finding a GCD?

 

[Arman777]

Before you started your code, did you try a few examples to see how you would go about finding a GCD?

I didnt actually no.This one seemed general and nice to me.

 

[PeroK]

I didnt actually no.This one seemed general and nice to me.

If we take an example of, say, $75$ and $30$, your algorithm is:

Divide $75$ and $30$ by $30$: fail
Divide $75$ and $30$ by $29$: fail

...

Divide $75$ and $30$ by $15$: bingo

Do you get any marks for efficiency in these algorithms?

 

[Arman777]

If we take an example of, say, $75$ and $30$, your algorithm is:

Divide $75$ and $30$ by $30$: fail
Divide $75$ and $30$ by $29$: fail

...

Divide $75$ and $30$ by $15$: bingo

Do you get any marks for efficiency in these algorithms?

No they dont. They look just the structure and if its right or not.

Edit:Sad I know but I guess they will start to care that in later

 

[jbriggs444]

9-If N%K is zero go to step 10, otherwise, go to step 4
10-Print "GCD is K"
11-Print "GCD is 1"

You are presenting these as linear sequences of lines but have mentioned a few times that they are "flow charts".

In a sequence of lines, following execution of line 10, one would expect to continue and execute line 11. This natural assumption is visible through your code where you do, in fact, assume that execution proceeds sequentially from one line to the next.

But then we come to the above code where you clearly expect the opposite. In the profession, we refer to this as "DWIM" logic -- "Do What I Mean". In real life, if you want execution to terminate after line 10, you have to say that execution stops after line 10.

Programs do what you say, not what you mean.

 

[Arman777]

 

[Arman777]

You are presenting these as linear sequences of lines but have mentioned a few times that they are "flow charts".

In a sequence of lines, following execution of line 10, one would expect to continue and execute line 11. This natural assumption is visible through your code where you do, in fact, assume that execution proceeds sequentially from one line to the next.

But then we come to the above code where you clearly expect the opposite. In the profession, we refer to this as "DWIM" logic -- "Do What I Mean". In real life, if you want execution to terminate after line 10, you have to say that execution stops after line 10.

Programs do what you say, not what you mean.

I see your point. But Its hard to write as a line step or introduce it like that...In flowcharts its really easy to see

 

[Arman777]

The main question is I guess what happens If M>N I am confused there. Should I copy the steps I did for N>M or is there another way or just we can take as it like that and its not a desicion thing ?

 

[PeroK]

No they dont. They look just the structure and if its right or not.

Edit:Sad I know but I guess they will start to care that in later

I would do something like this.

Inputs are $N, M$

Ensure $N \le M$

** Try as possible divisors $N, N/2, N/3 \dots$.

For $K = 1, 2, 3 \dots$

**Optional
If $K > N/2$, then $D = 1$ and goto Print
Endif (no possibility of further divisors when $N/K < 2$)
**

If $K$ divides $N$
then $D = N/K$ ($D$ is a possible GCD)
If $D$ divides $M$ then goto Print
Endif
Endif

Endfor

Print:
The GCD of $N$ and $M$ is $D$

Note that the first section about $K > N/2$ is optional - it's only there for a modicum of efficiency. If you drop that then you almost have only "one line of code".

What's interesting, I think, is to what extent is it good practice to consider efficiency as soon as start learning programming? After all, eventually, in many scientific applications, numerical efficiency may be the over-riding factor.

Something to think about at least.

 

[willem2]

Your flowchart still lacks updating of k in the loop, so if it loops once, it will loop forever.

You could have a cell in a flowchart titled: set K to the minimum of M and N and then draw a sub-flowchart that implements this step.

You might want to use labels in your pseudo-code, because renumbering when inserting steps will drive you crazy, or you could start with stepnumbers that are multiples of 10, so you can insert lines without any renumbering.

It's probably better to not use GOTO's to go to the next line in your pseudocode, and let all statements go to the next line by default. You will need and END PROGRAM statement to terminate the programm, instead of continuing to the next line.

GCD algorithms are possibly the most analyzed of all algorithms, and it can indeed be done much more efficiently, but a beginning programmer can hardly be expected to come up with anything better than you did. This seems to be a straightforward translation of the definition of GCD. Of course, googling is probably one of the most useful programming techniques, which you should also learn.

 

[jbriggs444]

I see your point. But Its hard to write as a line step or introduce it like that...In flowcharts its really easy to see

It is not that hard to present in a line step. If you want to have execution terminate after a line executes, write down "stop" or "exit".

e.g. 10-Print "GCD is K" and stop.

or

10-Print "GCD is K"
11-Stop

 

[jbriggs444]

The main question is I guess what happens If M>N I am confused there. Should I copy the steps I did for N>M or is there another way or just we can take as it like that and its not a desicion thing ?

The greatest common denominator of N and M is the same as the greatest common denominator of M and N.

In mathematics, one would write "without loss of generality, assume M >= N". The reader is then expected to say "oh, right! If N > M then we can just swap the roles of N and M and the rest of the proof goes through the same way"

In programming, one can do the same thing. Either explicitly with a temporary variable:

If M < N then...
Let T=M
Let M=N
Let N=T

or, as long as we are only writing pseudocode, by simply saying what we want to do:

If M < N then "swap the values of M and N"

 

[PeroK]

, but a beginning programmer can hardly be expected to come up with anything better than you did.

Except that it's not what you would do if given the task. If you started to do GCD that way, you would almost certainly abandon it. It seems to me there is a lot to be gained by associating (and definitely not automatically dissociating) computer logic from the mathematics as you would do it. It feels to me like a bad habit that eventually you will have to unlearn.

As is not being aware that you can run through your flowchart or pseudocode with "test data". I don't know that there is any excuse for a programer, beginner or not, not to test their own flowchart or pseudocode with some test data.

Note: there's no critcism of the OP in this. But, I would stress getting into these good habits from the beginning.

 

[Arman777]

I have other things to do beside this (other homeworks and daily things) and I have 6 hours left and I have to do also another flowchart in 6 hours. If I had more time like couple days or week I can thought something nice and efficient.

Except that it's not what you would do if given the task. If you started to do GCD that way, you would almost certainly abandon it. It seems to me there is a lot to be gained by associating (and definitely not automatically dissociating) computer logic from the mathematics as you would do it. It feels to me like a bad habit that eventually you will have to unlearn.

Sure you are right, but as I said I don't have much time.

 

[Arman777]

Your flowchart still lacks updating of k in the loop, so if it loops once, it will loop forever.

I noticed that the one that I send was wrong,
I am tired I ll try to do the next one.

 

[jbriggs444]

I noticed that the one that I send was wrong,
I am tired I ll try to do the next one.

This has the exact same bug that existed in your previous flowchart (the one for detecting primeness).

Try executing your code for N=4, M=2. The flowchart will claim that the GCD is 1.

 

[Arman777]

This has the exact same bug that existed in your previous flowchart (the one for detecting primeness).

Try executing your code for N=4, M=2. The flowchart will claim that the GCD is 1.

Cause when I say M=2 and then K=K-1 it gets 1 right.

 

[jbriggs444]

Cause when I say M=2 and then K=K-1 it gets 1 right

Right!

 

[Arman777]

Right!

 

[jbriggs444]

Yes, doing the increment at the end of the loop and the test at the beginning is good.

I think we can refrain from pointing out an optimization that would allow this particular termination test to be eliminated entirely. One lesson at a time.

 

[Arman777]

Yes, doing the increment at the end of the loop and the test at the beginning is good.

I am really happy that I solved this.

I think we can refrain from pointing out an optimization that would allow this particular termination test to be eliminated entirely. One lesson at a time.

Is it neceserry...:(

 

[jbriggs444]

Is it neceserry

No, It is not required. You've expressed concern over time pressure and we can respect that.

 

[Arman777]

No, It is not required. You've expressed concern over time pressure and we can respect that.

Okay..Well thanks all of you for your helps

 

[gneill]

Just out of curiosity, did you take any time to investigate the Euclidean Algorithm for determining the GCD? There is a particularly succinct implementation using the modulo function (common in most computer languages) that would be a breeze to flow chart. The Wikipedia article on the topic presents it in the "Implementations" section.

 

[Arman777]

Just out of curiosity, did you take any time to investigate the Euclidean Algorithm for determining the GCD? There is a particularly succinct implementation using the modulo function (common in most computer languages) that would be a breeze to flow chart. The Wikipedia article on the topic presents it in the "Implementations" section.

I didnt actually