Bisection Method in Embedded Systems

Embedeo - embedded systems and microcontroller projects

Main menu

Resources

Abstract

This article explains how to apply a bisection method in embedded systems, in order to avoid division of integer numbers. There are also mentioned: precision vs. speed tradeoff, and splitting of a nonlinear function into linear subranges. Included sample program in C, simulates calculation process and analysis of the maximum error.

by Nedko Iliev, posted:2006.08.07

We take into consideration some non-linear function y=f(x) in a given argument range (a0,a4). The goal of the target program, running on a microcontroller is calculation of y with predictable accuracy. First we split the entire argument range into several subranges [a_i,a_i+1], then we replace each part of the real function by a line g(x), so f(a_i)=g(a_i)=b_i and f(a_i+1)=g(a_i+1)=b_i+1 as it is shown on Fig.1

sample curve of a function
Fig.1

The linear function g(x) is expressed by the following equations:

or

The function is solvable but it involves some division. Additionally the replacement of f(x) by g(x) already involves an error. We can go further by this approach in order to avoid arbitrary division. At next example we'll seek y=f(x_c) but we'll not solve g(x) -equations directly.

part of the curve
Fig.2

We split the subrange along each axis in two equal parts, defining new subranges that are twice smaller. Thus for [a_i,a_i+1] and [b_i,b_i+1] we obtain their middle points x₁=((a_i+a_i+1)/2) and y₁=((b_i+b_i+1)/2), accordingly. Then we compare the given value x_c with the middle of the initial subrange x₁. If (x₁>x_c) then we assume for the next step new subrange [a_i;x₁] for x-axis, and [b_i;y₁] for y-axis, otherwise we shall assume the other new subranges, i.e. [x₁;a_i+1] and [y₁;b_i+1]. We continue splitting and comparison process, until we obtain a middle point on the x-axis exactly equal to x_c or reach certain limit of iterations (splitting and comparison). Of course the last obtained value for y-axis is the value we seek, and we should expect that it is not exact value of the function. Obviously we replace the arbitrary division by additions, comparisons and divisions by 2, and the last one is simply a shift-right operation for a microcontroller.

Download sample code

bisection.zip (5KB)
The zip file includes two files. The file bisection.c is a sample program in plain C for the command line. The program bisectionally finds solution for the sample function y=64*log(x/16), where log means natural logarithm (to base e). The argument x ranges from 32 to 1023. Scalling factors are includded for better resolution. The program also prints the maximum positive and negative errors for the given range of the argument. You can play with it, and observe various aspects of the bisection method. The other file lnsample.xls included in the zip-file, contains a spreadsheet with a graphical representation of the function. The file was created by OpenOffice.org Calc a spreadsheet program, which is part of the free, powerfull, multiplatform and open-source office suite OpenOffice.org

You can mail your questions or comments to:
This is intentionally picture