Suurin yhteinen tekijä

Ztane 14.05.07 12:14

Laskee lukujen suurimman yhteisen tekijän

 Tekstiversio  Arvo: 7 (7 ääntä)  Äänestä: +  -
def gcd(a, b):
        shift = 0
        if (a <= 0) or (b <= 0):
                return 0

        while a != 0:
                if a & 1 == 0:
                        a >>= 1
                        if b & 1 == 0:
                                shift += 1
                                b >>= 1
                                continue

                        continue

                if b & 1 == 0:
                        b >>= 1
                        continue

                # swap if a smaller than b
                if (a < b):
                        a, b = b, a

                a = (a - b) >> 1
                # continue while...

        return b << shift
 

editoitu: 17:39 14.5.07
Ztane 12:19 14.5.07 
Ei rekursiota, toimii myös isoille numeroille. Testannut olen ylimalkaisesti.

Perustuu seuraavaan:
- a parillinen, b parillinen: syt(a, b) = 2 syt(a / 2, b / 2)
- a parillinen, b pariton: syt(a, b) = syt(a / 2, b)
- a pariton, b pariton, a > b: syt(a, b) = syt((a - b) / 2, b)
- syt(0, b) = b (euklideen algoritmin loppuehto)
Häntärekursio aukaistu, n kappaletta 2:lla kertomisia vedetty muuttujaan shift.

Lue lisää: Cormen, Leiserson, Rivest (2000): Introduction to Algorithms, MIT Press.

Todistus:
1. a parillinen ja b parillinen -> yhteinen tekijä 2 -> syt (a, b) = 2 syt (a/2, b/2)
2. eri pariteetit -> 2 ei yhteinen tekijä, jaa parillinen kahdella.
3. molemmat parittomia: käytetään implikaatiota d | a, d | b -> d | (a - b). a - b on aina parillinen, joten sen voi jakaa heti kahdella, koska b on pariton. (sääntö 2)
Ztane 13:47 14.5.07 
Suoritusaika luokkaa O(lg(max(a, b))