Not Yet Answered # euclidean GCD algorithm

wildgoose 420

0

I'm looking at your code, but I don't see your algorithm.

If you're trying to find the Greatest Common Denominator, then I'm not seeing the algorithm. Several methods for a GCD. One is inner, outer loop. Subtract tmp divisor each time, looking for a divisor == 0 vs divisor < remainder result. If not zero, increment the divisor, reset the dividend and start again. Fastest method though would be to start from divisor half the dividend, and decrement the divisor each time.

You aren't using recursion. I'm not aware of any Euclidean GCD algorithm that uses a Nx2 algorithm in its basis.

Can you post your logic in pseudo code to make it clearer!

I've added comments to your code but it isn't helping me understand the algorithm.

What happens if a0 is (0)? I'm assuming a1 is (1) as its being used as a shifter, but shouldn't that be a divisor instead of a multiplier?

```
; a0, a1 preset.
; Assuming a1 always == 1, as a down counter?
; If 1==1 exit
loop: beq $a0, $a1, exit
slt $t0, $a0, $a1 ; t0 = a0 << a1 ??? Why making # bigger to zero instead of smaller?
bne $t0, $zero, label ; jmp t0==0 label
sub $a0, $a0, $a1 ; a0 -= a1 ??? Only subtracting (1)
j loop
; Outer Loop
label: sub $a1, $a1, $a0 ; a1 -= a0
j loop
exit: add $v0, $zero, $a0 ; return a0
```

Instead of starting with assembly. Start with pseudo code or a higher programming language to get the logic flow in place

*Edited 6 Years Ago by wildgoose*: n/a

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I am currently creating a simulation of a pizza ordering system in object oriented program. I have some question. the instruction and guideline is long but I will try and cut it down a lot. the instruction is to create a program that simulate a pizza restaurant using ...

```
#include <stdio.h>
int main(void)
int movieChoice;
int seatNum;
int seatPlan[5][10] = { 0 };
int rows, cols;
char space;
void seatDisplay(int a[][10]);
void seatNew(int n[][10]);
void seatDisplay(int a[][10]) { //this function shows the seat plan
for (int i = 0; i<5; i++) {
for (int j = 0; j<10; j++) ...
```

I have this tree format.

```
> myapp->
> setup.py
> tests ->
> test_myapp.py
> myapp ->
> __init__.py
> myapp.py
```

And from test_myapp.py, I am calling: `from myapp import myapp`

and when I run`python setup.py test`

I am getting `No module named 'myapp'`