Hatena::Groupsicp

SICP in the blanket

2008-09-26

1章

23:32 | はてなブックマーク - 1章  - SICP in the blanket 1章  - SICP in the blanket のブックマークコメント

今ざっと読み返して気になったところだけ適当に拾っていく。

Ackermann関数

なんかUnion-findの計算量を解析する時とかに出てくるやつ。

(define (A x y)
  (cond [(= x 0) (* 2 y)]
        [(= y 0) 0]
        [(= y 1) 2]
        [else    (A (- x 1)
                    (A x (- y 1)))]))
  • (A 0 0) = 0 ; (A 0 n) = (+ 2 (A 0 (- n 1)))
    • (A 0 n) = 2*n
  • (A 1 0) = 0 ; (A 1 n) = (* 2 (A 1 (- n 1)))
    • (A 1 n) = 2^n
  • (A 2 0) = 0 ; (A 2 n) = (expt 2 (A 2 (- n 1)))

Fibonacci, 黄金比φ

  • φ = (1 + √5) / 2
  • ψ = (1 - √5) / 2
  • |ψ|^n < √5 / 2
  • fib(n) = (φ^n - ψ^n) / √5
  • = (φ^n / √5) - ε ( |ε| < 1/2 )
  • fib(n) は φ^n / √5 に最も近い整数
  • Lameの定理: GCD(a,b)でkステップかかる ⇒ min(a,b) ≧ fib(k)

素数判定とか

後で使うのでライブラリ化しとく

(use math.mt-random)
(define generator (make <mersenne-twister> :seed (sys-time)))
(define (random n) ; generates a random integer between 1 .. n
  (+ 1 (mt-random-integer generator n))

;; x^n mod m
(define (expmod x n m)
  (define (squaremod x) (remainder (* x x) m))
  (cond [(= n 0) 1]
        [(even? n)
         (squaremod (expmod x (ash n -1) m))]
        [else
         (remainder (* x (expmod x (- n 1) m))
                    m)]))

;; Fermat test
(define (fermat-test n a)
  (= (expmod a (- n 1) n)
     1))

;; k-q decomposition
;; n = 2^k * q
(define (k&q n)
  (define (decomp k q)
    (if (odd? q)
        (list k q)
        (decomp (+ k 1) (ash q -1))))
  (decomp 0 n))

;; Miller-Rabin test
(define (miller-rabin-test n a)
  (define (squares k xs)
    (if (= k 0)
        xs
        (squares (- k 1)
                 (cons (expmod (car xs) 2 n) xs))))
  (define (traverse xs)
    (cond [(null? xs) #t]
          [(= (car xs) (- n 1))  #t]
          [(= (car xs) 1) (traverse (cdr xs))]
          [else #f]))
  (let* ([kq (k&q (- n 1))]
         [k  (car  kq)]
         [q  (cadr kq)]
         [xs (squares k `(,(expmod a q n)))])
    (if (= (car xs) 1)
        (traverse (cdr xs))
        #f)))

;; Prime Checker
(define (prime? n)
  (define times 5)
  (define (rand-test)
    (let ([a (random (- n 1))])
      (if (= (gcd a n) 1)
          (miller-rabin-test n a)
          #f)))
  (define (try i)
    (cond [(= i 0) #t]
          [(rand-test) (try (- i 1))]
          [else #f]))
  (if (<= n 1) #f (try times)))


;; Carmichael Numbers
(define carmichaels
  '(561 1105 1729 2465 2821 6601))

MattinglyMattingly2012/01/09 19:57Good to see real expertise on display. Your cotnrbiution is most welcome.

exjurlpgksoexjurlpgkso2012/01/10 17:23LtAXNu <a href="http://qwymdffdvjgu.com/">qwymdffdvjgu</a>

igtnwvigtnwv2012/01/15 01:29lgrZ4A , [url=http://dgncekoxiect.com/]dgncekoxiect[/url], [link=http://kgqqnwfzdjcy.com/]kgqqnwfzdjcy[/link], http://jtteuxkxmnoa.com/

トラックバック - http://sicp.g.hatena.ne.jp/blanketsky/20080926