The understanding of the code. C++

[prog2222]

Can you explain me please this code? I understand it in general terms. I need a clear understanding.

#define isEven(x) ((x & 0x01) == 0)
#define isOdd(x) (x & 0x01)
#define swap(x, y) (x^=y, y^=x, x^=y)
void foo(int *u, int *v, int *u1, int *u2, int *u3){
    int k, t1, t2, t3;
    if (*u < *v) swap (*u, *v);
    for (k = 0; isEven(*u) && isEven(*v); ++k) {
        *u >>= 1;
        *v >>= 1;
    }
    *u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u - 1; t3 = *v;
    do {
        do{
            if(isEven(*u3)) {
                if (isOdd(*u1) || isOdd(*u2)){
                    *u1 += *v;
                    *u2 += *u;
                }
            *u1 >>= 1;
            *u2 >>= 1;
            *u3 >>= 1;
            }
            if (isEven(t3) || *u3 < t3) {
                swap(*u1, t1);
                swap(*u2, t2);
                swap(*u3, t3);
            }
            } while (isEven(*u3));
            while (*u1 < t1 || *u2 < t2) {
                *u1 += *v;
                *u2 += *u;
            }
            *u1 -= t1;
            *u2 -= t2;
            *u3 -= t3;
        } while (t3 > 0);
        while (*u1 >= *v && *u2 >= *u) {
            *u1 -= *v;
            *u2 -= *u;
        }
        *u <<= k;
        *v <<= k;
        *u3 <<= k;
}

[jonnin]

what do you want to know? What do you think it does?

I can tell you that it is intentional gibberish, designed to mess with whoever is reading it, see the bad function name, bad macros (iseven is inefficient on top of being bad), bad variable names, bad use of pointers, cryptic and unnecessary bitwise logic, bad brace alignment, and other attempts to make it look as awful as possible.

Throw it away. Whatever it is supposed to do, you can do it better with clean code.

[lastchance]

He/she has taken it from a bona fide book on cryptography (by Bruce Schneier). It's apparently the extended Euclidean algorithm, and can be used (amongst other things) to find multiplicative inverses modulo n.

But don't ask me to prove that!

[jonnin]

this is arguably worse than the stuff in numerical recipes (early edition).
I mean, there is something to be said, if it works and you need to use it.
But if you need to understand it, ... f that.

[The Grey Wolf]

Even Schneier doesn't try to explain or prove it, he just points you to Knuth Art of Computer Programming Volume 2.

[malibor]

@jonnin lol man, when I saw OP's post I was of same opinion as you, "not worth trying to bother with nonsense".

But I was afraid from commenting because you never know ;)

[prog2222]

Thanks for answers. Yes, It is Schneier. So what can you advise instead of this code? I try to write the extended Euclidean algorithm.

[lastchance]

Why don't you code from the Wikipedia article on the Extended Euclidean algorithm?

[prog2222]

Something else?

[lastchance]

#include <iostream>
using namespace std;

void ExtendedEuclid( int a, int b, int &x, int &y, int &g )
{
   x = 1;  y = 0;
   int xb = 0, yb = 1;
   while ( b )
   {
      int q = a / b;                   // quotient
      int a0 = b, x0 = xb, y0 = yb;    // store previous
      b  = a - q * b ;                 // iteration
      xb = x - q * xb;
      yb = y - q * yb;
      a = a0;   x = x0;   y = y0;      // update
   }
   g = a;
}


int main()
{
   int a, b;
   cout << "Enter a and b (both positive): ";   cin >> a >> b;
   int x, y, g;
   cout << "Solves for Bezout coefficients x, y in ax + by = gcd( a, b )\n";
   ExtendedEuclid( a, b, x, y, g );
   cout << "a: " << a << "    b = " << b << "    gcd(a,b) = " << g << '\n';
   cout << "x: " << x << "    y = " << y << '\n';
   cout << "Check: ax+by = " << a * x + b * y << '\n';
}

Enter a and b (both positive): 240 46
Solves for Bezout coefficients x, y in ax + by = gcd( a, b )
a: 240    b = 46    gcd(a,b) = 2
x: -9    y = 47
Check: ax+by = 2

Just realised that you can slightly simplify it to

#include <iostream>
using namespace std;

void ExtendedEuclid( int a, int b, int &x, int &y, int &g )
{
   x = 1;
   int xb = 0, astore = a, bstore = b;
   while ( b )
   {
      int q = a / b;          // quotient
      int a0 = b, x0 = xb;    // store previous
      b  = a - q * b ;        // iteration
      xb = x - q * xb;
      a = a0;   x = x0;       // update
   }
   g = a;
   y = ( g - astore * x ) / bstore;
}


int main()
{
   int a, b;
   cout << "Enter a and b (both positive): ";   cin >> a >> b;
   int x, y, g;
   cout << "Solves for Bezout coefficients x, y in ax + by = gcd( a, b )\n";
   ExtendedEuclid( a, b, x, y, g );
   cout << "a: " << a << "    b = " << b << "    gcd(a,b) = " << g << '\n';
   cout << "x: " << x << "    y = " << y << '\n';
   cout << "Check: ax+by = " << a * x + b * y << '\n';
}

[prog2222]

@lastchance thank you very much

[prog2222]

@lastchance If It is not difficult for you, can you explain me what means xb, a0, x0?

[lastchance]

prog2222 wrote:

can you explain me what means xb, a0, x0?

I coded directly from the algorithm in
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
(Look at their segment of pseudocode.)

x and y correspond to what are called s and t respectively in that write-up.

The usual Euclidean algorithm uses updates of a and b rather than the sequence r_k, so that is the notation that I used.

Since I don't bother to store whole sequences I need to store and update two iteration levels for each step, and you need to advance these forward. So a0, x0 and y0 store the values that you are eventually going to have to assign to a, x and y (or r_k, s_k and t_k in the Wikipedia notation), whilst b, xb and yb are updated to what is r_k+1, s_k+1 and t_k+1 in the Wikipedia notation.

You need to sit down and follow the Wikipedia article or similar.



Incidentally, the code in your original post presumably gives the same result (difficulty to tell: it's indecipherable), and for all I know it might be faster, but I'm pretty sure it's not following the same algorithm. There is no evidence of extracting a quotient, for example.

[prog2222]

I tried to rewrite the code like:

function extended_gcd(a, b)
    s := 0;    old_s := 1
    r := b;    old_r := a
         
    while r ≠ 0 do
        quotient := old_r div r
        (old_r, r) := (r, old_r − quotient × r)
        (old_s, s) := (s, old_s − quotient × s)
    
    if b ≠ 0 then
        bezout_t := quotient(old_r − old_s × a, b)
    else
        bezout_t := 0
    
    output "Bézout coefficients:", (old_s, bezout_t)
    output "greatest common divisor:", old_r

I got:

void ExtendedEuclid(int a, int b, int &g) {
   int s = 0, old_s = 1;
   int r = b, old_r = a;

   while (b) {
      int quotient = a / b;
      int prov_a = r;
      int prov_x = s;

      r = old_r - quotient * r;
      s = old_s - quotient * s;

      old_r = prov_a;
      old_s = prov_x;
   }
   g = old_r;
   y = (g - old_r * x) / r;
}

int main() {
    int a, b;
    std::cout << "Enter a and b (both positive): "; std::cin >> a >> b;
    int x, y, gcd;
    std::cout << "Solves for Bezout coefficients x, y in ax + by = gcd(a, b)" << std::endl;
    ExtendedEuclid(a, b, gcd);
    std::cout << "gcd(a,b) = " << gcd << std::endl;
    std::cout << "x: " << x << "    y = " << y << std::endl;
    std::cout << "ax+by = " << a * x + b * y << std::endl;
}

Can it be true?

[lastchance]

Can it be true?

You are just using (the results for) the standard Euclidean algorithm. You aren't using or returning the coefficients x and y, and they wouldn't be correct from what you have coded since (amongst other things) x is never set.

If that is all you want then you might as well use the built-in function from the standard library std::gcd(a,b). You wouldn't need the Extended Euclidean Algorithm at all.

You had better make up your mind what you want.