Back to Basics: Successive Approximation in Powershell

In the last few posts we talked about exhaustive enumeration where we try all "possible" values until we find the solution. But what if there is no exact answer? What if we cannot enumerate all of the guesses? What we need is an ability to improve our guesses.

Enter Successive Approximation:

1. Start with a guess
2. Iterate
3. Improve our guess

So how do we do that? We are going to start with something called the Bisection Method. Lets see what Wikipedia has to say:

The bisection method in mathematics is a root-finding method which repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods.^[1] The method is also called the binary search method^[2] and is similar to the computer science Binary Search, where the range of possible solutions is halved each iteration.

The method is applicable when we wish to solve the equation f(x) = 0 for the real variable x, where f is a continuous function defined on an interval [a, b] and f(a) and f(b) have opposite signs. In this case aand b are said to bracket a root since, by the intermediate value theorem, the f must have at least one root in the interval (a, b).

At each step the method divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval and the value of the function f(c) at that point. Unless c is itself a root (which is very unlikely, but possible) there are now two possibilities: either f(a) and f(c) have opposite signs and bracket a root, or f(c) and f(b) have opposite signs and bracket a root. The method selects the subinterval that is a bracket as a new interval to be used in the next step. In this way the interval that contains a zero of f is reduced in width by 50% at each step. The process is continued until the interval is sufficiently small.

As always lets use a problem we can all understand, finding the square root of a real number. Lets write a Bisection search function and test it.

            
function squareRootBi {            
 Param(            
  [parameter(Position=0,             
  Mandatory=$true,             
  HelpMessage="Enter a non-negative number." )]             
  [ValidateScript({$_ -gt 0})]             
  $x,            
  [parameter(Position=1,             
  Mandatory=$true,             
  HelpMessage="Enter upper bound on the relative error." )]             
  [ValidateScript({$_ -gt 0})]            
  $epsilon            
 )            
             
 $low = 0            
 $high = $x            
 $guess = ($low + $high) / 2.0            
 $ctr = 1            
             
 while ([Math]::Abs([Math]::Pow($guess,2) - $x) -gt $epsilon -and $ctr -le 100) {            
  if ([Math]::Pow($guess,2) -lt $x) {            
   $low = $guess # Set the lower bound bisection value            
  } else {            
   $high = $guess # Set the higher bound bisection value            
  }            
              
  $guess = ($low + $high) / 2.0            
  $ctr += 1            
 }            
             
 if ($ctr -ge 100) {            
  Write-Warning "Iteration count exceeded."            
 }            
             
 Write-Host "BiMethod. Number of Iterations was:", $ctr, " and Estimate is: ", $guess            
 return $guess            
}

PS H:\Development\Powershell> squareRootBi -x 9 -epsilon 0.0001            
BiMethod. Number of Iterations was: 18  and Estimate is:  2.9999885559082            
2.9999885559082

Stay tuned for the next post where we dive into a much better way to solve this, the Newton-Raphson Method.

Back to Basics: Recursion

Google recursion and besides for the joke "Did you mean: recursion" you'll find a plethora of examples, definitions, and people showing you how clever they are.

Put simply, recursion is broken down like this:

• Base case - simpliest possible solution
• Inductive step - break problem into a simplier version of the same problem with some other steps to execute.

Ok clear as mud. So as always lets take a problem and break it down.

A lot of examples show recursion using the Fibonacci sequence. However I always liked the "Blastoff!" example from How to Think Like a Computer Scientist.

Alright lets define a function:

function countdown {            
 param(            
  [int]$n            
 )
 if ($n -le 0) {            
  Write-Host "Blastoff!"            
 } else {            
  $n            
  countdown($n-1)            
 }            
}

Now lets source our function and run it:

PS H:\Development\Powershell> . .\recursion.ps1            
PS H:\Development\Powershell> countdown -n 10            
10            
9            
8            
7            
6            
5            
4            
3            
2            
1            
Blastoff!

See recursion isn't so bad after all.

Back to Basics: Brute Force in Powershell

Most of you have heard some variation of this problem:

A farmer has pigs and chickens. When the farmer walks out in the yard he sees 20 heads and 56 legs. How many pigs and chickens does the farmer have?

Based on the information given we can determine a few basic truths:

1.  20 heads. I think we can assume we have no decapitated pigs or chickens so the number of pigs + number of chickens is equal to 20.
2. 56 legs. 4*number of pigs + 2*number of chickens is equal to 56.

So how are we going to solve this in a programmatic way? Lets try a brute force algorithm. That's just another way to say we are going to enumerate and check over and over until we hit a solution. Remember this code is for learning and doesn't follow best practices.

function solve {            
 param(            
 [int]$numLegs,            
 [int]$numHeads            
 )            
             
 foreach ($numChicks in (0..$numHeads + 1)) {            
  $numPigs = $numHeads - $numChicks            
  $totLegs = 4*$numPigs + 2*$numChicks            
  if ($totLegs -eq $numLegs) {            
   return $numPigs, $numChicks            
  }            
 }            
 return            
}            
            
function barnYard {            
 $heads = Read-Host "Enter the number of heads"            
 $legs = Read-Host "Enter the number of legs"            
 $pigs, $chickens = solve -numLegs $legs -numHeads $heads            
 if ($pigs -eq $null) {            
  Write-Host "No pigs"            
 } else {            
  Write-Host "Number of pigs", $pigs            
  Write-Host "Number of chickens", $chickens            
 }            
}

Above is two functions, solve and barnYard. In programming this is called "decomposition". Basically we want to isolate components and break up the code so we can have separation and reuse. Functions also allow us to capture common patterns of computation and refer to it by name. But you already knew that. So lets throw these two functions in a file called farmyard.ps1 and source it.

PS H:\Development\Powershell> . .\farmyard.ps1

Now we can call the functions within the file and solve our farmyard mystery:

PS H:\Development\Powershell> barnYard            
Enter the number of heads: 20            
Enter the number of legs: 56            
Number of pigs 8            
Number of chickens 12

I'll leave you with a few words from Wikipedia on the subject:

Brute-force search is typically used when the problem size is limited, or when there are problem-specific heuristics that can be used to reduce the set of candidate solutions to a manageable size. The method is also used when the simplicity of implementation is more important than speed. This is the case, for example, in critical applications where any errors in the algorithm would have very serious consequences; or when using a computer to prove a mathematical theorem. Brute-force search is also useful as "baseline" method when benchmarking other algorithms or metaheuristics. Indeed, brute-force search can be viewed as the simplest metaheuristic.