Spaces:
Sleeping
Sleeping
File size: 1,871 Bytes
9f135d5 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | // Binary GCD algorithm (Stein's algorithm)
// GCD computation using bit operations instead of division
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_TESTS 1000000
unsigned long long binary_gcd(unsigned long long u, unsigned long long v) {
if (u == 0) return v;
if (v == 0) return u;
// Count common factors of 2
int shift = 0;
while (((u | v) & 1) == 0) {
u >>= 1;
v >>= 1;
shift++;
}
// Remove remaining factors of 2 from u
while ((u & 1) == 0) {
u >>= 1;
}
do {
// Remove factors of 2 from v
while ((v & 1) == 0) {
v >>= 1;
}
// Ensure u <= v
if (u > v) {
unsigned long long temp = u;
u = v;
v = temp;
}
v -= u;
} while (v != 0);
return u << shift;
}
// Regular Euclidean GCD for comparison
unsigned long long euclidean_gcd(unsigned long long a, unsigned long long b) {
while (b != 0) {
unsigned long long temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
unsigned int seed = 42;
clock_t start = clock();
unsigned long long sum = 0;
for (int i = 0; i < NUM_TESTS; i++) {
seed = seed * 1103515245 + 12345;
unsigned long long a = (seed & 0xFFFFFFF) + 1;
seed = seed * 1103515245 + 12345;
unsigned long long b = (seed & 0xFFFFFFF) + 1;
sum += binary_gcd(a, b);
}
clock_t end = clock();
double time_spent = (double)(end - start) / CLOCKS_PER_SEC;
printf("Binary GCD (Stein's): %d tests, %.6f seconds\n",
NUM_TESTS, time_spent);
printf("Sum of GCDs: %llu\n", sum);
return 0;
}
|