5.3 Until Loops

The until loop is just the opposite of a while loop. Instead of occurring while some condition remains true, an until loop occurs until some condition becomes true. The code and semantics of the until loop are presented in Example 5-3. Its corresponding flowchart is shown in Figure 5-3.

    1 until (condition)
    2 	# statement 1
    3 	# statement 2
    4 	# ...
    5 	# statement n
    6 end

Until loops execute the same way as while loops; the only difference is the way they terminate. If we want the counting program to work with until loops, only one line of the program needs to be changed: while(i <= n) becomes until(i > n). The until and while loops are logical opposites, and the change in the counting program illustrates this, as a greater-than conditional operator (>) is used instead of less than or equal to (<=). Table 5-1 shows every logical operator and its opposite operator.

Switching from a while loop to an until loop is easy; simply switch the operator in the condition to its opposite. However, this raises an interesting point: these loop constructs are interchangeable. There is never any case where you must use an until loop instead of a while loop, or vice versa. A Ruby programmer could go her or his entire life only knowing one of these loops and never have any problem writing any program.

At this point you are probably wondering why both loop types even exist. The reason for having both is to improve the clarity of a program. Some things are simply expressed in a clearer manner with while loops than with until loops, and vice versa. Instead of saying “while this is not true” we can say “until this is true,” and instead of saying “until this is not true” we can say “while this is true.” Frequently it is easier for someone to understand a program that simply tests for the existence of true instead of not true.

In the counting program from Example 5-2, the variable i is a counter. Using counters is common to many tasks that require automation. Anytime a given set of instructions needs to be executed a certain number of times, we will be using counters. Ruby actually does not require us to set up the counter at all. Instead, it is possible to give a set of numbers for a loop to iterate through.

5.4 For Loops and Nested Loops

    1 for num in (0..5)
    2 	puts num
    3 end

Nested Loops

A nested loop is a loop inside another loop. Although all kinds of loops can be nested, the most common nested loop involves for loops. These loops are particularly useful when displaying multidimensional data.

When using these loops, the first iteration of the first loop will initialize, followed by the second loop. The second loop will completely finish before the first loop moves on to its next iteration. If that sounds confusing, the example in Example 5-5 should help you understand the concept. Its corresponding flowchart is shown in Figure 5-4.

Nested loop construct

    1 for i in (1..3)
    2 	puts "Outer loop: i = " + i.to_s
    3 for k in (1..4)
    4   puts "Inner loop: k = " + k.to_s
    5 	end
    6 end

If you execute the program presented, you will see that the outer loop is displayed three times. However, between each outer loop, four iterations of the inner loop are run.

The flowchart illustrates the internal computation necessary to execute the code presented. The code itself, however, is easier to follow than the actual flowchart. Note thus the essence of using the proper code structure for a particular task.

Nested loops can be a powerful tool when displaying data involving both rows and columns. For example, it is possible to make a program that would print a calendar that displays 12 different months, and for each month, displays each day.

5.5 Infinite Loops

A classic problem, especially among new programmers, is that a small mistake can lead to implementing a program that simply will not stop.

Example 5-6 has an initial value of 5 stored in the variable i in line 3. The loop indicates that we should continue as long as i is greater than zero. Line 5 increments i. Hence, the loop condition of i > 0 is always true; so the loop will never terminate. When you run the program, it will look like nothing is happening, but in actuality, your computer is quite busy. It is happily repeating lines 4 and 5 forever. To terminate the program, hold down the Ctrl key and press C. This is an old key sequence that is an abbreviation for cancel, one of the arcane things you should memorize. (Ctrl-C cancels execution, and Ctrl-D ends the file.) There are a few other Ctrl sequences, but these two are all you need to make it through this book.

    1 puts "Count from 0 to ? "
    2 n = gets.to_i
    3 i = 5
    4 while (i > 0)
    5 	i = i + 2
    6 end

Assume you realize that you are in an endless loop, and you want to fix it. Sometimes new programmers simply execute the program again with no changes. Let us assure you that if you do not make a change, nothing will change. The program will once again run indefinitely.

The secret to fixing an endless loop is to check the terminating condition and make sure that it will ultimately be satisfied. Hence, change something but do not change things randomly. Identify the cause of the problem, make a change that makes sense, and then test to see if your change has fixed the problem.

5.6 Example: Finding Prime Numbers

You now know enough to write numerous computer programs in Ruby, and we will soon finally be able to stop worrying about the details of a programming language and return to the fundamentals of computer science. In fact, at this point, you really know enough to compute mathematically just about anything that can be computed. To provide a little more practice with the topics we have discussed, let’s return to our prime number example. First we present a Ruby implementation (Example 5-7), and then we explain the algorithm illustrated in detail.

     1 # Initialize our counter
     2 i = 1
     3 
     4 # i: [0, 100]
     5 while (i <= 100)
     6   # Initialize prime flag
     7   prime_flag = true
     8   j = 2
     9   # Test divisibility of i from [0, i/2]
    10   while (j <= i / 2)
    11     # puts " i ==> " + i.to_s + " j ==> " + j.to_s
    12     if (i % j == 0)
    13       prime_flag = false
    14       # break
    15     end
    16     j = j + 1
    17   end
    18   # We found a prime!
    19   if prime_flag
    20     puts "Prime ==> " + i.to_s
    21   end
    22   # Increment the counter
    23   i += 1
    24 end

Recall that a number is considered prime if and only if its only divisors, commonly called factors, are 1 and itself. For example, 9 is not prime while 7 is. As hinted in Chapter 3, it is unnecessary to check for factors until you reach the actual number (minus one) since the largest divisor must be no greater than half the number itself. A prime number implementation can be optimized by using the knowledge that we can terminate the loop early.

The Ruby implementation shown in Example 5-7 includes a main loop that terminates at half the number rather than continuing until the actual number (minus one). Using this modification, we eliminate roughly half the number of loop iterations needed to determine if the number is a prime. If the number being tested is large, such a reduction can be significant in terms of the actual execution time.

$ ruby prime.rb
Prime ==$>$ 1
Prime ==$>$ 2
Prime ==$>$ 3
Prime ==$>$ 5
Prime ==$>$ 7
Prime ==$>$ 11
Prime ==$>$ 13
Prime ==$>$ 17
Prime ==$>$ 19
Prime ==$>$ 23

5.7 Summary

You are now able to write numerous programs in Ruby. You also now have a better idea of what an algorithm is. What remains are topics that simplify the writing of complex algorithms and programs.

5.8 Exercises

1. For each of the following subproblems, convert the given loop type (while, until) into its opposite.

   1. while (x == 5)

   2. until (x < 7)

   3. until ((x != 0) and (y > 2))

2. Walk through the program in Example 5-8 and explain what it does.

   Code for Exercise 2

       1 puts "Enter a number >= 0: "
       2 n = gets.to_i
       3 a = 1
       4 while (n > 1)
       5 	a = (n * (n - 1)) * a
       6 	n = n - 2
       7 end
       8 puts a
   

3. Write a program to calculate compounded interest using a while loop. The user inputs the amount deposited, the interest rate (as a percentage) per period, and the number of periods the deposit accumulates interest. Compound interest means that every period, your new balance is calculated using the last period’s balance times the interest rate.

4. Implement the mod operator without using the mod operator but using a loop. (Assume the numerator is always greater than the denominator and both are greater than 0.)

5. Make a simple calculator. It should read in two numbers, apply an operator (+, -, *, /), and display the result. It should continue to do this until a condition of your choosing stops it.

6. Write a program that outputs the first 20 numbers in the Fibonacci sequence. In the Fibonacci sequence, the current number is the sum of the previous two numbers. The first two numbers in the sequence are 1 and 1.