Newton's Method

Newton's method is a numerical technique for finding solutions to problems of the form f(x) = 0. Any value of x that satisfies f(x) = 0 is called a root of the function f.

To find a root, you start with a guess x₀. You then update your guess using the formula:

x₁ = x₀ - f(x₀) / f'(x₀)

where f'(x) is the derivative of f(x). You repeat this process until a sufficiently accurate value is found:

x_n+1 = x_n - f(x_n) / f'(x_n)

Finding Square Roots

Suppose you want to find the square root of a number t. This is equivalent to finding a root of the equation:

f(x) = t - x²

With a little bit of algebra, you can show that:

x_n+1 = 0.5 * (x_n + t / x_n)

Notice that if x_n = t / x_n then

x_n+1 = x_n

Finding Square Roots

To find the square root of a number t:

set x to t
while (x != t / x)
  replace x with the average of x and t / x
output x

Does this work?

Sentinel-Based Input

Write a loop that repeatedly reads an integer number from the user until the user enters -1.

In pseudocode:

set number to zero
while number is not -1
   read number from user

In Java:

final int SENTINEL = -1;
int number = 0;
while (???)
{
   
}

Compute the Sum

Write a loop that repeatedly reads an integer number from the user until the user enters -1; the loop should compute and output the sum of the numbers entered so far.

In Java:

final int SENTINEL = -1;
int number = 0;
int sum = 0;
while (???)
{
   
}

Compute the Sum of n Numbers

Instead of using a sentinel, suppose you ask the user how many numbers they want to input. Write a loop that computes the total sum of the numbers input by the user.

output.print("How many numbers do you want to enter?: ");
int n = input.nextInt();

int sum = 0;

while (???)
{

}

for Loops

The idea of using a loop controlled by a counter is so common that it has its own kind of loop, the for loop.

The for loop is controlled by 3 expressions, all of which are optional.

      for (initial-expression; logical-expression; update-expression)
      {
         statements
      }

The loop executes as follows:

1. The initial-expression executes; this only ever happens once.
2. The logical-expression is evaluated. If it is true then:
   1. The body statements are executed.
   2. The update-expression is executed.
3. Step 2 is repeated.

Tracing a Loop

Suppose we have the following loop that computes the sum 0 + 1 + 2:

      int sum = 0;
      for (int i = 0; i < 3; i++)
      {
         sum = sum + i;
      }

You can think of this loop as being equivalent to:

      int sum = 0;
      {
         int i = 0;          // this only happens once

         if (i < 3)
         {
            sum = sum + i;   // sum is now 0
         }
         i++;                // i is now 1

         if (i < 3)
         {
            sum = sum + i;   // sum is now 1
         }
         i++;                // i is now 2

         if (i < 3)
         {
            sum = sum + i;   // sum is now 3
         }
         i++;                // i is now 3
         
         // i < 3 is false so the loop ends
      }

Compute the Sum on n Numbers

output.print("How many numbers do you want to enter?: ");
int n = input.nextInt();

int sum = 0;

for (int count = 0; count < n; count++)
{
   int number = input.nextInt();
   sum += number;
}

When written this way, the variable count is local to body of the loop; you cannot use count after the loop body.

Traditionally, loop counter variables are named i, j, and k.

Count from 0 to 9

Write a for loop that outputs the integers 0 to 9.

      final int MAX = 10;
      for (int i = 0; i < MAX; i++)
      {
         out.println(i);
      }

Count from 0 to 10

Write a for loop that outputs the integers 0 to 10.

      final int MAX = 10;
      for (int i = 0; i <= MAX; i++)
      {
         out.println(i);
      }

It is very easy to make an off-by-1 error when using loops.

Count from m to n

Write a for loop that outputs the integers m to n.

      for (int i = m; i <= n; i++)
      {
         out.println(i);
      }

Count from 10 to 0

Write a for loop that outputs the integers 10 down to 0.

      final int MAX = 10;
      for (int i = MAX; i >= 0; i--)
      {
         out.println(i);
      }

Count from 0 to 10 in increments of 2

Write a for loop that outputs the integers 0 to 10 in increments of 2 (0, 2, 4, 6, 8, 10)

      final int MAX = 10;
      for (int i = 0; i <= MAX; i = i + 2)
      {
         out.println(i);
      }

Count from 0 to n in increments of m

Write a for loop that outputs the integers 0 to n in increments of m; make sure that the number n is output once and only once.

      for (int i = 0; i < n; i = i + m)
      {
         out.println(i);
      }
      out.println(n);

Nested Loops

You can put one loop inside another loop. For example, supposed you wanted to print this:

****
****
****
****

1. for each row
   a. print 4 stars
   b. print a newline

      final int N = 4;
      for (int row = 0; row < N; row++)
      {
         for (int col = 0; col < N; col++)
         {
            output.print("*");
         }
         output.println();
      }

Nested Loops

Supposed you wanted to print this:

    *
   **
  ***
 ****
*****

1. for each row
   a. print some spaces
   b. print some stars
   c. print a new line

      final int N = 5;
      for (int row = 0; row < N; row++)
      {
         // how many spaces?
         int spaces = ???;
         for (???; ???; ???)
         {
            output.print(" ");
         }
         // how many stars?
         int stars = ???;
         for (???; ???; ???)
         {
            output.print("*");
         }
         output.println();
      }

Nested Loops

Supposed you wanted to print this:

    *
   ***
  *****
 *******
*********

1. for each row
   a. print some spaces
   b. print some stars
   c. print a new line

      final int N = 5;
      for (int row = 0; row < N; row++)
      {
         // how many spaces?
         int spaces = ???;
         for (???; ???; ???)
         {
            output.print(" ");
         }
         // how many stars?
         int stars = ???;
         for (???; ???; ???)
         {
            output.print("*");
         }
         output.println();
      }