Partial Answers to Rec 10

10.2
> (setq a 1L0)
1.0L0
> (setq b -1L0)
-1.0L0
> (setq c -1L0)
-1.0L0
> (setq r1 (/ (+ (- b) (sqrt (- (* b b) (* a c 4L0)))) (* 2L0 a) ))
1.6180339887498948482L0
> (setq r1 (/ (- (- b) (sqrt (- (* b b) (* a c 4L0)))) (* 2L0 a) ))
-0.6180339887498948482L0
------------------------------------------
10.3 
> (defun harm (n)
   (cond
      ((= n 1) 1)
      (t (+ (/ 1 n) (harm (1- n)))) ))
HARM
> (harm 10)
7381/2520
> (harm 20)
55835135/15519504
------------------------------------------
> (defun harm (n)
   (cond
      ((= n 1) 1L0)
      (t (+ (/ 1L0 n) (harm (1- n)))) ))
HARM
> (harm 10)
2.9289682539682539684L0
------------------------------------------
10.4
> (defun f(n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (t (+ (f (1- n)) (f (- n 2)))) ))
F
> (f 10)
55
> (f 20)
6765
> (f 30)
832040    (6 seconds)
> (f 35)
9227465    (70 seconds)
(after compiling)
> (f 30)
832040    (2 seconds)
> (f 35)
9227465   (12 seconds)
------------------------------------------
10.5
> (defun pow (a b)
    (cond ((= b 0) 1L0)
          ((> b 0)(* a (pow a (- b 1))))
          (t (pow (/ 1L0 a) (- b)  )) ))
POW
> (pow 2 -10)
9.765625L-4
> (pow (pow 2 -10) 10)
7.888609052210118054L-31
> (pow (pow 2 -10) -10)
1.2676506002282294015L30
------------------------------------------
10.6
> (defun pow (a b)
   (cond ((= b 0) 1)
         (t (* (pow a (1- b)) a)) ))
POW
> (SETF (EXT:LONG-FLOAT-DIGITS) 200)
200
(setq phi (/ (+ 1L0 (sqrt 5l0)) 2L0))
1.6180339887498948482045868343656381177203091798057628621354486227053L0
> (pow phi 100)
7.920708398483722531269999999999999999999987374866619361570578109776L20 =
 792070839848372253126.9999999999999999999987374866619361570578109776
> (pow phi 121)
1.9386725908489881939795601000000000000000000000000051581685567756328L25 =
 19386725908489881939795601.000000000000000000000000051581685567756328
------------------------------------------
10.7 a. b.
> (defun sqr (a) (* a a))
SQR
> (defun rtp (a b)
    (princ '|rtp: |)(prin1 a)(princ '| |)(prin1 b)(terpri)
    (cond ((= b 0) 1)
          ((< b 0) (rtp (/ 1 a) (- b)  ))
          ((= (rem b 2) 0) (sqr (rtp a (/ b 2))))
          (t (* a (sqr (rtp a (/ (1- b) 2)))))  ))
RTP
> (rtp 7 23)
rtp: 7 23
rtp: 7 11
rtp: 7 5
rtp: 7 2
rtp: 7 1
rtp: 7 0
27368747340080916343
> (rtp 2 2143)
rtp: 2 2143
rtp: 2 1071
rtp: 2 535
rtp: 2 267
rtp: 2 133
rtp: 2 66
rtp: 2 33
rtp: 2 16
rtp: 2 8
rtp: 2 4
rtp: 2 2
rtp: 2 1
rtp: 2 0
12802085044961478795367571515013465982477677008083
84824056269949281586845410140428570655004658446632
17115625587381358460356660450871918720939240888175
21157218784499258411228140630521692744111953045073
80386406346930112508549825064495772572662547879518
87861005682689570699797323898341140889108998361924
62645988744432003160564221763543176511199745637764
07204040441178038071701226728913070775474376251696
74752813376649485322074152735268053901445951599049
82757572048233702695783419566230729778749768048644
41052868382689183762460103808291244046216190050982
24654867352342211981863619663261440116394432831863
8946715429911315024874141425080268348832350208
--------------------------------------------------
(646 digits, newlines added)
log10(22143) = log10(2)*2143 = 0.30103*2143 = 645.10728
--------------------------------------------------
         11111111112222222222333333333344444444445
12345678901234567890123456789012345678901234567890
--------------------------------------------------


------------------------------------------
10.7 c.
  At each recursive call, b is divided by 2, so b gets down to 1 in log2(b) calls.
  Specifically,
     if b = 2143, then log2(b) = 11.0654
     if b = 106, then log2(b) = 19.93157 = 20 (approx)
  -------------------------------------------------
  Thus rtp is a O(log b) algorithm.
  Notice that the pow algorithm is only O(b).
------------------------------------------