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

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

ios - Euclidean algorithm pseudocode conversion to Swift?, 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  algorithm,graph,pseudocode,tarjans-algorithm. 1) Your first question: It can easily been done in O(1) , just maintain a boolean array inStack, the moment node n is put in the stack, flag inStack[n] to true. When you pop it off the stack, flag it back to false. 2) Not much different between w.index and

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
}

Euclidean algorithm pseudocode conversion to Swift?, 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  The Euclidean algorithm is an algorithm. It can be used to find the biggest number that divides two other numbers (the greatest common divisor of two numbers). It can be used to find the biggest number that divides two other numbers (the greatest common divisor of two numbers).

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)
}

ios - Euclidean algorithm pseudocode conversion to Swift? -, i have been working on function reducing fractions in swift, , came across euclidean algorithm finding greatest common factor  As is indeed a number of the form − for some , our algorithm is justified. The point of the algorithm is to continue this procedure until one number is 0, because g c d ( x , 0 ) = a b s ( x ) {\displaystyle gcd(x,0)=abs(x)} , which we can then return as our answer.

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

Euclidean algorithm, Euclidean algorithm pseudocode conversion to Swift? I converted the pseudo code into swift, but yet I am confused how this is going to give me the greatest  Euclidean Algorithm for Greatest Common Divisor (GCD) The Euclidean Algorithm finds the GCD of 2 numbers. You will better understand this Algorithm by seeing it in action. Assuming you want to calculate the GCD of 1220 and 516, lets apply the Euclidean Algorithm- Assuming you want to calculate the GCD of 1220 and 516, lets apply the Euclidean Algorithm- Pseudo Code of the Algorithm-Step 1: Let a, b be the two numbers Step 2: a mod b = R

Once Again, about Greatest Common Divisor, the Euclidean , In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for Implementations of the algorithm may be expressed in pseudocode. version which was Euclid's original version, the remainder calculation ( b := a mod  Euclidean Algorithm For the basics and the table notation; Extended Euclidean Algorithm Unless you only want to use this calculator for the basic Euclidean Algorithm. Multiplicative inverse in case you are interested in calculating the multiplicative inverse of a number modulo n using the Extended Euclidean Algorithm; Calculator

Greatest common divisor, One of the most famous is so-called the Euclidean algorithm — perhaps, Here's an example of Swift implementation of the subtraction one: Let an integer function f:{1,2,3n} be monotonic and defined in {1,2,3n} and suppose that f(1) > 0 and f(n) < 0. We would like to find the smallest integer i with f(i) < 0. Design an algorithm for this purpose that run in O(logn).

(PDF) An Analysis of Lehmer's Euclidean GCD Algorithm, 27.1 Iterative Euclid algorithm; 27.2 Recursive Euclid algorithm; 27.3 Iterative binary algorithm. 28 C# Euclid algorithm. 161 Smalltalk; 162 SNOBOL4; 163 Sparkling; 164 SQL; 165 Stata; 166 Swift; 167 Tcl Translation of: Python. F gcd​(=u  pseudocode The randomcoord function was given to me in the project. That's why it's not mentioned anywhere else. That's why it's not mentioned anywhere else. This is in pseudocode and I just wanted to check if there is anything wrong with it.

Comments
  • Thank you, this helped! I was caught up at first because I needed to add the keyword var before a: and b: so it doesn't default to let variables.
  • @dasblinkenlight, I used a tuple to get rid of t in your answer.