03 SOME SIMPLE NUMERICAL PROGRAMS

3.1 Exhaustive Enumeration

What is decrementing function in a loop program block?

The decrementing function in a loop has four properties:

1. It maps a set of program variables into an integer.
2. When the loop is entered, its value is nonnegative.
3. When its value is ≤ 0, the loop terminates.
4. Its value is decreased every time through the loop.

Can we look down the exhaustive enumeration algorithms?

The algorithmic technique used in this program is a variant of guess and check called exhaustive enumeration. We enumerate all possibilities until we get to the right answer or exhaust the space of possibilities. At first blush[^ At first blush], this may seem like an incredibly stupid way to solve a problem. Surprisingly, however, exhaustive enumeration algorithms are often the most practical way to solve a problem. They are typically easy to implement and easy to understand. And, in many cases, they run fast enough for all practical purposes.

[^ At first blush]: At first blush , or At the first blush , at the first appearance or view. “At the first blush, we thought they had been ships come from France.” Hakluyt. This phrase is used now more of ideas, opinions, etc., than of material things.

3.2 For Loops

What is the relationship of for loop mechanism and while loop?

The while loops we have used so far are highly stylized [^ stylized]. Each iterates over a sequence of integers. Python provides a language mechanism, the for loop, that can be used to simplify programs containing this kind of iteration.

[^ stylized]: stylized: depicted or treated in a mannered and nonrealistic style.

3.3 Approximate Solutions and Bisection Search

What is the exhaustive enumeration method for finding the square root?

# x = 25
x = 0.25
epsilon = 0.01
step = epsilon**2
numGuesses = 0
ans = 0.0
# while abs(ans**2 - x) >= epsilon and ans <= x:
while abs(ans**2 - x) >= epsilon and ans*ans <= x:
    ans += step
    numGuesses += 1 
print('numGuesses =', numGuesses) 
if abs(ans**2 - x) >= epsilon:
    print('Failed on square root of', x) 
else:
    print(ans, 'is close to square root of', x)

Exhaustive enumeration method for finding the square root has nothing in common with the way of finding square roots using a pencil that you might have learned in middle school. It is often the case that the best way to solve a problem with a computer is quite different from how one would approach the problem by hand.

Should we be disappointed that the program didn’t figure out that 25 is a perfect square and print 5?

No. The program did what it was intended to do. Though it would have been OK to print 5, doing so is no better than printing any value close enough to 5.

What is the option B when finding exhaustive enumeration algorithm not efficient in some case?

We could try to speed it up by starting closer to the answer, but that presumes that we know the answer. The time has come to look for a different way to attack the problem. We need to choose a better algorithm rather than fine-tune the current one.

What is the bisection search method for finding the square root?

x = 25
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
while abs(ans**2 - x) >= epsilon:
    print('low =', low, 'high =', high, 'ans =', ans) 
    numGuesses += 1
    if ans**2 < x:
        low = ans 
    else:
        high = ans
    ans = (high + low)/2.0
print('numGuesses =', numGuesses) 
print(ans, 'is close to square root of', x)

More important, notice that at each iteration of the loop the size of the space to be searched is cut in half. Because it divides the search space in half at each step, it is called a bisection search. Bisection search is a huge improvement over our earlier algorithm, which reduced the search space by only a small amount at each iteration.

3.4 A Few Words About Using Floats

Why not call it real number in computer system?

In almost modern programming languages non-integer numbers are implemented using a representation called floating point.

How to represent digital number in binary float point?

Modern computers use binary, not decimal, representations. We represent the significant digits and exponents in binary rather than decimal and raise 2 rather than 10 to the exponent. For example, the number 0.625 (5/8) would be represented as the pair (101, -11); because 5/8 is 0.101 in binary and -11 is the binary representation of -3, the pair (101, -11) stands for 5*2-3 = 5/8 = 0.625.

What is the representation of 0.1 in Python floating point?

What about the decimal fraction 1/10, which we write in Python as 0.1? The best we can do with four significant binary digits is (0011, -101). This is equivalent to 3/32, i.e., 0.09375. If we had five significant binary digits, we would represent 0.1 as (11001, -1000), which is equivalent to 25/256, i.e., 0.09765625. How many significant digits would we need to get an exact floating point representation of 0.1? An infinite number of digits! There do not exist integers sig and exp such that sig * 2^-exp equals 0.1.

In most Python implementations, there are 53 bits of precision available for floating point numbers, so the significant digits stored for the decimal number 0.1 will be

11001100110011001100110011001100110011001100110011001

This is equivalent to the decimal number

0.1000000000000000055511151231257827021181583404541015625

Does the difference between real and floating point numbers really matter?

As we have seen, using == to compare two floating point values can produce a surprising result. It is almost always more appropriate to ask whether two floating point values are close enough to each other, not whether they are identical. So, for example, it is better to write abs(x-y) < 0.0001 rather than x == y.

3.5 Newton-Raphson

How to define finding the square root problem in the polynomial formulation?

A polynomial with one variable (by convention, we will write the variable as x) is either 0 or the sum of a finite number of nonzero terms, e.g., 3x2 + 2x + 3. Each term, e.g., 3x2, consists of a constant (the coefficient of the term, 3 in this case) multiplied by the variable (x in this case) raised to a nonnegative integer exponent (2 in this case). The exponent on a variable in a term is called the degree of that term. The degree of a polynomial is the largest degree of any single term. Some examples are, 3 (degree 0), 2.5x + 12 (degree 1), and 3x2 (degree 2). In contrast, 2/x and x0.5 are not polynomials.

If p is a polynomial and r a real number, we will write p(r) to stand for the value of the polynomial when x = r. A root of the polynomial p is a solution to the equation p = 0, i.e., an r such that p(r) = 0. So, for example, the problem of finding an approximation to the square root of 24 can be formulated as finding an x such that x2 – 24 ≈ 0.

What is successive approximation?

Newton proved a theorem that implies that if a value, call it guess, is an ap- proximation to a root of a polynomial, then guess – p(guess)/p’(guess), where p’ is the first derivative of p, is a better approximation.20

For any constant k and any coefficient c, the first derivative of the polynomial cx² + k is 2cx. For example, the first derivative of x² – k is 2x. Therefore, we know that we can improve on the current guess, call it y, by choosing as our next guess y - (y² - k)/2y. This is called successive approximation.

What is Newton-Raphson method code for finding square root?

#Newton-Raphson for square root
#Find x such that x**2 - 24 is within epsilon of 0 epsilon = 0.01
k = 24.0
guess = k/2.0
while abs(guess*guess - k) >= epsilon:
    guess = guess - (((guess**2) - k)/(2*guess)) 
print('Square root of', k, 'is about', guess)

Compare the efficiency of Newton-Raphson and bisection search method?

Square root of 54.0 is about 7.348469483546109