Computing Square Root, Fixed Point Iteration & Lisp

A function is said to have reached a fixed point when f(y) = y.
We can use this to find the square root of a function.

• Guess a value for the square root , say y
• Find the value of Avg(y, x/y ). If it is same as y, then we are done.
• Else assign Avg(x/y, y ) to y ( the new improved value ). Go back to Step 2.

Note that when y = Avg(x/y, y) the value of y that is possible is sqrt(x).So when the fixed point for the above function is reached, the value y is the square root.

So, if we have a black box which computes the fixed point of any function, then
we can pass to this black box , the function Avg(x/y, y ) & find it's fixed point.

Thus, in terms of a functional language , if we have a function for computing the fixed point, we can pass any function ( Avg in this case ) to it to be able to get the desired value. In terms of LISP, this would imply we write a higher-order procedure which takes in another procedure as input [ function here being a first class value ] and returns the fixed point.

Note that fixed point iteration that we use here is exactly the same as that used for data flow analysis in any control flow graph [ lattice of functions ? ]

As an aside , the kinds of abstraction that LISP supports : Black Box Abstraction (Higher order procedures ), Conventional Interfaces ( Generics, OOPs ), Meta-linguistic Abstraction ( being able to write other programming languages in LISP ,eg logic programming language, register machines )

[Reference]

Radix Exchange Sort , Straight Radix Sort & Induction

Radix Exchange Sort :

Sorts beginning from the most significant digit and then for each list, inductively sort the remaining digits by forming lists within each list . For eg, to sort : 12 45 67 22 14 6 23 90 11

First form lists from 0 to 9 for the 10's place :
0 : 06
1 : 12 14 11
2 : 22 23
3 :
4 : 45
5 :
6 : 67
7 :
8 :
9 : 90

Then for each list, form lists within for the unit's place
For eg, for list 1 : ( lists based on unit's place )
0 :
1 : 11
2 : 12
3 :
4 : 14
5 :
Now read off all numbers in order : 06 11 12 14 22 23 45 67 90

Straight Radix Sort :

This is the traditional sorting taught in class based on sorting beginning at the least significant digit. The point here to note is that you need to form a list of numbers one for each kind of digit ( 10 lists for the decimal system ) only once and then you need one more queue for holding the numbers at the end of each pass.

This sorting is based on induction in the sense : Assume you have sorted the least i digits and now you have two numbers starting at the (i + 1)th digit as u = a[i digits] and v = b[i digits] with a = b . Now since u and v are sorted in the least i digits , if [ i digit - u] < [ i digit - v ] then u would precede v in the queue already and the current sort phase would not disturb the order in this pass and hence it would remain sorted.

For eg if u = 6789 and v = 6098 , then in the queue v would precede u ( as 098 < 789 ) and in this phase first v would be put in list 6 followed by u. Hence the numbers would remain sorted.

Its complexity is O(kn) where k is the max # of digits in any input number and n is the total size of input ( k passes, at every pass , all numbers are relocated )