Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
#42 (Normal Order Evaluation)
#1
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)
Reply
#2
I think your second recursive call is off.
Reply
#3
(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)
Reply
#4
Yes, but how many are actually performed?
Reply
#5
(09-03-2017, 10:37 PM)lusth Wrote: Yes, but how many are actually performed?

Idea 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)
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)