Numerical Algorithms using Playgrounds

Learn how to use numerical algorithms in iOS by using Playgrounds. By Jean-Pierre Distler.

Leave a rating/review
Save for later
Share

Hopefully you didn’t vomit when read numerical algorithms. If you did, well, look on the bright side … you can have lunch again! :]

In this tutorial, you’ll learn what numerical algorithms are and how to use them to solve problems that don’t have an analytic solution. You’ll also learn how you can use playgrounds to easily visualize the solutions.

If the notion of math doesn’t excite you, nor are you an avid user of physics or computer science, you’ll still find value in this tutorial. All you need is a basic understanding of calculus and some elementary physics.

You’ll learn how to solve two different problems with numerical algorithms, but for the sake of learning, both also allow analytic solutions. Though algorithms are ideal for those times when analytics won’t work, it’s easier to understand how they work when you can compare the two methodologies.

What are Numerical Algorithms?

Simply put, numerical algorithms are methods to solve mathematical problems that don’t rely on a closed-form analytic solution.

What is a Closed-Form Analytic Solution?

It’s any mathematical formula that you use to solve an exact value by plugging in the values you already know and performing a finite set of operations.

More simply put, if you can use algebra to find an expression to solve an unknown value, and all you need to do is substitute the known values and evaluate that expression, then you have a closed-form analytic solution.

When to Use Numerical Algorithms

For many problems, no analytic solution exists. For others, there is, but it would take too long to calculate, and In these cases, you need numerical algorithms. 

For example, imagine that you wrote a physics engine that computes the behavior of many objects in a limited amount of time. In this scenario, you can use numerical algorithms to calculate the behavior much faster.

There is a downside: You pay for the faster calculation with less precise results. But in many cases, the result is good enough.

Weather forecasting is example of an activity that benefits from the use of numerics. Think about how quickly it evolves and how many factors affect it; it’s a highly complex system and only numerical simulations can handle the task of predicting the future.

Maybe a lack of these algorithms is why your iPhone tells you that it’s raining but a look outside says the opposite!
Ah-ha! iPhone weather exists soley to make math look good.

Getting Started

As a warm up, you’ll play a game, and then you’ll calculate the square root of a given number. For both tasks, you’ll use the bisection method. Surprise! You probably know this method, but maybe not by name.

Think back to the childhood game where you choose a number between one and 100, and then someone else has to guess it. The only hint you can give the other person is if the number is bigger or smaller than the guess.

Let’s say you’re guessing what I’ve chosen, and you start with one. I tell you the number is higher. Then you choose two, and again, I tell you it’s higher. Now you choose three, then four, and each time I tell you the number is bigger, until you get to five, which is my number.

After five steps you find the number — not bad — but if I chose 78, this approach would take quite a bit of time.

This game moves much faster when you use the bisection method to find the solution.

The Bisection Method

You know the number is inside the interval [1,100], so instead of making incremental or even random guesses, you divide this interval into two subintervals of the same size: a=[1,50] and b=[51,100].

Then you determine if the number is inside interval a or b by asking if the number is 50. If the number is smaller than 50, you forget interval b and subdivide interval a again.

Then you repeat these steps until you find the number. Here’s an example:

My number is 60, and the intervals are a=[1,50] and b=[51,100].

In the first step, you say 50 to test the upper bound of interval a. I tell you the number is bigger, and now you know that the number is in interval b. Now you subdivide b into the intervals c=[51,75] and d=[76,100]. Again, you take the upper bound of interval c, 75, and my answer is that the number is smaller. This means the number must be in interval c, so you subdivide again

By using this method, you find the number after just seven steps versus 60 steps with the first approach.

  1. 50 -> bigger
  2. 75 -> smaller
  3. 62 -> smaller
  4. 56 -> bigger
  5. 59 -> bigger
  6. 61 -> smaller
  7. 60 -> got it

For the square root of a number x, the process looks similar. The square root is between 0 and x, or expressed as an interval it is (0, x]. If the number is bigger than or equal to 1. You can use the interval [1, x].

Dividing this interval brings you to a=(0, x/2] and b=(x/2, x].

If my number is 9, the interval is [1, 9] the divided intervals are a=[1, 5] and b=(5, 9]. The middle m is (1+9)/2 = 5.

Next, you check if m*m – x is bigger than the desired accuracy. Is this case, you check if m*m is bigger or smaller than x. If it’s bigger, you use the interval (0,x/2] otherwise (x/2,x]

Let’s see this in action, we start with m=5 and a desired accuracy of 0.1:

  1. Calculate m*m-x: 5*5-9 = 16
  2. Check if the desired accuracy is reached: 25-11 <= 0.1 ?
  3. Search next interval: Is m*m greater than x? Yes 25 is greater than 9, now use the interval [1, 5] with a middle of (1+5)/2 = 3
  4. Calculate m*m-x: 3*3-9 = 0
  5. Check if the desired accuracy is reached: 9-9 <= 0.1 ?
  6. Got it.
Note: Are you wondering what the different parentheses mean? An interval has the form (lower bound, upper bound) and the different parentheses tell you if one of these bounds is part of the interval. Round parentheses mean the bound is not inside the interval and brackets mean it’s inside. The interval (0, a] contains a but not zero. In the above example, the interval a contains a/2 but not zero, and b contains everything above a/2 up to a.