Long code execution or endless loop?

Question

There are 2 lists that store the digits of a number. Well, you need to find the GCD of these numbers. If you take the number 9239923923999 - 99992399 - everything seems to be okay, it works. If it's 99999999999999 and 9, then I'm just waiting .. How can I understand if I have an infinite loop somewhere, or is the code itself written crookedly and therefore it’s considered for a long time ?? If the 2nd option, how to speed ?? Algorithm NOD took this:

{ while (a != b) { if (a > b) { long tmp = a; a = b; b = tmp; } b = b - a; } return a; }

Since it is easier to subtract two numbers stored in the list than modulo division. Actually, the subtraction itself:

 { Item * tempfirst = A->Head; Item * tempsecond = B->Head; while (tempfirst && tempsecond) { if (tempfirst->digit < tempsecond->digit) { Item * CurrentItem = tempfirst; CurrentItem->digit += 10; CurrentItem = CurrentItem->next; while (CurrentItem->digit <= 0) { CurrentItem->digit += 9; CurrentItem = CurrentItem->next; } CurrentItem->digit -= 1; } tempfirst->digit -= tempsecond->digit; tempfirst = tempfirst->next; tempsecond = tempsecond->next; } tempfirst = A->Tail; while (tempfirst) { if (tempfirst->digit != 0) break; A->Tail = tempfirst->prev; A->Tail->next = NULL; free(tempfirst); tempfirst = A->Tail; A->size--; } return A; } }

For the rest, it seems to be sure .. But I feel in the subtraction somewhere that is a mistake, or something else.

Accepted Answer · 2017-05-02T18:54:51

Well, you give ... So it’s possible to count the GCD before the carrot of the blast ...

It is clear that you need to count through the remainder! After all, think for it - even if you simply subtract from 99999999999999 by 9 - with ordinary arithmetic, even for a nanosecond - it will take 10 ^ 13 nanoseconds, or 10,000 seconds - 3 hours. And you, with your complicated procedure ?!

For m and n gcd is calculated as while(m && n) if (m < n) n %= m; else m %= n; return m + n;
while(m && n) if (m < n) n %= m; else m %= n; return m + n;
Implement the operation of obtaining the balance, otherwise there will be no sense.
Eh .. Well, I basically assumed that it would take a long time, but I still hoped more that I had nosyachil somewhere and caught an infinite loop.
Well, I'm sorry I upset ... If you are satisfied with the answer - close the question, marking the answer as accepted ...

jfs jfs 44.5k 8 gold signs 53 silver marks 199 bronze marks · Answer 2 · 2017-05-02T21:55:10

Euclidean algorithm for finding the greatest common divisor (GCD) , recorded by division with the remainder:

 U gcd(U a, U b) { while (b) { U t = b; b = a % b; a = t; } return a; }

where U : typedef unsigned long U;

If the effective implementation of a % b not available, then you can try an algorithm that uses x >> 1 (right shift) and x & 1 (even / odd) bitwise operations :

 U gcd(U a, U b) { if (a == b) return a; if (a == 0) return b; if (b == 0) return a; // a != b and > 0 if (a & 1) { // a is odd if (b & 1) {// b is odd // both odd, diff is even, reduce larger arg return (a > b) ? gcd((a - b) >> 1, b) : gcd((b - a) >> 1, a); } else { // a is odd, b is even return gcd(a, b >> 1); } } else if (b & 1) { // a is even, b is odd return gcd(a >> 1, b); } // a is even, b is even return gcd(a >> 1, b >> 1) << 1; // non tail-recursive }

Example of use:

 #include <stdio.h> int main(void) { printf("%lu\n", gcd(99999999999999, 9)); return 0; }

Startup example:

 $ cc *.c && time ./a.out 9 ./a.out 0.00s user 0.00s system 0% cpu 0.001 total

It can be seen that the code is instantly executed.

The speed of execution there was also good, but, alas, "Trust but verify" - not about me.
And I could not make out this algorithm, unfortunately .. Yes, and in any case, it is necessary to implement operations >> and & I understand that >> 1, be divided into two.
Therefore, it will probably be easier to immediately determine the division operation with the remainder.
More specifically, tell me how to implement it - I will be grateful.
(I left my own version under the answer above in the comments)
@TorSen the difference between x>>1 (shr) and x%y (div) can be big.
Despite the more complex algorithm, the shift (Stein) option is, on average, up to 60% faster in terms of the bitwise operations of the Euclidean algorithm — your question is labeled with performance — so bringing such an algorithm is completely appropriate.
Although in practice, many modern processors have an effective division instruction (not your case, as I understand it), so without measurements, it is difficult to say which of the options presented, on which data and hardware will be faster.
>> therefore the cast of such an algorithm is perfectly appropriate.
The fact is that the bitwise version, in the presence of recursion for experienced people, for beginners (at least for me) they are difficult to understand.
And if you also take into account the fact that you need to do all this using lists - so much the more.
@TorSen If it is impossible to realize a logical shift by one for your presentation, then ask a separate question specifically about this.
For this understanding of the algorithm / recursion is not required, although over time you will realize that this is a simple algorithm (and it is useful to understand recursion, but not all at once).
Still, he stopped at the version with the division with the remainder.
(for the rest of it I can justify, but before such algorithms, I have not yet developed.) Regarding the algorithm: Where does the parity / oddness of the number come from and due to what is understandable.

Long code execution or endless loop?

2 answers 2

More articles: