Ask Your Question

Birdman's profile - activity

2016-09-15 17:32:51 -0600 received badge  Popular Question (source)
2011-11-12 23:26:20 -0600 commented answer Recursion oddity

Thanks, I am a version behind. I've also found that gcd(15, ceil(50/2)) works for what I'm doing.

2011-11-12 23:24:58 -0600 marked best answer Recursion oddity

You're probably running an older version of Sage. For reasons I (famously) disagreed with, it used to be the case that gcd(2, 4/2) and your gcd(15,50/2) would return 1, because the second term is a rational, and the gcd of rationals was defined to be 1. I thought this was very silly, even though defensible.

After a long discussion on sage-devel (following my first ever post there!) and thanks to work by Simon King (trac # 10771), this is no longer the case, and your code seems to work:

sage: gcd_recur(50)
GCD of 15 and 50: 5
GCD of 15 and 25: 5
GCD of 15 and 25/2: 5/2
GCD of 15 and 25/4: 5/4
GCD of 15 and 25/8: 5/8
GCD of 15 and 25/16: 5/16
2011-11-12 23:24:58 -0600 received badge  Scholar (source)
2011-11-12 15:04:37 -0600 asked a question Recursion oddity

I've been having a problem with a recursive factorization algorithm I've been writing in Sage code. The problem is reproduced on my machine using the code below:

def gcd_recur(num):
    if(num <= 1):
        return
    g = gcd(15,num)
    print "GCD of 15 and {0}: {1}".format(num, g)
    gcd_recur(num/2)  

gcd_recur(50)

The result I'm getting is:

GCD of 15 and 50: 5
GCD of 15 and 25: 1
GCD of 15 and 25/2: 1
GCD of 15 and 25/4: 1
GCD of 15 and 25/8: 1
GCD of 15 and 25/16: 1

However, I can run the code below outside of the algorithm and receive the correct result:

gcd(15, 25)

5

Are there some variable scoping issues that I'm not seeing here? Thanks.