Ask Your Question
0

Recursion oddity

asked 2011-11-12 15:04:37 -0500

Birdman gravatar image

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.

edit retag flag offensive close merge delete

Comments

Can you be more clear as to what the answer that you want to get from gcd_recur? The code you posted is working correctly as it is written.

Mike Hansen gravatar imageMike Hansen ( 2011-11-12 17:00:02 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
3

answered 2011-11-12 17:07:08 -0500

DSM gravatar image

updated 2011-11-12 17:07:37 -0500

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
edit flag offensive delete link more

Comments

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

Birdman gravatar imageBirdman ( 2011-11-12 23:26:20 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2011-11-12 15:04:37 -0500

Seen: 215 times

Last updated: Nov 12 '11