#lang racket

;;;;;;;;;;
;; 1.35 ;;
;;;;;;;;;;

(define tolerance 0.00001)
(define (close-enough? v1 v2)
  (< (abs (- v1 v2)) tolerance))

(define (fixed-point f first-guess)
  (define (try guess)
    (let ([next (f guess)])
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))

;; phi is the root of x ^ 2 - x - 1.  So it is the fixed point of f(x) = 1 + 1 / x.

(/ (+ 1 (sqrt 5)) 2) ; phi
;; 1.618033988749895

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
;; 1.6180327868852458

;;;;;;;;;;
;; 1.36 ;;
;;;;;;;;;;

(define (new-fixed-point f first-guess)
  (define (try guess)
    (displayln guess)
    (let ([next (f guess)])
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))

(define soln
  (new-fixed-point (lambda (x) (/ (log 1000) (log x)))
                   2.0)) ; took 24 iterations
;; 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.555527808516254
;; 4.555540912917957

(expt soln soln) ; should be 1000
;; 999.9913579312362

(define (average a b)
  (/ (+ a b) 2))

(define (new-damped-fixed-point f first-guess)
  (define (try guess)
    (displayln guess)
    (let ([next (average guess (f guess))])
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))

(define damped-soln
  (new-damped-fixed-point (lambda (x) (/ (log 1000) (log x)))
                          2.0)) ; took 9 iterations
;; 2.0
;; 5.9828921423310435
;; 4.922168721308343
;; 4.628224318195455
;; 4.568346513136242
;; 4.5577305909237005
;; 4.555909809045131
;; 4.555599411610624
;; 4.5555465521473675

(expt damped-soln damped-soln) ; should be 1000
;; 1000.0046472054871

;;;;;;;;;;
;; 1.37 ;;
;;;;;;;;;;

(define (cont-frac n d k)
  (define (get-tail i) ; return n(i) / [d(i) + ...]
    (if (= i k)
      (/ (n k) (d k))
      (/ (n i) (+ (d i) (get-tail (add1 i))))))
  (get-tail 1))

(define (estimate-one-over-phi k)
  (cont-frac (lambda (i) 1.0)
             (lambda (i) 1.0)
             k))

(/ 2 (add1 (sqrt 5))) ; this is 1 / phi
;; 0.6180339887498948

(for ([k (in-range 1 15)]) (displayln (estimate-one-over-phi k)))
;; 1.0
;; 0.5
;; 0.6666666666666666
;; 0.6000000000000001
;; 0.625
;; 0.6153846153846154
;; 0.6190476190476191
;; 0.6176470588235294
;; 0.6181818181818182
;; 0.6179775280898876
;; 0.6180555555555556 ; k = 11 gives four places of accuracy
;; 0.6180257510729613
;; 0.6180371352785146
;; 0.6180327868852459

(define (iterative-cont-frac n d k)
  (define (iter i tail)
    ; the invariant is tail = n(i + 1) / [d(i + 1) + ...]
    (if (zero? i)
      tail
      (iter (sub1 i) (/ (n i) (+ (d i) tail)))))
  (iter k 0))

(define (iterative-estimate-one-over-phi k)
  (iterative-cont-frac (lambda (i) 1.0)
                       (lambda (i) 1.0)
                       k))

(for ([k (in-range 1 10)]) (displayln (iterative-estimate-one-over-phi k)))
;; 1.0
;; 0.5
;; 0.6666666666666666
;; 0.6000000000000001
;; 0.625
;; 0.6153846153846154
;; 0.6190476190476191
;; 0.6176470588235294
;; 0.6181818181818182

;;;;;;;;;;
;; 1.38 ;;
;;;;;;;;;;

(exp 1) ; this is e
;; 2.718281828459045

(define (euler-n i) 1)
(define (euler-d i)
  (if (= (remainder i 3) 2)
    (* 2 (/ (add1 i) 3))
    1))

(define (estimate-e k)
  (+ 2.0 (cont-frac euler-n euler-d k)))

(for ([k (in-range 1 10)]) (displayln (estimate-e k)))
;; 3.0
;; 2.666666666666666
;; 2.75
;; 2.714285714285714
;; 2.71875
;; 2.717948717948718
;; 2.718309859154929
;; 2.718279569892473
;; 2.718283582089552

;;;;;;;;;;
;; 1.39 ;;
;;;;;;;;;;

(define (tan-cf x k)
  (define (n i)
    (if (= i 1)
      x
      (- (sqr x))))
  (define (d i)
    (sub1 (* 2 i)))
  (cont-frac n d k))

(tan pi)
;; -1.2246467991473532e-016
(tan-cf pi 10)
;; -1.893214149359168e-009

(tan (/ pi 4))
;; 0.9999999999999999
(tan-cf (/ pi 4) 10)
;; 1.0