Number Theory & Algorithms

int x = 126, y = 105; do{ if(x > y) x = x - y; else y = y - x; }while(x!=y); printf('%d", x); The output of the given C code segment is __________. (Answer in integer)

Consider the following ANSI C function: int SomeFunction (int x, int y) { if ( (x == 1) I I (y == 1)) return 1; if (x == y) return x; if (x > y) return SomeFunction(x - y, y); if (y > x) return SomeFunction(x, y - x); }...

Consider the following C functions. int tob(int b, int* arr) { int i; for (i=0; b>0; i++) { if (b%2) arr[i] = 1; else arr[i]=0; b = b/2; } return (i); } ____________________ int pp(int a, int b) { int arr[20]; int i, tot...

In the following C function, let n $$ \ge $$ m. int gcd(n,m) { if (n % m == 0) return m; n = n % m; return gcd(m,n); } How many recursive calls are made by this function?

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute (b n mod m),$$0 \le b,n \le m$$?

Consider the following C program main ( ) { int x, y, m, n; scanf("%d %d", &x, &y); /* Assume x > 0 and y > 0 */ m=x; n=y; while(m!=n) { if(m>n) m=m-n; else n=n-m; } printf("%d", n); } The program computes

What does the following algorithm approximate? (Assume m > 1, $$ \in > 0$$) x = m; y = 1; while(x - y > ε){ x = (x + y) / 2; y = m/x; } print(x);