obsidian-notes/代码/最大公约数gcd.md

title	updated	created	tags
最大公约数gcd	2022-01-14 01:51:50Z	2022-01-08 13:18:07Z	mcu pll 代码块

含义

great common divisor, gcd 能够整除多个整数的最大正整数

算法

辗转相除法

$gcd(a,0)=a$ $gcd(a,b)=gcd(b,a mod b)$ 如果参数都大于0，那么可以简写成 $gcd(a,a)=a$ $gcd(a,b)=gcd(a-b,a), if \space a>b$ gcd(a,b)=gcd(a,b-a), if \space a<b

代码

int gcd(int a, int b)
{
    if(b)
    {
   	 while((a %= b) && (b %= a));
   	 return a + b
    }
}

// greatest common denominator - euclid algo w/o recursion
uint32_t gcd_iter(uint32_t u, uint32_t v)
{
        uint32_t t;
        while (v) {
                t = u;
                u = v;
                v = t % v;
        }
        return u ;
}

#mcu #pll #代码块