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

using normal order evaluation? There are four recursive calls which involve remainder operations.Code:`gcd(412,60)`

isCode:`gcd(a,b)`

is the first of these.Code:`gcd(b,a%b)`

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)

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)