SICP 演習問題 1.3
Exercise 1.29
;h = (b-a)/n
;y_k=func(a+kh)
;sum = (y_0 + 4y_1 + 2y_2 + 4y_3 + ... + y_n)
;
#lang Racket
(define (simpthon a b func n)
(* (/ (h a b n) 3)
(sum-simpthon a b func 0 n)))
(define (sum-simpthon a b func k n)
(if (> k n)
0
(+ (cond ((or (= k 0) (= k n)) (y a b func k n))
((odd? k) (* 4 (y a b func k n)))
((even? k) (* 2 (y a b func k n))))
(sum-simpthon a b func (+ k 1) n))))
(define (h a b n) (/ (- b a) n))
(define (y a b func k n) (func (+ a (* k (h a b n)))))
(define (odd? k) (= (remainder k 2) 1))
(define (even? k) (= (remainder k 2) 0))
(define (linear x) x)
(define (square x) (* x x))
(simpthon 0 1 linear 1)
(simpthon 0 1 linear 10)
(simpthon 0 1 linear 100)
(simpthon 0 1 square 10)
Exercise 1.30
#lang Racket
(define (sum term a next b)
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))
(define (sum2 term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
(define (square x) (* x x))
(define (step x) (+ x 1))
(sum square 1 step 4)
(sum2 square 1 step 4)
Exercise 1.31
1.31a
#lang Racket
(require racket/flonum)
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
(define (factorial n) (product abs 1 inc n))
(define (inc x) (+ x 1))
(define (pi n) (* 4 (product wallis 2 inc n)))
(define (wallis x)
(fl/ (->fl (wallis-even x))
(->fl (wallis-odd x))))
(define (wallis-even x) (if (odd? x) (+ x 1) x))
(define (wallis-odd x) (if (even? x) (+ x 1) x))
(factorial 5)
(pi 1000000)
1.31b
#lang Racket
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
Exercise 1.32
1.32a
;sum (define (sum term a next b) (accumlate + 0 term a next b)) ;product (define (product term a next b) (accumulate * 1 term a next b))
1.32b
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner
(term a)
(accumulate combiner null-value term (next a) next b))))
Exercise 1.33
#lang Racket
(define
(filtered-accumulate combiner null-value filter term a next b)
(define (iter a result)
(cond ((> a b) result)
((filter a) (iter (next a) (combiner (term a) result)))
(else (iter (next a) result))))
(iter a null-value))
1.33a
#lang Racket
(define (prime-square-sum a b)
(filtered-accumulate + 0 prime? square a inc b))
(define (prime? n) (= n (smallest-divisor n)))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(define (divides? a b) (= (remainder b a) 0))
(define (square n) (* n n))
(define (next n) (if (= n 2) 3 (+ n 2)))
(define (inc x) (+ x 1))
(prime-square-sum 1 5)
1.33b
#lang Racket (define (disjoint-product n) (define (disjoint? x) (= (gcd x n) 1)) (filtered-accumulate * 1 disjoint? abs 1 inc n)) (disjoint-product 6)
Exercise 1.33
#lang Racket
(define
(filtered-accumulate combiner null-value filter term a next b)
(define (iter a result)
(cond ((> a b) result)
((filter a) (iter (next a) (combiner (term a) result)))
(else (iter (next a) result))))
(iter a null-value))
a
#lang Racket
(define (prime-square-sum a b)
(filtered-accumulate + 0 prime? square a inc b))
(define (prime? n) (= n (smallest-divisor n)))
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(define (divides? a b) (= (remainder b a) 0))
(define (square n) (* n n))
(define (next n) (if (= n 2) 3 (+ n 2)))
(define (inc x) (+ x 1))
(prime-square-sum 1 5)
b
#lang Racket (define (disjoint-product n) (define (disjoint? x) (= (gcd x n) 1)) (filtered-accumulate * 1 disjoint? abs 1 inc n)) (disjoint-product 6)
Excercise 1.34
(2 2) はひょうかできましぇん
#lang racket (define (f g) (g 2)) (define (square x) (* x x)) (f square) (f (lambda (z) (* z (+ z 1)))) (f f)
1.35
#lang Racket
(require racket/flonum)
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (fl+ 1.0 (fl/ 1.0 x))) 1.0)
1.36
#lang Racket
(require racket/flonum)
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(display "***")(display guess)(newline)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (fl/ (log 1000) (log x))) 1.1)
(define (average x y) (/ (+ x y) 2))
(fixed-point (lambda (x) (average x (fl/ (log 1000) (log x)))) 1.1)
tolerance 0.00001 38 steps (4.555538934848503) vs 14 steps (4.555536364911781)
tolerance 0.00000000000001 87 steps (4.555535705195124) vs 27 steps (4.555535705195128)
1.37
a
#lang Racket
(require racket/flonum)
(define (cont-frac-try n d k i)
(if (> i k) 0.0
(fl/ (n i) (fl+ (d i) (cont-frac-try n d k (+ i 1))))))
(define (cont-frac n d k)
(cont-frac-try n d k 1))
(cont-frac (lambda (i) 1.0) (lambda(i) 1.0) 11)
(cont-frac (lambda (i) 1.0) (lambda(i) 1.0) 12)
(cont-frac (lambda (i) 1.0) (lambda(i) 1.0) 13)
b
(define (cont-frac n d k)
(define (cont-frac-try i result)
(if (<= i 0)
result
(cont-frac-try (- i 1) (/ (n i) (+ (d i) result)))))
(cont-frac-try k 0.0))
1.38
(define (dfc k)
(+ 2
(cont-frac
(lambda (x) 1.0)
(lambda (x)
(cond ((= (remainder x 3) 2) (* (+ (floor(/ x 3)) 1) 2))
(else 1.0)))
k)))
(dfc 1000)
1.39
#lang Racket
(require racket/flonum)
(define (tan-cf x k)
(define (tan-cf-try i)
(if (> i k)
0
(/ (* x x)
(- (- (* i 2) 1) (tan-cf-try (+ i 1))))))
(/ x (- 1 (tan-cf-try 2))))
(define pi 3.141592)
(tan-cf (/ pi 4) 1000)
(tan-cf (/ pi 3) 1000)
(tan-cf pi 1000)
1.40
#lang Racket
(define dx 0.00001)
(define tolerance 0.00001)
(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
(define (newton-transform g)
(lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
(define (cubic a b c) (lambda (x) (+ (* x x x) (* a x x) (* b x) c)))
(newtons-method (cubic -3 3 -1) 1.1)
(newtons-method (cubic -6 12 -8) 1.1)
1.41
#lang racket (define (double f) (lambda (x) (f (f x)))) (define (inc x) (+ x 1)) ((double inc) 1) (((double (double double)) inc) 5)
(((double (double double)) inc) 5) (((double (lambda (x) (double (double x)))) inc) 5) (((lambda (x) (double (double (double (double x))))) inc) 5) ((double (double (double (double inc)))) 5) ((double (double (double (lambda (x) (inc (inc x)))))) 5) ((double (double (lambda (x) (inc (inc (inc (inc x))))))) 5) ((double (lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc x)))))))))) 5) ((lambda (x) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc x))))))))))))))))) 5) (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc (inc 5)))))))))))))))))
1.42
#lang racket (define (compose f g) (lambda (x) (f (g x)))) (define (square x) (* x x)) (define (inc x) (+ x 1)) ((compose square inc) 6)
1.43
#lang Racket
1.44
#lang Racket
(define dx 0.0001)
(define (smooth f)
(lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))
(define (repeated f n)
(if (<= n 1)
(lambda (x) (f x))
(compose f (repeated f (- n 1)))))
(define (n-fold-smooth f n) ((repeated smooth n) f))
1.45
#lang Racket
(define tolerance 0.00001)
(define (repeated f n)
(if (<= n 1)
(lambda (x) (f x))
(compose f (repeated f (- n 1)))))
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (average-damp f) (lambda (x) (average x (f x))))
(define (average x y) (/ (+ x y) 2))
(define (pow x n)
(if (<= n 0) 1 (* x (pow x (- n 1)))))
(define (n-root x n k)
(fixed-point
((repeated average-damp k)
(lambda (y) (/ x (pow y (- n 1)))))
1.1 ))
(n-root 2 2 1)
(n-root 2 3 1)
(n-root 2 4 2)
(n-root 2 5 2)
(n-root 2 6 2)
(n-root 2 7 2)
(n-root 2 8 3)
(n-root 2 10 3)
(n-root 2 15 3)
(n-root 2 16 4)
(n-root 2 20 4)
(n-root 2 30 4)
(n-root 2 31 4)
(n-root 2 32 5)
(n-root 2 40 5)
(n-root 2 63 5)
(n-root 2 64 6)
log2(n) の模様 したがって
#lang Racket
(define tolerance 0.00001)
(define (repeated f n)
(if (<= n 1)
(lambda (x) (f x))
(compose f (repeated f (- n 1)))))
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(define (average-damp f) (lambda (x) (average x (f x))))
(define (average x y) (/ (+ x y) 2))
(define (pow x n)
(if (<= n 0) 1 (* x (pow x (- n 1)))))
(define (log2 x)
(/ (log x) (log 2)))
(define (n-root x n)
(fixed-point
((repeated average-damp (floor (log2 n)))
(lambda (y) (/ x (pow y (- n 1)))))
1.1 ))
Excercise 1.46
#lang Racket
(define (iterative-improve evaluate improve)
(lambda (x)
(let ((next (improve x)))
(if (evaluate x next)
next
((iterative-improve evaluate improve) next)))))
(define tolerance 0.00001)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (sqrt x)
((iterative-improve
close-enough?
(lambda (y)
(/ (+(/ x y) y) 2))) 1.0))
(define (fixed-point f first-guess)
((iterative-improve
close-enough?
f)
first-guess))
SICP 演習問題 1.2
Exercise 1.9
(define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) (+ 4 5) (inc (+ 3 5)) (inc (inc (+ 2 5))) (inc (inc (inc (+ 1 5)))) (inc (inc (inc (inc (+ 0 5))))) (inc (inc (inc (inc 5)))) (inc (inc (inc 6)) (inc (inc 7) (inc 8) 9
(define (+ a b) (if (= a 0) b (+ (dec a) (inc b)))) (+ 4 5) (+ (dec 4) (inc 5)) (+ 3 (inc 5)) (+ (dec 3) (inc (inc 5))) (+ 2 (inc(inc 5))) (+ (dec 2) (inc (inc (inc 5)))) (+ 1 (inc (inc (inc 5)))) (+ (dec 1) (inc (inc (inc (inc 5))))) (+ 0 (inc (inc (inc (inc 5))))) (inc (inc (inc (inc 5)))) 9
反復
Exercise 1.10
(A 1 10) (A 0 (A 1 9) (A 0 (A 0 A(1 8))) (A 0 (A 0 A(0 A(1 7)))) ... 1024
(A 2 4) (A 1 (A 2 3)) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A 0 (A 1 1)))) (A 1 (A 1 (* 2 2))) (A 1 (A 0 (A 1 3))) (A 1 (A 0 (A 0 (A 1 2)))) ... 2^16
(A 3 3) (A 2 (A 3 2)) (A 2 (A 2 (A 3 1))) (A 2 (A 2 2)) (A 2 (A 1 (A 2 1))) (A 2 (A 1 2)) (A 2 (A 0 (A 1 1))) (A 2 (A 0 2)) (A 2 4) ... 2^16
(define (f n) (A 0 n)) (f n) -> 2n (define (g n) (A 1 n)) (g n) -> 2^n (define (h n) (A 2 n)) (h n) -> 2^(2^n)
2の2のn乗乗？？
Exercise 1.11
(define (f n) (cond (< n 3) n) (else (+ (f (- n 1)) (f (- n 2)) (f (- n 3)))) )
Excercise 1.12
#lang racket (define (pascal x y) (cond ((< y 1) 0) ((> y x) 0) ((= y 1) 1) ((= y x) 1) (else (+ (pascal (- x 1) (- y 1)) (pascal (- x 1) y)))))
Exercise 1.13
Fib(0)=0 Fib(1)=1 Fib(n)=Fib(n-1)+Fib(n-2) Fib(n)=(φ^(n) - ψ^(n))/a ( a = 5^(1/2) ) を証明 n=0のとき、n=1のとき、成立 Fib(k) = (φ^(k) - ψ^(k))/a Fib(k+1) = (φ^(k+1) - ψ^(k+1))/a が成立すると仮定して、 Fib(k+2)のとき Fib(k+2)=(φ^(k+2) - ψ^(k+2))/a を示す. Fib(n+2) = ( φ^(n+1) - ψ^(n+1) + φ^(n) - ψ^(n) )/a = ( φ^n(φ+1)-ψ^n(ψ+1) )/a = (φ^(k+2) - ψ^(k+2))/a ∵ φ+1 = φ^2 , ψ+1 = ψ^2 よって帰納法により、 Fib(n)=(φ^(n) - ψ^(n))/a
Exercise 1.14
はれないので省略
Exercise 1.15
12.15/3 = 4.05 4.05/3 = 1.35 1.35/3 = 0.45 0.45/3 = 0.15 0.15/3 = 0.03
4回
aに対しては3を底とする対数のオーダーなのでO(logn)となる。
Exercise 1.16
(define (fast-expt b n) (expt-iter 1 b n )) (define (expt-iter a b n) (cond ((= n 0) a) ((even? n) (expt-iter (* (square b) a) b (/ n 2))) (else (expt-iter (* b a) b (- n 1)))))
Exercise 1.17
(define (fast-* a b) (cond (= b 0) 0 (even? n) (+ (double a) (* a (halve b) )) (else (+ a (* a (- b 1) )))))
Exercise 1.18
(define (fast-* a b c) (cond (= b 0) 0 (even? n) (* a (halve b) (+ (double a) c) ) (else (* a (- b 1) (+ a c) ))))
Exercise 1.19
a <- bq + aq + ap b <- bp + aq a <- (bp+aq)q + (bq + aq + ap)q + (bq + aq + ap)p = bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2 = b(2pq + q^2) + a(2q^2 + 2pq + p^2) = b(2pq + q^2) + a(2pq+q^2) + a(q^2+p^2) b <- (bp + aq)p + (bq + aq + ap)q = b(p^2 + q^2) + a(2pq + q^2) i.e. P' = (p^2 + q^2) q' = (2pq + q^2)
(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (* p p) (* q q)) (+ (* 2 p q) (* q q)) (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b q) (* a q)) p q (- count 1)))))
Exercise 1.20
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b))))
適用順
(gcd 206 40) (gcd 40 (remainder 206 40)) (gcd 40 6) (gcd 6 (remainder 40 6)) (gcd 6 4) (gcd 4 (remainder 6 4)) (gcd 4 2) (gcd 2 (remainder 4 2)) (gcd 2 0) 2
正規化順
(gcd 206 40) (gcd 40 (remainder 206 40)) (if (= (remainder 206 40) 0) 40 (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) (if (= 6 0) 40 (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))) (if (= (remainder 40 (remainder 206 40)) 0) (remainder 206 40) (gcd (remainder 40 (remainder 206 40)) (remainde 6 (remainder 40 (remainder 206 40)))))
Exercise 1.21
#lang racket (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (next test-divisor))))) (define (divides? a b) (= (remainder b a) 0)) (define (prime? n) (= n (smallest-divisor n))) (define (square n) (* n n)) (define (next n) (+ n 1)) (smallest-divisor 199) ;->199 (smallest-divisor 1999) ;->1999 (smallest-divisor 19999) ;->7
Exercise 1.22
#lang Racket (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (next test-divisor))))) (define (divides? a b) (= (remainder b a) 0)) (define (prime? n) (= n (smallest-divisor n))) (define (square n) (* n n)) (define (next n) (+ n 1)) (define (timed-prime-test n) (newline) (display n) (start-prime-test n (current-inexact-milliseconds))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1)) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (define (runtime) (current-milliseconds)) (timed-prime-test 1009) (timed-prime-test 1013) (timed-prime-test 1019) (timed-prime-test 10007) (timed-prime-test 10009) (timed-prime-test 10037) (timed-prime-test 100003) (timed-prime-test 100019) (timed-prime-test 100043) (timed-prime-test 1000003) (timed-prime-test 1000033) (timed-prime-test 1000037)
結果
1009 *** 0.1689453125 1013 *** 0.004150390625 1019 *** 0.00390625 10007 *** 0.01220703125 10009 *** 0.010986328125 10037 *** 0.010986328125 100003 *** 0.031982421875 100019 *** 0.031982421875 100043 *** 0.031982421875 1000003 *** 0.10009765625 1000033 *** 0.10009765625 1000037 *** 0.10009765625
1009だけ異様に遅い。。。
他はおおむね理論通り。
Exercise 1.23
#lang racket (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (next test-divisor))))) (define (divides? a b) (= (remainder b a) 0)) (define (prime? n) (= n (smallest-divisor n))) (define (square n) (* n n)) (define (next n) (cond ((= n 2) 3) (else (+ n 2)))) (define (timed-prime-test n) (newline) (display n) (start-prime-test n (current-inexact-milliseconds))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1)) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (timed-prime-test 1009) (timed-prime-test 1013) (timed-prime-test 1019) (timed-prime-test 10007) (timed-prime-test 10009) (timed-prime-test 10037) (timed-prime-test 100003) (timed-prime-test 100019) (timed-prime-test 100043) (timed-prime-test 1000003) (timed-prime-test 1000033) (timed-prime-test 1000037)
結果
1009 *** 0.200927734375 1013 *** 0.003173828125 1019 *** 0.0029296875 10007 *** 0.007080078125 10009 *** 0.005859375 10037 *** 0.007080078125 100003 *** 0.01904296875 100019 *** 0.01904296875 100043 *** 0.02001953125 1000003 *** 0.06005859375 1000033 *** 0.06005859375 1000037 *** 0.05908203125
半分ではなく、3：2ぐらいの減り具合。 これは(next n) のオーバヘッドのせいではないか。
Exercise 1.24
#lang Racket (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (square a) (* a a)) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a)) (try-it (+ 1 (random (- n 1))))) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false))) (define (timed-prime-test n) (newline) (display n) (start-prime-test n (current-inexact-milliseconds))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) -1)) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (timed-prime-test 1009) (timed-prime-test 1013) (timed-prime-test 1019) (timed-prime-test 10007) (timed-prime-test 10009) (timed-prime-test 10037) (timed-prime-test 100003) (timed-prime-test 100019) (timed-prime-test 100043) (timed-prime-test 1000003) (timed-prime-test 1000033) (timed-prime-test 1000037)
Exercise 1.25
巨大な数の演算をしてしまう。。。
#lang Racket (define (expmod base exp m) (cond ((= exp 0) 1) (( even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (square a) (* a a)) (define (expmod2 base exp m) (remainder (fast-expt base exp) m)) (define (fast-expt base exp) (cond ((= exp 0) 1) (( even? exp) (square (fast-expt base (/ exp 2)))) (else (* base (fast-expt base (- exp 1))))))
Exercise 1.26
(remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m))
これは、expmodを二回計算してしまうため、計算料の節約が帳消しになる。
Exercise 1.27
#lang Racket (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (square a) (* a a)) (define (fermat-test n a) (= (expmod a n n) a)) (define (carmichael-prime? n times) (cond ((= times 0) true) ((fermat-test n times) (carmichael-prime? n (- times 1))) (else false))) (define (carmichael-test n) (carmichael-prime? n (- n 1))) (carmichael-test 6601)
Exercise 1.28
;(= expmod( a n-1 n) 1) ; n is prime ;任意のaについていかが成り立つ ; 0 < a < n (a∈N) ; a^(n-1) ≡ 1 (mod n) ;かつ、以下を満たすaが存在しない ; 1 < a < n-1 ; a^2 ≡ 1 (mod n) #lang Racket (define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (if (= (remainder (square base) m) 1) 0 (remainder (square (expmod base (/ exp 2) m)) m))) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (square a) (* a a)) (define (miller-rabin-test n) (define (try-it a) (= (expmod a (- n 1) n) 1)) (try-it (+ 1 (random (- n 1))))) (define (fast-prime2? n times) (cond ((= times 0) true) ((miller-rabin-test n) (fast-prime2? n (- times 1))) (else false))) (fast-prime2? 2821 10) (fast-prime2? 6601 100) (fast-prime2? 10007 100)
SICP 演習問題 1.1
実はちょっと前からやっていたんだけど、長続きしないと恥ずかしいからアップするのを控えていた。
それなりに続いているし、このまま止まらないようにアップして自分を追い詰めることにした。
とりあえず1章から順番に。。。
Exercise 1.1
10 # -> 10 (+ 5 3 4) # -> 12 (- 9 1) #-> 8 (/ 6 2) # -> 3 (+ (*2 4) (- 4 6)) # -> (+ 8 -2) # -> 6 (define a 3) (define b (+ a 1) (+ a b (*a b)) # -> (+ 3 4 12) # -> 19 (= a b) # -> false (if (and (> b a) (< b (*a b))) b a) # -> (if (and true true)) b a) # -> b (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) # -> (cond (fase 6) (true 16) (else 25)) # -> 16 (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) # -> (* b 4) # -> 16
Exercise 1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
Exercise 1.3
#lang Racket (define (sum-sqrt a b) (+ (* a a) (* b b))) (define (major-sum-sqrt x y z) (cond ((and (< x y) (< x z)) (sum-sqrt y z)) ((and (< y x) (< y z)) (sum-sqrt x z)) (else (sum-sqrt x y)))) (major-sum-sqrt 1 2 3) (major-sum-sqrt 4 2 3) (major-sum-sqrt 1 4 3)
Exercise 1.4
b>0のとき
(if (> b 0) + -)
の評価結果は + となり、 (+ a b) が評価される。
他方b<0のとき
(if (> b 0) + -)
の評価結果は - となり、 (- a b) が評価される。
上記の通り、 評価結果として手続き ( + or - ) が返せる ＝「演算子が複合式であるような組み合わせが作れる」 ということ？
Exercise 1.5
適用順序評価の場合、以下のように評価され、0を返す。
(test 0 (p)) ; (testを評価 (if (= x 0) 0 (p)) ; (= x 0) を評価 0
正規順序評価の場合、無限ループする
(test 0 (p)) ; (p) を評価 (test 0 (p)) ; (p) を評価 ...
Exercise 1.6
new-if ではtrue 節、 else 節両方が評価されてしまうため、処理が終了しない。
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) (define (sqrt-iter guess x) (new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (sqrt-iter 1.0 2) ;sqrt-iterを展開 (new-if (good-enough? 1.0 2) 1.0 (sqrt-iter (improve 1.0 2) 2)) ;new-if を展開 (cond (good-enough? 1.0 2) 1.0 (sqrt-iter (improve 1.0 2) 2)) ;good-enough?を評価 ;sqrt-iterを展開 ;以下略
以下の例を実行すると、
ture, else 双方が評価されていることが分かる。
（＝返り値が正しくても副作用がある場合バグる）
#lang Racket (define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause))) (define (then-stub) (display "I'm then-clause")(newline)(= 0 0)) (define (else-stub) (display "I'm else-clause")(newline)(= 0 1)) ;返り値は#t（true）だが、displayはthen, else 両方出る (new-if (> 1 0) (then-stub) (else-stub)) ;返り値は#f（false）だが、displayはthen, else 両方出る (new-if (> 0 1) (then-stub) (else-stub))
Exercise 1.7
小さい数の場合、推測値が誤差許容範囲(0.0001)よりも小さくなると、
誤差判定を必ずパスしてしまう。
（例： 10^-4のオーダーで引き算したら必ず答えは 0.0001より小さくなる）
大きい数の場合、小数桁がけた落ちしてしまうので、 小さい差分の比較ができなくなる。（評価が終わらない）
Exercise 1.8
#lang Racket (define (cube-root guess x) (if (good-enough? guess x) guess (cube-root (improve guess x) x))) (define (good-enough? guess x) (< (abs (- (cube guess) x)) 0.001)) (define (improve guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3)) (define (square x) (* x x)) (define (cube x) (* x x x)) (cube-root 1.0 8)
Katagaitai CTF勉強会 関東med (Crypt 理論編？）
先週末に行ってきた勉強会。とてもタメになった。
が、なかなか本腰いれて取り組めないので、少しずつアップすることにした。
今回は午前中のcryptについて、理論面を整理。 実装は、きっとこのあとやる・・・はず。
問題
CSAW CTF 2014 – Crypto300 – feal.py
FEAL（the Fast Data Encipherment Algorithm）
https://ja.wikipedia.org/wiki/FEAL
の復号を扱う問題。
第１段階
特定条件を満たす値が要求される
- a sha1 sum ending in 16bits set to 1
- it must be of length 21 bytes
- starting with [毎度変化する乱数]
時間制限は特に無いもよう。 何度か試したが乱数は必ず16byteなので、21-16=5byteのブルートフォースを考える。
以下のループを作る。（速度考えC言語）
- 末尾5byteを1bitずつインクリメントする
- 各ループでSHA1hashを計算
- 計算したSHA1hashの末尾16bitが1になっていたらbreak
また、ネットワーク経由で回答するので、以下のスクリプトを用意
- サーバにソケットをはる
- 乱数部を取得する
- ブルートフォースの結果を送信する
第2段階
暗号文の復号を求められる。
任意の値を入力すると、その暗号化結果を返してくる。 （この時、同じ鍵を使って暗号化している）
↑重要。しばらくこれに気づかなかったので解法のアプローチが理解できなかった
問題名をググるとFEAL暗号に行き着く。
金言：暗号問題は、とにかくググッて暗号文アルゴリズムと解法を見つける
FEAL暗号の仕組みを書こうとすると勉強会スライドのコピペになってしまいそうなので、自分が理解する過程で書いたメモをここにおいておく。
注意点(自分へのToDoも兼ねて）
- ページ数は勉強会資料のスライド番号
- 勉強会資料のURLは公開され次第反映予定（覚えていれば
- 勉強会当時と内容が修正されている場合、ページ数に齟齬が出るかも（覚えていれば修正する
- 以降勉強会資料中では XOR演算を + と表記しているので、ここでもそれに習います。 （+ は加算ではないので注意）
FEALの概要 (pp25-27)
- 共通鍵暗号方式
- ブロック暗号
暗号解析のアプローチ(pp28-29)
僅かに異なる2つの入力を与えてみて、暗号化結果の相関を見る。 （共通部分が同じ暗号化結果になる場合、それはヒントになり得る）
差分解析
FEALにおける差分解析の有効性(pp30-31)
４ラウンドあるので、１ラウンドずつ見ていく。(p30)
- 8byte毎に分割した4つの入力を処理しているので、これらの組み合わせ（同じ／違う）を考える
- ラウンド内にある関数G0,G1は入力が(0,0)の場合に特定の値(0 or 4)を吐き出す。
- Gn(a,b) = (n or a or b) mod 256 <<< 2
- G0(0,0) = (0 or 0 or 0) mod 256 <<< 2 = 0 <<< 0 = 0
- G1(0,0) = (1 or 0 or 0) mod 256 <<< 2 = 1 <<< 2 = 4
x0～x4までの値の組み合わせを工夫して、G0とG1への入力を0にする方法を考える
（考えるというか、誰かが考えた内容を見つけて理解する）
解析手順(p32)
- 途中にXOR演算が存在する
- XOR演算の箇所に同じ値が入るようにすれば 0 が作れる
具体的な値を入れて差分をとってみる(pp33- )
(pp33-34)
図中でも書いてくれているが、自分で各値を計算して整理してみたのが以下。
（計算して資料と合わない点は質問ちう）
(x0,x1,x2,x3) → (y0,y1,y2,y3)
とした時、y0～y3の定義は
y0 = G0(x0, y1) = G0(x0, G1(x0+x1, x2+x3)) y1 = G1(x0+x1, x2+x3) y2 = G0(y1, x2+x3) = G0(G1(x0+y1,x2+x3), x2+x3) y3 = G1(y2, x3) = G1(G0(G1(x0+y1,x2+x3), x2+x3),x3)
ここで、x0=x1, x2=x3 とすると、x0+x1=0, x2+x3=0のため、
y0 = G0(x0, G1(x0+x1, x2+x3)) = G0(x0, G1(0,0)) = G0(x0, 4) y1 = G1(0,0) = 4 y2 = G0(y1,0) = G0(4,0) = 16 y3 = G1(16,x3)
スライドだとy2=32だが?
→(2/6追記)
bataさんより、本問は3bitシフトなので32で正しいとご指摘いただいた。
@linus404 「スライドだとy2=32だが?」→ この問題は，本来のFEALではなく，少し改変されたFEALなんです．なのでG()内のシフト量がオリジナルとは違う事に注意して下さい．(引用した資料の図が間違ってて，<<<2じゃなくて<<<3です．y2=32は合ってます)
— bata (@bata_24) 2016, 1月 29
確かに、ソースを見たらその通りだった。
何故見ようとしなかったのだろう・・・
def rot3(x):
return ((x<<3)|(x>>5))&0xff
def gBox(a,b,mode):
return rot3((a+b+mode)%256)
(追記おわり)
もう一つの入力
(x'0,x'1,x'2,x'3) → (y'0,y'1,y'2,y'3)
については、x,yをx',y'にするだけなので省略
差分は
⊿y0 = G0(x0,4)+G0(x'0,4) ⊿y1 = 4 + 4 = 0 （※一見おかしいけど、 + は xor なので正しい） ⊿y2 = 32 + 32 = 0 ⊿y3 = G1(32,x3) + G1(32,x'3)
出力差分がx1, x3のみに依存する＝偏る
(pp35-36)
- X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
- X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)
y0 = G0(0,4) = 0x10 y'0 = G0(0x80,4) = 0x84 <<< 3 = 0x12 ⊿y0 = 0x02 y3 = y'3 = G1(32, 0) ⊿y3 = 0
- 特定の⊿xになる入力で⊿yを推測可能 *
(pp37-41)
以上は1ラウンドだけの話
これを4ラウンド続けたらどうなるか。
Y, Y'を計算してから⊿Yを導いてみる
- X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
- X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)
1段目入力
左：P1l=X+K4 ⊿P1l=⊿X 右：P1r=K4+K5 ⊿P1r=0
1段目出力
左：C1l=X+K4+f(K0+K4+K5) ⊿C1l = ⊿X = 0x80800000 右；C1r=K4+K5 ⊿C1r = 0
2段目入力
左：P2l=P1r ⊿P2l = 0 右：P2r=C1l ⊿P2r = 0x80800000
2段目出力
左：C2l=P2l+f(K1+C1l) ⊿C2l = f(0x80800000) = 0x02000000 右：C2r=P2r ⊿C2r = 0x80800000
3段目入力
左：P3l=C2r ⊿P3l=0x80800000 右：P3r=C2l ⊿P3r=0x02000000
3段目出力
左：C3l=P3l+f(K2+P3r) ⊿C3l = 0x80800000 + ⊿f(K2+P3r) = ??? 右：C3r=P3r ⊿C3r = 0x02000000
4段目入力
左：P4l=C3r ⊿P4l=0x02000000 右：P4r=C3l ⊿P4r=不明
4段目出力
左：C4l=P4l+f(K3+P4r) ⊿不明 右：C4r=P4r ⊿P4r=不明
(pp42-46)
最終的な出力から考えてみると、
左出力： Cl = C4l 右出力： Cr = C4r+C4l = P4r + Cl
よって、
P4r=Cr+Cl となる。
つまり、狙った差分の入力X,X'から、C, C'を得られれば、逆算可能。
（そして、C,C'は暗号化結果なので取得可能な値）
(pp47-53)
4つの値（左右入出力差分）がわかったので、Key3が逆算可能
あとは芋づる式に K2, K1 K0, K4, K5 を求める。
K3： ⊿C1= ⊿P4l+f(C4r+K3)+f(C'4r+K3) =0x02000000+f(Cl+Cr+K3)+f(C'l+C'r+K3) C4r=Cr+Cl C4l=Cl K2: ⊿C3l=⊿P3l+f(C3r+K2)+f(C'3r+K2) C3r=C4l+f(C4r+K3) C3l=C4r K1: ⊿C2l=⊿P2l+f(C2r+K1)+f(C'2r+K1) C2r=C3l+f(C3r+K2) =C1+C2+f(C3r+K2) C2l=C3r K0: ⊿C1l=⊿P1l+f(C1r+K0)+f(C'1r+K0) C1r=C2l+f(C2r+K0) C1l=C2r K4: K4=P1l+Pl=C1l+f(C1r+K0)+Pl K5: K5=C1r+Pr+K4+Pl
後はこれを実装すれば、きっと・・・（まだやっていない）
SECCON 2015 online
前日が同期の結婚式で多忙だったので抜け殻状態でトライ。
二日酔いの寝不足で途中寝落ちたりしたので、実質3時間程度しか戦っていない。
結果、1問 300点しか取れませんでした。
やっぱ片手間じゃ太刀打ちできませんよねー。
# network 100 Entry form
## 大会中の動き
Webアプリ系問題。
Emailアドレスと名前を入力する登録フォーム。
ディレクトリトラバーサルで問題アプリのソースコードを発見。
sendmailを使って登録完了メールを送るソースだったので、捨てアドで登録してメールヘッダインジェクションを試みるも、そもそもメールが届かない。
じゃあコマンドインジェクションかー。と試してみるが、動かず。
一旦他の問題に移り、そのまま放置
## 事後の反省
WirteUpを見る限り、アプローチは正しかった模様。
おそらくは、構文の組み立てがちゃんとできていなかったのだと思う。
（シングルクォーテーションの扱いとか、気をつけたつもりだけど雑だったんだと思う）
# network 200 fragment2
## 大会中の動き
pcap解析の問題。
パケット末尾に the flag is in header とあったので、ヘッダを順番にみてみる。
しかし、
- pcapヘッダ
- etherヘッダ
- ipヘッダ
- tcpヘッダ
いずれも不審点なし。
tcpヘッダの末尾から the flag is...の間に 70バイトほどのデータが有ったので、ここに着目。
port80だし、HTTP2だろーと思って、Wiresharkでデコードしてみる。
が、デコード出来ず。
万策尽きて、別の問題へ
## 事後の反省
なんと、予想通り HTTP2だったらしい。
Wiresharkをバージョンアップして再度試したところ、うまくデコードできた。。。グダグダ
そしてHeader Block Fragmentがある。これがFragment2か。
HPACKされているはずなので、こいつをHPACKデコードすればフラグが出そう。
go言語のHAPCKデコーダを見つけたので、こいつを使えばいけそうな予感。
（go書いたことないけど）
# Unknown 300 Exec dmesg
## 大会中の動き
Linuxのisoイメージが配布される。
中身は tiny core linux.
新入社員のとき仕事で使ってた懐かしいOS。
問題文のとおりdmesgを実行しようとしたが、busybox に ねーよ と怒られる。
dmesgの本体は /var/ だか /dev/ にあるはずだけど思いだせねー
と思い、 dmesgアリ版のbusyboxを調達することにする。
uname -a したところ、幸い、i686だったので特に障害も無し。
dmesgできるバイナリを配置して、実行すると、dmesg中にフラグを見つけた。
## 事後の反省
別のWriteupで
```
# grep -iR SECCON /
でフラグ発見。grep最強！
```
という記述を見て、エレガントだと思った。
また、dmesgを目grepでフラグ見つけた自分、アカンなと思った。
# 全体
今回はスケジュール的に専念出来ない状況だったので、まあ仕方ないといえば仕方ない。
逆に、腰を据えて挑まないとろくにパフォーマンスが出ないということをよく証明する意味で、良い悪い見本（？）となる経験だった。
あとどうでもいいけど、出題者QRコード好き過ぎ。
やってないけど。
sqlite3のデータ型について
いくつか驚いたことがあったので忘れないようにメモ。
結論
- create文で存在しないデータ型を指定してもエラーにならない
- integer型のカラムに数字に出来そうにない文字列(e.g. sqlite)をぶち込んでもエラーにならない（text型で格納される）
- データ型は「その型しか入らない」ではなく、「その型に変換できないかがんばる」ためのものと捉えた方がいい
実験
まずは、 integer型のidと、text型のnameというフィールドを持つテーブルを試す。
sqlite> create table texttype (id integer, name text);
sqlite> insert into texttype values (1, 'alice');
sqlite> insert into texttype values ('2', 'bob');
sqlite> insert into texttype values ('c', 'cindy');
sqlite> insert into texttype values (2.5, 1234);
sqlite> select id, typeof(id), name, typeof(name) from texttype;
1|integer|alice|text
2|integer|bob|text
c|text|cindy|text
2.5|real|1234|text
integer型の場合
整数→integer
数字リテラル→integer (型変換)
非数字リテラル→text
小数→real
と、当たり前のように整数型以外が入った。
どうも、「型変換はがんばるが、無理ならそのまま入れる」みたいな作りらしい。
続いて、あり得ないデータ型（foo, bar）でつくってみる。
sqlite> create table othertype (id foo, name bar);
sqlite> insert into othertype values (1, 'alice');
sqlite> insert into othertype values ('2', 'bob');
sqlite> insert into othertype values ('c', 'cindy');
sqlite> insert into othertype values (2.5, 1234);
sqlite> select id, typeof(id), name, typeof(name) from othertype;
1|integer|alice|text
2|integer|bob|text
c|text|cindy|text
2.5|real|1234|integer
型変換なしで何でも入る模様。
これだと
create table jiro (yasai mashimashi, ninniku Chomolungma, choi karame )
とか出来ちゃうってことか。。。
んー。DBのデータ型って意識したことなかったけど、こんなものなのか・・・
他のDBMSも調べてみよう。
