CODEWITHSUNDEEP
iosswiftpseudocode
Matt Young
Matt Young

Reputation: 33

Euclidean algorithm pseudocode conversion to Swift?

I have been working on a function for reducing fractions in Swift, and came across the Euclidean algorithm for finding the greatest common factor (http://en.wikipedia.org/wiki/Euclidean_algorithm)

I converted the pseudo code into swift, but yet I am confused how this is going to give me the greatest common factor if it is returning a which I thought was supposed to be the numerator of the fraction. Any help on this would be greatly appreciated. Thanks!

Pseudocode:

function gcd(a, b)
    while b ≠ 0
       t := b
       b := a mod b
       a := t
     return a

Swift:

var a = 2
var b = 4

func gcd(a: Int, b: Int) -> Int {
    var t = 0
    while b != 0 {
        t = b
        let b = a % b
        let a = t
    }
    return a
}

println("\(a)/\(b)")

Console output: 2/4

Upvotes: 3

Views: 1544

Answers (4)

Paul Bird
Paul Bird

Reputation: 74

Swift 3 version of answer given by Christopher Larsen

func gcd(a: Int, b: Int) -> Int {
  if b == 0 { return a }
  return gcd(a: b, b: a % b)
}

Upvotes: 1

vacawama
vacawama

Reputation: 154691

Taking @dasblinkenlight's answer and getting rid of t by using tuples for parallel assignment yields:

Swift 2.1:

func gcd(var a: Int, var _ b: Int) -> Int {
    while b != 0 {
        (a, b) = (b, a % b)
    }
    return a
}

gcd(1001, 39)  // 13

var parameters are deprecated in Swift 2.2 and will be removed in Swift 3. So now it becomes necessary to declare a and b as var within the function:

func gcd(a: Int, _ b: Int) -> Int {
    var (a, b) = (a, b)
    while b != 0 {
        (a, b) = (b, a % b)
    }
    return a
}

Upvotes: 4

Christopher Larsen
Christopher Larsen

Reputation: 1411

Can use a recursive method that just keeps calling itself until the GCD is found.

func gcd(a: Int, b: Int) -> Int {
    if b == 0 {
        return a
    }

    let remainder: Int = a % b

    return gcd(b, b: remainder)
}

and use like so

let gcdOfSomeNums = gcd(28851538, b: 1183019)
//gcdOfSomeNums is 17657

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726919

When you do this

let b = a % b

you are creating another readonly variable b, which has nothing to do with the variable b from the outside scope. You need to remove both lets inside the loop, and make parameters modifiable by declaring them with var, like this:

func gcd(var a: Int, var b: Int) -> Int {
    var t = 0
    while b != 0 {
        t = b
        b = a % b
        a = t
    }
    return a
}

You can call your function like this:

let a = 111
let b = 259
println("a=\(a), b=\(b), gcd=\(gcd(a,b))")

This prints a=111, b=259, gcd=37

Upvotes: 5

Related Questions