iterationschemelispracketsicp# Using fixed point to show square root

In going through the exercises of SICP, it defines a fixed-point as a function that satisfies the equation F(x)=x. And iterating to find where the function stops changing, for example `F(F(F(x)))`

.

The thing I don't understand is how a square root of, say, 9 has anything to do with that.

For example, if I have `F(x) = sqrt(9)`

, obviously x=3. Yet, how does that relate to doing:

```
F(F(F(x))) --> sqrt(sqrt(sqrt(9)))
```

Which I believe just converges to zero:

```
>>> math.sqrt(math.sqrt(math.sqrt(math.sqrt(math.sqrt(math.sqrt(9))))))
1.0349277670798647
```

Since F(x) = sqrt(x) when x=1. In other words, how does finding the square root of a constant have anything to do with finding fixed points of functions?

Solution

When calculating the square-root of a number, say `a`

, you essentially have an equation of the form `x^2 - a = 0`

. That is, to find the square-root of `a`

, you have to find an `x`

such that `x^2 = a`

or `x^2 - a = 0`

-- call the latter equation as (1). The form given in (1) is an equation which is of the form `g(x) = 0`

, where `g(x) := x^2 - a`

.

To use the fixed-point method for calculating the roots of this equation, you have to make some *subtle modifications* to the existing equation and bring it to the form `f(x) = x`

. One way to do this is to rewrite (1) as x = a/x -- call it (2). Now in (2), you have obtained the form required for solving an equation by the fixed-point method: f(x) is a/x.

Observe that this method requires both sides of the equation to have an 'x' term; an equation of the form `sqrt(a) = x`

doesn't meet the specification and hence can't be solved (iteratively) using the fixed-point method.

The thing I don't understand is how a square root of, say, 9 has anything to do with that.

For example, if I have F(x) = sqrt(9), obviously x=3. Yet, how does that relate to doing: F(F(F(x))) --> sqrt(sqrt(sqrt(9)))

These are standard methods for numerical calculation of roots of non-linear equations, quite a complex topic on its own and one which is usually covered in Engineering courses. So don't worry if you don't get the "hang of it", the authors probably felt it was a good example of iterative problem solving.

- How should I loop over the elements of a C++ container in reverse order?
- Excel 2013 vba refresh chart content after each iteration of For Loop
- Loop (for each) over an array in JavaScript
- Fastest way to iterate over all the chars in a String
- Taking the value of the node above in xsl for-each loop
- Generate all permutations: Why is the yielded value in recursion not in the output?
- Erasing nodes of a std::map within a range-based "for" loop
- Conditionally concatenate strings in vector based on a value in secondary vector in R
- Combine census tracts with neighbor to reach a population threshold in R
- Debugging iteration (closures) in Groovy with IntelliJ IDEA
- How to remove elements from list while iterating
- How to flatten a list of objects in python
- JavaScript Set vs. Array performance
- Is if(items != null) superfluous before foreach(T item in items)?
- How to remove items from a list while iterating?
- How do I make an infinite while loop in JavaScript?
- How to auto populate the address in json
- Laravel foreach only returns first value
- Iterating array of objects and joining the key values with commas
- SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process
- R: Improving Implementation Simple Model
- Angular Content Projection with iteration
- Way to go from recursion to iteration
- How subtract a Dataframe with totals another Dataframe based on condition and until 0
- Read nested list with other attributes in Java streams
- R code to iterate over lists, combining them into a data frame with grouping variables?
- Iteratively convert an arbitrary depth list to a dict
- TestDome - Malware Analysis in C++
- Java LinkedHashSet backwards iteration
- Iterate an array as a pair (current, next) in JavaScript