#42 (Normal Order Evaluation) davidmccoy Scam Skeptic Posts: 65 Threads: 29 Joined: Aug 2017 Reputation: 13 09-03-2017, 08:30 PM (This post was last modified: 09-03-2017, 08:32 PM by davidmccoy.) Quote:42. Consider this recurrence: Code:```   gcd(a,b) = a if b is zero    gcd(a,b) = gcd(b,a%b) otherwise``` Assuming a knowledge of when to stop, what is the number of remainder operations performed by Code:`gcd(412,60)`using normal order evaluation? There are four recursive calls which involve remainder operations. Code:`gcd(a,b)` is Code:`gcd(b,a%b)`is the first of these. Using normal order, we would evaluate at the last possible moment, correct? If so, is this how we should approach the problem? gcd(a,b) gcd(b, a%b) gcd(a%b, (a%b)%(a%b)) gcd((a%b)%(a%b), ((a%b)%(a%b))%((a%b)%(a%b))) This adds up to 15 '%' operations, and technically I should be including a fourth level for gcd(412,60), but the answer is not listed. How should I be performing normal order evaluation? UA ACM Vice President ACM has bi-weekly meetings Tuesdays at 5:15pm We're UA's best organization for CS majors (website) Join us on Slack for all kinds of discussion channels (including one for CS403) lusth Administrator Posts: 200 Threads: 15 Joined: Jul 2017 Reputation: 12 09-03-2017, 09:00 PM I think your second recursive call is off. davidmccoy Scam Skeptic Posts: 65 Threads: 29 Joined: Aug 2017 Reputation: 13 09-03-2017, 09:36 PM (09-03-2017, 09:00 PM)lusth Wrote: I think your second recursive call is off. Whoops, yeah it was off. But now, I'm still not getting one of the answers listed: gcd(b, a%b) gcd(a%b, b%(a%b)) gcd(b%(a%b), (a%b)%(b%(a%b))) gcd((a%b)%(b%(a%b)), (b%(a%b))%((a%b)%(b%(a%b)))) This totals 21 remainder operations. UA ACM Vice President ACM has bi-weekly meetings Tuesdays at 5:15pm We're UA's best organization for CS majors (website) Join us on Slack for all kinds of discussion channels (including one for CS403) lusth Administrator Posts: 200 Threads: 15 Joined: Jul 2017 Reputation: 12 09-03-2017, 10:37 PM Yes, but how many are actually performed? davidmccoy Scam Skeptic Posts: 65 Threads: 29 Joined: Aug 2017 Reputation: 13 09-03-2017, 10:54 PM (09-03-2017, 10:37 PM)lusth Wrote: Yes, but how many are actually performed? gotta love those "aha" moments. UA ACM Vice President ACM has bi-weekly meetings Tuesdays at 5:15pm We're UA's best organization for CS majors (website) Join us on Slack for all kinds of discussion channels (including one for CS403) « Next Oldest | Next Newest »