1.36.tex

\documentclass[a4paper,12pt]{article}
\usepackage{listings}
\lstset{language=Lisp}

\begin{document}
We can the modify \lstinline!fixed-point! definition as,
\begin{lstlisting}
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (cond ((close-enough? guess next) next)
	    (else
	     (newline)
	     (display guess)
	     (try next)))))
    (try first-guess))
\end{lstlisting}
We then find a solution of $x^x = 1000$ by finding a fixed point of \\
$x \mapsto \log(1000)/\lg(x)$.
\begin{lstlisting}
(fixed-point (lambda (x) (/ (log 1000) (log x)))
	     2.0)
\end{lstlisting}
$\rightarrow$
\begin{lstlisting}
2.0
9.965784284662087
3.004472209841214
6.279195757507157
3.759850702401539
5.215843784925895
4.182207192401397
4.8277650983445906
4.387593384662677
4.671250085763899
4.481403616895052
4.6053657460929
4.5230849678718865
4.577114682047341
4.541382480151454
4.564903245230833
4.549372679303342
4.559606491913287
4.552853875788271
4.557305529748263
4.554369064436181
4.556305311532999
4.555028263573554
4.555870396702851
4.555315001192079
4.5556812635433275
4.555439715736846
4.555599009998291
4.555493957531389
4.555563237292884
4.555517548417651
4.555547679306398
4.5555278085162544.555532270803653
\end{lstlisting}
Using average-damping we have,
\begin{lstlisting}
(fixed-point (lambda (x) (/ (+ x
			       (/ (log 1000)
				  (log x)))
			    2))
	     2.0) 
\end{lstlisting}
$\rightarrow$
\begin{lstlisting}
2.0
5.9828921423310435
4.922168721308343
4.628224318195455
4.568346513136242
4.5577305909237005
4.555909809045131
4.5555994116106244.555537551999825
\end{lstlisting}
We could see that the simple version takes $32$ steps whereas the
average-damping version takes only $8$ steps.
\end{document}