loop-invariants/1/div.cs - Division by repeated subtraction.

Lecture 13 - slide 32 : 32 Program 1

using System;

class LoopInvariantDemo{

  static int Div(int x, int y){
    // require x >= 0 && y > 0;   

    int rest = x;
    int quotient = 0;
    
    while (rest >= y) {
      // invariant rest + quotient * y = x;   
      rest = rest - y;
      quotient = quotient + 1;
    }
    return quotient;
    // ensure  rest + quotient * y = x && rest < y && rest >= 0;   
  } 

  public static void Main(){
    Console.WriteLine("Div({0}, {1}) = {2}", 10, 2, Div(10, 2));
    Console.WriteLine("Div({0}, {1}) = {2}", 100, 25, Div(100, 25));
    Console.WriteLine("Div({0}, {1}) = {2}", 1234567, 89, Div(1234567, 89));
  }

}