I thought I’d start this thread as a place for folks to post short algorithms, with the idea that someone out there might be able to show us how to do what we’re doing better, more efficiently, or in fewer words.
Here’s my entry (Wikipedia tells me that it’s Euclid’s algorithm, though the description there isn’t quite right):
To decide what number is the greatest common divisor of (A - a number) and (B - a number):
let R be the remainder after dividing A by B;
if R is 0, let R be B;
while R is greater than 0:
let S be the remainder after dividing B by R;
if S is 0, break;
let B be R;
let R be S;
decide on R.
Is there a way to do this more elegantly? I’m especially thinking about all of the reassignments (let R be B, let B be R, let R be S), but of course it’s also possible that I’m missing something at a higher level.
I’m not a programmer by trade or by training, and most of what I know of programming I’ve learned via Inform 7, dipping a toe into I6 once in awhile, and through all the help I’ve gotten on this forum. Which I guess is just a long way of saying please don’t laugh too hard at my code
As a rule of thumb, a recursive definition of an algorithm tends to be more readable than an iterative one.
To decide what number is the greatest common divisor of (A - a number) and (B - a number):
if b is 0, decide on A;
decide on the greatest common divisor of B and the remainder after dividing A by B.
As Zarf already pointed out, the “greatest common multiple” of two numbers wouldn’t be a very useful thing to know. It would always be either zero or an infinite number.
I think I also like the recursive version better, but here’s how I would rewrite the loop version:
First, there’s no need for the “break” since your while loop is testing the value of S after it’s assigned to R. There’s also a bug - your phrase would return 0 every time it got to the while loop. I think you meant to return B, not R. Giving variables more descriptive names can sometimes avoid bugs like that.
In terms of Inform syntax, you only need “let” the first time you define a variable. After that it’s typical to use “now.”
You really do need an extra temporary variable when you’re juggling values like that. Personally, I might also create one more temporary variable just for clarity.
To decide what number is the greatest common factor of (A - a number) and (B - a number):
let the candidate be B;
let the old remainder be the remainder after dividing A by the candidate;
while the old remainder is greater than 0:
let the new remainder be the remainder after dividing the candidate by the old remainder;
Now the candidate is the old remainder;
Now the old remainder is the new remainder;
decide on the candidate.
I looked at the Wikipedia page, and I decided I like the recursive version better:
To decide what number is the GCF of (A - a number) and (B - a number):
if B is 0, decide on A;
Decide on the GCF of B and the remainder after dividing A by B;
Is it just me, or does I7 look incredibly awkward with that kind of stuff? A bit like trying to solve a math equation without being able to use math notation…
That true, there isn’t a need for the break anymore (originally there was).
I’m not seeing that bug. I don’t protect against illegal division when the user supplies 0 for B (as Ben’s code does and yours does not), but I don’t think that’s what you’re talking about. Could you specify the conditions under which it might occur? I haven’t been able to break the routine with any input except 0 (intentional).
Using more descriptive names probably would have been better for seeing issues, though, and I normally would have done that–except that I used letters to work this out on paper, then just transferred the logic to Inform.
I consciously use “let” anytime the variable is temporary, regardless of whether it is a declaration or an assignment–it makes it easier to tell at a glance what’s temporary and what’s not. Unless there is a sound technical (performance or something) reason for using “now”, I think I’ll stick with using “let”.
Not as elegant as Ben’s, but definitely more readable than mine.
You actually can use the math notation, to some degree (requires a lot more parentheses, not every operation has a built-in symbol), but it doesn’t work so well with I7’s larger convention of using full words for everything. Code that does lots of math, especially with properties of objects, starts to look far more verbose than it needs to.
You’re right, I was reading your code wrong. The “break” prevents returning a value of 0. So my real complaint would be that the “break” obscures the true nature of the loop - it would be exactly the same if you phrased it as “while true is true.”
I also realized that I could roll the loop more fully AND avoid division by zero by naming the input arguments more cleverly:
To decide what number is the greatest common factor of (candidate - a number) and (old remainder - a number):
while the old remainder is greater than 0:
let the new remainder be the remainder after dividing the candidate by the old remainder;
Now the candidate is the old remainder;
Now the old remainder is the new remainder;
decide on the candidate.
I like to use “now” because then I know that I’m reusing existing variables as opposed to new ones. But in general I like languages like Python where you don’t have to declare variables at all most of the time.
[code]To decide what number is the greatest common factor of (a - a number) and (b - a number):
while a is not 0:
now b be the remainder after dividing b by a;
if b is 0, decide on a;
now a be the remainder after dividing a by b;
decide on b;
or
To decide what number is the greatest common factor of (a - a number) and (b - a number):
forever: [or while 1 is 1, if I7 lacks this]
if a is 0, decide on b;
now b be the remainder after dividing b by a;
if b is 0, decide on a;
now a be the remainder after dividing a by b;
[/code]
Yeah, I think that’s why I7 introduced the concept of “Equations”, to address this issue. Having said that, I haven’t been able to find an opportunity to use equations except to create examples of how to use equations.
And even then it’s pretty limited. It can’t do the quadratic equation, for example.
My current project actually has a perfect application for equations, but I found that I couldn’t use them because of the lack of fractional math. I needed to have accurate fractional multipliers and divisors to arrive at the solutions for many of the equations. I could have gotten there by refactoring the equations, I suppose, but they were already complex enough for my little brain. (I ended up using a phrase structure, which let me use Fixed Point Maths to take care of the fractional values. But Inform’s general disregard for the rules of precedence then meant I spent many hours adding parentheses to make all precedence explicit.)
If and when the Inform library gets support for the Glulx floating point spec, equations might become at least slightly useful.
