辗转相减法求最大公约数要点

辗转相减法在《九章算术》中有所论述

方法如下：
1 用2对分子分母约分，记录约分次数count；
2 如果分子或分母出现奇数，则转到3；
3 分子分母中较大的为a，较小的为b；
4 c = a - b；
5 若c与b不相等，则c与b中较大的为a，较小的为b，回到4；相等则到6；
6 若count为0，则result = c；不为0则c乘以2的count次方的积赋给result；
7 result即为a与b的最大公约数。

这里有一点需要注意：
当a与b相等时，这个算法不能正确处理，所以应保证a与b不相等。但是如果使用辗转相除（欧几里得算法）就没有这个问题。

代码及测试如下：

substraction.c 描述了辗转相减法
====================================================================
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//#define _DEBUG_ 1

void print_usage()
{
printf("Usage: rotate_substraction <num1> <num2>");
printf("\n");
}

int rotate_substraction(int num1, int num2, int odd_time)
{
// equal number is itself
if (num1 == num2) {
return num2;
}
#ifdef _DEBUG_
printf("Num1 is : %d\n", num1);
printf("Num2 is : %d\n", num2);
#endif
// half
while (num1 % 2 == 0 && num2 % 2 == 0) {
num1 >>= 1;
num2 >>= 1;
odd_time++;
}

// substrcation
int sub = num1 - num2;
if (sub == num2) {
if (odd_time == 0) {
return sub;
} else {
return sub * pow(2, odd_time);
}
} else {
return rotate_substraction(
sub > num2 ? sub : num2,
sub < num2 ? sub : num2,
odd_time
);
}
}

int main(int argc, char **argv)
{
if (argc < 3) {
print_usage();
return -1;
}

int num1 = atoi(argv[1]);
int num2 = atoi(argv[2]);

printf("[%d, %d]Equal Number is : %d\n", num1, num2,
rotate_substraction(
num1 > num2 ? num1 : num2,
num1 < num2 ? num1 : num2,
0
));

return 0;
}

devision.c 描述了辗转相除法（欧几里得算法）
====================================================================
#include <stdio.h>
#include <stdlib.h>

//#define _DEBUG_ 1

void print_usage()
{
printf("rotate_devision <num1> <num2>");
printf("\n");
}

int rotate_devision(int num1, int num2)
{
#ifdef _DEBUG_
printf("Num1 is : %d\n", num1);
printf("Num2 is : %d\n", num2);
#endif

if (num1 % num2 == 0) {
return num2;
}

int dev = num1 % num2;

return rotate_devision(
dev > num2 ? dev : num2,
dev < num2 ? dev : num2
);
}

int main(int argc, char **argv)
{
if (argc < 3) {
print_usage();
return -1;
}

int num1 = atoi(argv[1]);
int num2 = atoi(argv[2]);

printf("[%d, %d]Equal Number is : %d\n", num1, num2,
rotate_devision(
num1 > num2 ? num1 : num2,
num1 < num2 ? num1 : num2
));

return 0;
}

测试bash脚本
====================================================================
#!/bin/sh

gcc -lm -o substraction substraction.c
gcc -o devision devision.c

for i in $(seq 1 100); do
./substraction 100 $i >> sub_result
./devision 100 $i >> dev_result
diff -i sub_result dev_result > result
cat result
rm *_result
done

我测试了1到10000和10000的最大公约数，两种算法所得结果一致。