결국 1.19 문제는 우지챠 해답을 보기로 한 레후....
수포자인 우지챠에게 준 수학문제는 넘나 잔인한 레후...
이런 문제가 하나가 아닐거라는게 문제긴 하지만...
애당초 입문서라 해도 mit 애들 대상으로 한 입문서인 레후...
뇌의 질 자체로만 치면 샤대 애들도 몇 수 접는 레후...
애당초 샤대는 뇌의 질이 좋지 않아도 마개조로 갈 수 있는데
mit는 그게 샤대보다 힘들테니 렣....

(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` value calculate
                  <??> ;q` value calculate
                  (/count 2)))
       (else (fib-iter (+ (* b q) (* a q) (* a p))
                       (+ (* b p) (* a q))
                       p
                       q
                       (- count 1)))))   

(define (square x)
 (* x x))
(define (eveb? n)
 (= (remainder n 2) 0))
(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
                  (+ (square p) (square q))
                  (+ (square q) (* 2 p q))
                  (/ count 2)
                  ))
       (else (fib-iter (+ (* b q) (* a q) (* a p))
                       (+ (* b p) (* a q))
                       p q
                       (- count 1))
             )))  

레무룩....

1.25 최대공약수 p62

최대공약수(GCD)에 대해서는 다들 알고 있을 것이다. 두 수를 나머지 없이 잘라 나눌 수 있는 가장 큰 정수를 말한다.
에컨데 16과 28의 GCD는a,ba 4다. 이 최대공약수는 헬조센 기초기육을 이수한 사람은 앤간하면 알고 있는 인수분해로 구하지만
그보다 더 좋은 알고리즘을 통해 구할 수 있다.

이 알고리즘은 a를 b로 나눈 나머지가 r일때
a와 b의 최대 공약수가 a와 r의 최대 공약수와 같다는 사실에 바탕을 둔다.
GCD(a, b) = GCD(b r)
이걸 전개하면 대충 이렇다.
GCD(206, 40)
= GCD(40 6)
= GCD(6 4)
= GCD(4 2)
= GCD(2 0)
= 2

0보다 큰 정수 들을 받아서 이런 과정을 되풀이 하면 언제나 둘쨰 수가 0이 된다.
이때 첫 수가 GCD다.
이 알고리즘이 유클리드 알고리즘이다.


아 쓰바... 이레서 수학수학 하는구나.
무언가 덜 혼모노한걸 훨씬 혼모노한 레벨로
끌어내려서 혼모노하게 처리할 수 있으니까.

(define (gcd a b)
 (if (= b 0) a
 (gcd b (remainder a b))))

신기하게도 거꾸루 해도 된다 ㅋㅋ

이 프로시저는 반복하는 프로세스로 펼쳐지면 밟아야 할 단계 수가 로그 비례로 자라난다.
유클리드 알고리즘의 계산 단계가 로그 자람 차수를 가진다는 사실에는 피보나치 수열과의 재미있는 관계가 있다.

라메의 정리 : 유클리알고리즘으로 GCD를 구하는데 k 단계를 거치는 겨우 두 수 가운데 작은 수는 k번째 피보나치 수보다 크거야 같아야 한다.

이 정리를 바탕으로 유클리드 알고리즘의 자람 차수를 얻을 수 있다.
gcd 프로시저의 두 인자 가운데 작은 값을 n이라 하자.
계산이 k 단계를 거쳐 끝난다고 하면
의 관계가 맞아떨어진다.
그러므로 단계수는 {}를 밑 수로 잡은 n의 로그로 자라난다.

수학은 가장 혼모노함을 추상화한 학문이다.
오로지 수 많의 세계를 인간이 추상화 하였다.
그리고 그 혼모노한 세계 하에서 여러 짓거리를 하는데
그렇기에 혼모노함이 필요한 알고리즘 분야에서 쓰일 수밖에 없다.
뭔소리야 쓰바.. 우지챠가 했는데도 모르곘는 레후 ~~ ㅎㅎ


연습문제 1.20 (p64)
프로시저가 만드는 프로세스는 마땅히 실행기의 계산 규칙에서 영향을 받는다. 앞서 나온 GCD 프로시저를 보기 삼아서 이 문제를 살펴보자. 먼저 이번에는 1.1.5절에서 선보인 정의대로 계산하는 방법을 따른다고 하자.(if를 정의대로 계싼하는 방법은 연습문제 1.5에 있다.) 맞바꿈 계산법으로 (gcd 206 40)을 정의한대로 구하는 프로세스를 보이고 remainder 연산을 어디에다 쓰는지 표시하자. 프로세스가 끝날 때까지 remainder 연산을 어디에다 쓰는지 표시하자. 프로세스가 끝날 때까지 remainder 연산을 얼마나 쓰는가? 인자먼저계산을 쓰는 경우라면 또 어떠한가?

참 창의적으로 뇌를 고문하는 레후...
다만 뇌를 고문하지 않으면 효과가 없는 레후...
애당초 고문하라고 산 책인 레후....
우지챠는 마조히스트 우지인 레후....

잠깐 뒤로 가보면 대충 다음과 같은 레후...

1.1.5. 맞바꿈 계산법(substritution model)로 프로시저 실행(19p)
(f 5)
위의 (f) 프로시저를 통한 (f 5) 계산은 다음과 같이 풀어쓸 수 있다.
(sum-of-square (+ a 1) (* a 2)))
여기서 a 인자를 5 로 바꾼다.
(sum-of-square (+ 5 1) (* 5 2)))
이를 풀어쓰면 다음과 같다.
(+ (square 6) (square 10))
이 역시 아래와 같이 계속 풀어쓴다.
(+ (* 6 6) (* 10 10))
(+ 36 100)
136
이로 인하여 136의 답이 나왔다.
단 이것은 도움을 주기 위한 설명일 뿐
실행기가 진짜로 이리 돌아간다는 것은 아니다.
실제로 돌아가는 방법은 4장에서 설명하고 있다 한다.

인자 먼저 계산법과 정의대로 계산법(21p)
위의 식은 다음과 같이 풀어 쓸 수도 있다.
(sum-of-square (+ 5 1) (* 5 2))) =
(+ (square 5 1) (square 5 2))) =
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2))) =
그리고 나서 아래와 같이 줄어든다.
( + (* 6 6) (* 10 10)) =
( +    36      100) =
136

즉 끝까지 펼치고 난 다음에 줄여나가는 방법이 있으며
위에서 본 인자를 대입하고 보는 방법이 있다.
LISP 는 인자를 먼저 대입하는 방법을 쓰며
가끔씩 두 방법에 따라 다른 값이 나오기도 하기에
두 규칙은 상호 보완적이다.

연습문제 1.5(28p)
다음 두 개의 함수를 정의한다.
(define (p)(p))
(define (test x y)
 (if (= x 0)
     0
     y))
그 뒤 다음 값을 실행한다.
(test 0 (p))
정의대로 계산법과 인자 먼저 계산법 에서의 결과를 살펴본다.

우선 인자먼저 계산법에서는 씨발놈의 무한루프가 나온다.
(test 0 (p)) 에 일단 p 부터 대입하다 보니까 무한루프다.
하지만 정의대로 계산법에서는
존나 풀어 내놓고 아누자이마냥
근본부터 가다 보니
define에 p 값을 쳐 넣은 것부터
에로사항이 꽃펴 오류 값을 낼것이다.

아마도 ....


즉...

인자먼저
(gcd 206 40)
이건 다음과 같이 풀어 쓸 수 있다.
(if (= b 0) a  (gcd b (remainder a b)))
바꾼다
(if (= 400 0) 206  (gcd 40 (remainder 206 40)))
(if (= 6 0) 40  (gcd 6 (remainder 40 6)))
(if (= 4 0) 6  (gcd 4 (remainder 6 4)))
(if (= 2 0) 4  (gcd 2 (remainder 4 2)))
(if (= 0 0) 2  (gcd 0 (remainder 2 0)))

4번인 레후웅~
아니 이게 정의대로 인가?
아니 인자먼저 봤다.


정의대로
결국 퍼왔다...

(gcd 206 40)
if (= 40 0)
(gcd 40 (remainder 206 40))
if(= (remainder 206 40) 0) – 1
(gcd (remainder 206 40)  (remainder 40 (remainder 206 40)))
if (= (remainder 40 (remainder 206 40)) 0) – 2
(gcd (remainder 40 (remainder 206 40))  (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) – 4
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))  (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) – 7
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))) – 1
(remainder 6 (remainder 40 (remainder 206 40))) – 1
(remainder 6 (remainder 40 6)) – 1
(remainder 6 4) – 1

대충 뭘 하라고 말한건지는 알거갔다.

1.2.6 소수 찾기 (64p)

소수는 자기자신과 1 외에는 나누어 떨어지지 않는 외로운 수이니 외로울 때는 소수를 새면 좋다.
여기서는 그 외롭고 고고하며 아름다운 수인 소수를 찾는 방법에 대해 알아본다 한다.
옛날부터 수학 좀 한다 싶은 닝겐들은 무엇이 소수인지 알기 위해 존나 매달렸다.
여튼간에 가장 보편적인 방법은 약수를 찾아내는 것이다.


1. 약수찾기.
(define (square a)
 (* a a))


(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 (+ test-divisor 1)))))
(define (divides? a b)
 (= (remainder b a) 0)
위 알고리즘은 뭐 간단하다. 1보다 큰 가장 작은 약수를 구하는 프로그램이다.
2 부터 시작해서 1씩 올라간다. 하지만 어차피  소수가 아니라면 sqrt(n) 보다 작거나 같은 약수가 꼭 있기 떄문에
1부터 sqrt(n) 까지의 값만 탐색한다.
따라서 n이 소수인지 알아보는데 거치는 계산 단계는
Θsqrt(n) 이 된다.


2.페르마 검사.
Θlog(n) 차수로 소수를 찾는 방법은 페르마의 작은 정리라고 하는 이론에서 이끌어 낸 알고리즘이다.
로그가 먼지 기억이 안나서 구글 검색했다.... 무식한레후...
페르마의 작은 정리 : n이 소수고 a가 n 보다는 작고 0 보다는 큰 정수라면 a^n은 a modulo n 으로 맞아 떨어진다.
(modulo가 % 이더라)
한 마디로 임의의 소수 pp와 서로소인 한 수의 p-1p−1승을 pp로 나눈 나머지는 무조건 11이라는 정리.

씨-----------발

뭐 그렇다고 치자.



어렵지만 나아가는 레후.
일단 국내 블로그라도 보면서 페르마 정리와 소수에 대해 보는 레후.


소수를 구하는 데는 몇 가지 종류의 알고리즘이 있다.
1. 자연수 a가 소수인지 알아보기 위해 2부터 a-1까지 나눠본다(sqrt a)도 되긴 하다만.
  • 이 경우 직관적이라 설명하기 쉽고, 구현하기도 쉽다. 하지만 딱 봐도 효율성과는 거리가 멀어버린다
2. 에라토스테네스의 체를 이용한 방법이다. 

- 너무 길어 생략 -

나무위키에서 퍼온 레후.
사실 첫 방법이란 별로 다를 것도 없음.

3.  페르마의 마지막 정리를 이용한 방법

소수 p와 p로 나눠지지 않는 정수 a에 대해서
즉 소수 p와 정수 a가 서로소라면
ap−1 을 p로 나누었을 때 나머지가 1이 된다

이걸 소스코드로 작성해 보면.

def sosu(p, a):
    if ((a**(p-1))%p == 1):
        return "소수"
    else:
        return "합성수"
print(sosu(12, 5))
print(sosu(3,2))
print(sosu(341,2))



합성수
소수
소수

뭐 그런대로 된다. 단 
sosu(341,3) 같은 경우에는 제대로 합성수 리턴 때린다.


자 그러면 책에 있는 lisp 코드를 보자.

우선 어떤 수를 거듭제곱하여 구한 값을 다시 다른 수로 modulo 하는 프로시저가 필요하다.

(define (square a)
(* a a))

(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 (expmod base exp m) ; base 밑수, exp 거듭제곱하는 수,  
  (cond ((= exp 0) 1) ; 거듭제곱 하는 수가 0이면 1을 반환
        ((even? exp) ; exp가 짝수면
         (remainder  ; remainder 함수가 % 연산이다.(square (expmod base (/ exp 2) m ;거듭 제곱을 절반으로 주고 square로 재귀)) 
                    m) ; 그 값을 m으로 나눈 나머지
         (else
          remainder (* base (expmod base (- exp 1) m))
          m))))

LISP는 위에서 아래가 아니라 괄호 안쪽에서부터 연산을 시작한다.
그것이 특유의 가독성 좆같음을 유발한다.
거기에 더해서 괄호는 또 괄호는 오질나게 많다.


(define (square a)
(* a a))

(define (expmod base exp m) ; base 밑수, exp 거듭제곱하는 수,  
  (cond ((= exp 0) 1) ; 거듭제곱 하는 수가 0이면 1을 반환
        ((even? exp) ; exp가 짝수면
         (remainder  (square (expmod base (/ exp 2) m ))  ; remainder 함수가 % 연산이다.  ;거듭 제곱을 절반으로 주고 square로 재귀
                    m) ; 그 값을 m으로 나눈 나머지
         (else ; exp가 홀수면
          remainder (* base (expmod base (- exp 1) m)) ; 거듭재곱하는 수를 하나 뺸 대신 밑수 하나 곱하기 결국 같은 이야기
          m)))) ; 그 값을 m으로 나눈 나머지

+어떤 수를 거듭제곱하여 구한 값을 다시 다른 수로 % 하는 프로시저
  
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1))))) 

(define (fast-frime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))


(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1))))) 
; 난수 생성

(define (fast-frime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))
; 본체 정해진 만큼 페르마 검사

일단 쳐봤다. 

씨발!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
레에에에에.............
이건 아냐....


(define (square a)
(* a a))

(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 (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 (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 (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 (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))))


뭐 여튼간에 다시 하지마루 하는 데스웅




확률을 바탕으로 하는 알고리즘 (p67)

알고리즘이라 하면 보통 틀림없는 답을 낸다.
하지만 페르마 검사는 그렇지 않다. 정확하지 않고 어림잡은 답만 나온다.
하지만 페르마 검사를 쓸모 없게 만드는 카마이클 수의 경우 매우 드물다.
매우 큰 수를 마구잡이로 골라 그 수가 소수인지 알아볼 때
페르마 검사가 틀릴 확률은 원인불명의 오류에 의해 컴퓨터가 고장날 확률보다 낮다.
처음에는 틀렸기 때문에 알맞지 않은 알고리즘이라고 했다가
나중에는 쓸만하다고 여겨졌는데
바로 이런 판단 기준의 차이가 수학과 공학의 차이를 말해준다.

여튼간에 그 틀릴가능성을 줄이기 위한 이런저런 알고리즘이 있다.
또한 페르마 검사를 역으로 하여 
n이 소수가 아닐 때에는 a<n인 정수 가운제 조건을 만족하는 경우가 거의 없다는 사실을 알았다.
이런식으로 틀릴 확률이 줄어든다고 증명할 수 있는 여러 검사방법이 있는데
이로부터 확률 알고리즘에 대한 관심이 높아지게 되었다. 
특히 암호 분야에서 절찬리 이용 중이다.



연습문제 1.21 (p68)

(define (sd a)
  (sdsd a 2))
(define (sdsd a b)
  (cond
    ((= (remainder a b) 0) b)
  (else
   (sdsd a (+ 1 b)))
  ))

> (sd 199)
199
> (sd 1999)
1999
> (sd 19999)
7

레후!

연습문제 1.22(68p)

대게 LISP 시스템에는 runtime 라는 기본 프로시저가 있어서 이것으로 시스템이 실제 돌아간 시간을 정수 값으로 앋얼 수 있다. 아래 timed prime test는 정수 n을 받아서 찍은 다음 그 값이 소수인지 따져보는 프로시저로 n이 소수면 별포 세 개와 함께 검사하는데 걸린 시간을 찍는다.
(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elasped-time))
(timed-prime-test 7)

코드를 쳤는데 제대로 실행되는 scheme 이 재공되지 않아서 해맸다.
plt scheme 에서
expender 선택했다.
근데 이것도 뭔가...
current-process-milliseconds 으로 대신 하든 해야겠다.
...




연습문제 1.23(69p)
이 절 처음에 만든 smallest-divisor 프로시저는 쓸모없는 검사를 너무 많이 한다.
다시 말해서 어떤 수가 2로 나뉜다면 다시 그 수가 더 큰 짝수로 나뉘는지 알아볼 까닭이 없기 때문이다.
이 말을 test-divisor에서 
2,3,4,5,6 이 아니라
2,3,5,7,9 를 써야 한다.
이 생각에 2가 들어오면 3을
그 밖의 값이 들어오면 2를 더한 값을 내놓는 프로시저 next를 만들어라


누군 머리 좋아서 하는줄 암...