연습문제 1.7 풀고 계시거나 푸신 분들께 질문..

[comkid]

연습문제 1.7번이

앞서만든 good-enough?로는아주 작은 수의 제곱근을 구하지 못한다.또 컴퓨터에서수를 셈할 때는 유효숫자가 딱 정해져 있다
는 점 때문에아주 큰 수의 제곱근을 구하는 데도 알맞지 않다.아주 작은 수나큰 수의 제곱근을 구할 때 good-enough?가올
바로 답을 내지 못하는 보기를 들어 이런 문제를설명해보라. good-enough?를 만드는여러 방법 가운데 하나는, 참값에 더
가까운값 guess를 구하기 위해 어림잡은 값을 조금씩 고쳐 나가면서 헌값에 견주어 고친 값이 그다지 나아지지 않을 때까지 계산
을 이어가는 것이다.이 방법에 따라위에서 만든 제곱근 프로시저를 고쳐보자. 그렇게 고치고나니, 아주 작은 수나 큰 수의 제곱근
을 구할 때 전보다 잘 돌아가는가?

이런 내용인데 혹시 문제에 나오는 아주 작은 수와 아주 큰 수의 예를 찾으신 분 계신가요??

그냥 간단하게 생각해서 이전에 만들어진 sqrt-iter의 정확도가 떨어져서 이런 문제를 낸 것인지 아니면 실제 이진수로 부동
소수점을 표현할 때 발생할 수 있는 문제들과 연관해서 이런 문제를 낸 건지 모르겠어서요. (제가 너무 꼬아서 생각했나요..-_-
a)

일단 문제에서 설명하는 대로 풀어보면

"제곱근을 구하지 못하는 아주 작은 값"
"제곱근을 구하는데 책에 정의된 sqrt를 사용하는 것이 적합하지 않은 아주 큰 값"

이 두개의 예를 찾아야 하는데..

구하지 못하는 것과 적합하지 않은 것은 차이가 뭔지.. (아주 큰 값의 경우는 거기다 유효숫자에 대한 언급도 있고..) 그리고
오차에 관련된 것이라면 굳이 아주 큰 값이나 아주 작은 값 말고도 오차가 발생할 수 있는 숫자는 얼마든지 있을 것 같구요..

이런 면에서 볼 때 부동 소수점 표기와 관련되서 얽힌 문제일 것 같다고 생각하고 그 쪽을 막 팠는데.. scheme에서 실
수 표현을 위해 어떤 방식을 쓰는지도 잘 모르겠고.. 또 진짜 이거 관련됐다고 하면 1장 수준에서는 너무 난이도가 높을 것 같
고..

이어지는 문제를 보면 그냥 오차와 관련된 것일 수도 있을 것 같고..


아악.... 머리가 아플라 그래요.. on_

[Jiah]

연습문제 1.7은 커녕 1.6 근처에도 못 가서...
저는 거기까지 풀게되면 같이 고민해볼께요~ ^^;

08. 2. 26, comkid <ico...@gmail.com>님이 작성:

[황천의달]

큰수는 말그대로 큰 수 넣어보시면 됩니다. 전 다른 글보고 92400000000000000 를 넣어보니 과감히 스택 오버 플로
우.. -.-

반대로 작은 수는 0.0001인가.. 넣어보시면.. 0.032던가.. 그런 값이 나옵니다.

SICP진도를 요즘 못나가서..(주중에 공부하기 참 힘들죠.. 후새드..) LISP공부랑 그냥 겸하고 있습니다.

(Scheme 코드를 LISP으로도 한번 더 짜보기도 겸사겸사 재미있네요..)


--
새로움을 느끼기에 삶은 즐겁다..
모험가 아돌 크리스틴을 꿈꾸며..
Sia..

[황천의달]

큰수는 대략 92400000000000000 정도?? 다른 사이트 보고 찾았습니다...
작은 수는 0.000001 같은 수 넣어보면 됩니다. good-enough? 의 문제점을 찾는다고 보면 될 것 같네요...

--
새로움을 느끼기에 삶은 즐겁다..
모험가 아돌 크리스틴을 꿈꾸며..
Sia..

On 2월26일, 오후11시48분, comkid <icom...@gmail.com> wrote:

[comkid]

아! 그렇군요. 제가 너무 꼬아서 생각을 했었나보네요.. :)

근데 LISP은 업무에서 쓰셔서 하시는 건가요?? (궁금 ㅎㅎ)

[comkid]

google 검색창에

sqrt 숫자

입력하면 해당 숫자에 대한 제곱근이 나오는데

sqrt 0.0001

을 입력하면 이상한 값이 나오네요. 희안하네~

구글 계산기 사용법 : http://www.google.co.kr/help/calculator.html

[황천의달]

Lisp은 머 거의 취미생활입니다. :-)
게임도 끊고 TV나 그런거 안보다보니 Lisp에 어찌어찌 취미를 붙였네요 (웃음)

--
새로움을 느끼기에 삶은 즐겁다..
모험가 아돌 크리스틴을 꿈꾸며..
Sia..

[Jin]

1.1장에서 이 문제가 푸는데 시간이 가장 많이 걸리는 거 같네요.

제가 보기엔 큰 수와 작은 수의 경우가 다른 거 같습니다. 작은 수의 경우는 정확한 답을 못 내는 거 같고, 큰 수의 경우는 어
떤 에러를 발생시키는 거죠(큰 수도 정확한 답을 못 낼 수도 있겠죠).

작은 수의 경우 대략 0.001 정도부터 계속 차수 단위로 값을 내려가며 실행해보면 어느 순간인가 같은 값이 계속 나옵니다. 0
을 넣고 실행했을 때와 값이 같습니다. :( 이건 good-enough? 가 단지 제곱과의 차이 비교를 하기 때문인 거 같습니
다. 제곱의 값이 비교값(0.001) 보다 작은데 비교를 해봤자죠.

그리고 큰 수의 경우는 아마도 부동소수점 연산과 관련된 거 같습니다. 큰 수(10e28 이상 정도)를 넣어보면 무한 반복을 합
니다. improve 프로시저에 guess 값을 출력하는 부분을 넣고 살펴보면 어느 때부터인가 계속 같은 값이 출력되면서 무한
반복됩니다. 아마도 유효숫자 처리와 관련하여 부동소수점 연산과 관련된 거 같은데 C를 하시는 분들께서 설명해 주시면 좋겠네요.
아니면 C로 이 프로시저를 그대로 구현해서 살펴보는 법도 있겠죠.

On 2월26일, 오후11시48분, comkid <icom...@gmail.com> wrote:

[comkid]

Exercise 1.7. The good-enough? test used in computing square roots
will not be very effective for finding the square roots of very small
numbers. Also, in real computers, arithmetic operations are almost
always performed with limited precision. This makes our test
inadequate for very large numbers. Explain these statements, with
examples showing how the test fails for small and large numbers. An
alternative strategy for implementing good-enough? is to watch how
guess changes from one iteration to the next and to stop when the
change is a very small fraction of the guess. Design a square-root
procedure that uses this kind of end test. Does this work better for
small and large numbers?

문제 원문입니다.
아주 작은 숫자의 경우에는 책에 주어진 good-enough?로 제곱근을 찾는 것이 별로 효과적이지 않다.
=> 이부분은 황천의달님이나 Jin님 말씀처럼 너무 작은 숫자의 경우에는 제곱의 차이가 비교값 보다 작기 때문으로 보입니다.

그리고 아주 큰 숫자의 경우는 부동 소수점의 유효숫자와 관련하여 정확한 값을 내지 못하는 경우를 찾으면 될 것 같습니다.
테스트 해본 바로 scheme의 부동소숫점 표기는 IEEE 754 standard의 Double precision을 따르는 것으
로 보이는데 이 때문에 무한정 큰 숫자를 표시할 수는 없습니다.

부동소숫점 표기와 관련된 내용은 아래 두 링크를 참고..

http://en.wikipedia.org/wiki/Double_precision
http://www.winapi.co.kr/clec/cpp2/18-1-4.htm

첫번째 링크에서 보면 double precision으로 표기할 수 있는 가장 큰 숫자는 1.7976931348623157 x
10^308이 됩니다.

계산을 쉽게 하기 위해서 x^n을 구해주는 함수를 정의했습니다.

(define (pow x y)
(define (pow-iter p y)
(if (= y 0 ) p (pow-iter (* p x) (- y 1))))
(pow-iter 1 y))

이 함수로 Max 값을 구하고 여기에 특정값을 더하거나 곱해 보았습니다.

> (+ 0.1 (* 1.7976931348623157 (pow 10 308)))
1.7976931348623157e+308
> (+ 1 (* 1.7976931348623157 (pow 10 308)))
1.7976931348623157e+308
> (+ 10 (* 1.7976931348623157 (pow 10 308)))
1.7976931348623157e+308

> (* 0.1 (* 1.7976931348623157 (pow 10 308)))
1.7976931348623158e+307
> (* 1 (* 1.7976931348623157 (pow 10 308)))
1.7976931348623157e+308
> (* 1.0 (* 1.7976931348623157 (pow 10 308)))
1.7976931348623157e+308
> (* 1.1 (* 1.7976931348623157 (pow 10 308)))
+inf.0
> (* 2 (* 1.7976931348623157 (pow 10 308)))
+inf.0
> (* 10 (* 1.7976931348623157 (pow 10 308)))
+inf.0

덧셈의 경우는 무슨 이유인지 모르겠지만 계속 같은 값이 나오고, 곱셈의 경우는 조금만(1 이상) 배가 되도 inf가 되버립니
다. 만약 근사값이나 근사값의 제곱이 +inf.0이 되버리면 good-enough?에서 정상적으로 비교가 이루어지지 않을 것 같
습니다. (무한대 - 어떤 수 = 무한대 라서 그럴 것 같은..)

double max 값을 sqrt 함수 안에 넣어봤는데 tail recursion이라 stack fault는 안나는데 계속 무
한 루프를 도는 것 같네요.

[배기성]

comkid 님의 예제를 실행해봤는데 다음과 같은 에러가 나네요.

 

define: expected only one expression for the function body, but found one extra part

 

혹시나 싶어 책에 있는 예제들을 실행해봐도 마찬가지입니다. define 안에 다시 define 이 나오는 경우 이런 에러가 나네요.

DrScheme 에서 Language 설정을 잘못해놔서 그런걸까요? Advanced Student 로 해놓고 쓰고 있는데요.

 

2008/3/1 comkid <ico...@gmail.com>:

[황천의달]

저는 잘되는데요..
제 경우는 Lauguage를 Standard(R5RS)로 해서 진행중입니다.

--
새로움을 느끼기에 삶은 즐겁다..
모험가 아돌 크리스틴을 꿈꾸며..
Sia..

On 3월1일, 오후4시45분, "배기성" <gson...@gmail.com> wrote:
> comkid 님의 예제를 실행해봤는데 다음과 같은 에러가 나네요.
>
> define: expected only one expression for the function body, but found one
> extra part
>
> 혹시나 싶어 책에 있는 예제들을 실행해봐도 마찬가지입니다. define 안에 다시 define 이 나오는 경우 이런 에러가 나네요.
> DrScheme 에서 Language 설정을 잘못해놔서 그런걸까요? Advanced Student 로 해놓고 쓰고 있는데요.
>

> 2008/3/1 comkid <icom...@gmail.com>:

> --
>
> Thanks
> Ki Sung Bae

[배기성]

감사합니다. Standard 로 하니 저도 문제가 없네요 :)

2008/3/2 황천의달 <sia...@gmail.com>:

[Jin]

이 문제를 다시 생각해 봤습니다.

큰 수의 경우인데요. 부동소수점 연산의 정확도 문제로 무한정 큰 수를 표시할 수 없을 뿐 아니라
모든 자리수에 대해 값이 정확한 것도 아니네요.

32bit float 형인 경우 유효숫자를 23bit로 저장하니까 대략 7자리 정도만 유효한 숫자가 됩니다.
따라서 2진수 표기로 보면 높은 자리수로 23bit 까지만 저장하고 나머지는 모두 0이 되는 겁니다.

위에서 값을 더하면 계속 같은 값이 나온다고 했는데 이게 바로 그로 인해 발생하는 겁니다.

생각하기 쉽게 십진수로 되어 있다고 생각하고 유효 숫자가 7이라면

1. 987654321 이라는 값이 입력되면 이 값은 9.876543e8 로 저장됩니다. 21은 버려지게 되는 거죠
2. 여기에 1(=1.0e0)을 더하면 9.876543e8 + 1.0e0 이고 이는 987654300 + 1 =
987654301 이지만 저장하면서
9.876543e8 이 됩니다. 아주 큰 수에 작은 수를 더하면 값은 그냥 버려지게 됩니다.

위키피디아 Floating Point 항목에 이에 대한 설명이 나와 있습니다. 이를 round-of error 라고 하는군
요.
http://en.wikipedia.org/wiki/Floating_point#Addition_and_subtraction

위와 같은 문제가 큰 수의 제곱근을 뉴턴 메서드로 구할 때도 발생하는 것입니다.

뉴턴 메서드는 반복이 진행될수록 값의 정밀도가 높아지는데요(제곱의 비율로 수렴한다고 하는데
무슨 의미인지 정확한 뜻은 모르겠네요), 이 정밀도가 부동소수점 시스템의 유효 숫자 이상으로 넘어가게 되면
위에서처럼 값이 버려지게 됩니다. 그러면 반복이 진행돼도 계속 같은 값이 나오는 거죠.

'부동' 소수점이라는 것은 소수점이 옮겨 다닌다는 건데요, 그래서 정밀도(또는 오차)도 소수점처럼 옮겨 다니는 것 -
즉 상대적인 값이라는 건가 봅니다. 정밀도를 절대 값으로 유지하려면 "고정" 소수점(Fixed Point) 시스템을
써야 하는 거겠죠.

많은 분들이 1.7번 문제를 어려워 하시는 것 같고, 저도 이 문제를 푸느라 생각도 많이 걸렸고 다른 분들의 풀이도
많이 참조했는데 큰 수의 경우는 뾰족한 풀이가 없는 거 같아 의견을 내봤습니다.

PS. 스킴 외에 다른 언어(제 경우 자바)로 구현해도 같은 현상이 발생합니다.
자신이 잘 다루는 개발 환경으로 구현해서 다양한 방법으로 반복을 관찰해 보면(디버거라든지 출력을 통해)
실마리가 보일 것 같네요.

On 3월1일, 오전12시32분, comkid <icom...@gmail.com> wrote:
> Exercise 1.7. The good-enough? test used in computing square roots
> will not be very effective for finding the square roots of very small
> numbers. Also, in real computers, arithmetic operations are almost
> always performed with limited precision. This makes our test
> inadequate for very large numbers. Explain these statements, with
> examples showing how the test fails for small and large numbers. An
> alternative strategy for implementing good-enough? is to watch how
> guess changes from one iteration to the next and to stop when the
> change is a very small fraction of the guess. Design a square-root
> procedure that uses this kind of end test. Does this work better for
> small and large numbers?
>
> 문제 원문입니다.
> 아주 작은 숫자의 경우에는 책에 주어진 good-enough?로 제곱근을 찾는 것이 별로 효과적이지 않다.
> => 이부분은 황천의달님이나 Jin님 말씀처럼 너무 작은 숫자의 경우에는 제곱의 차이가 비교값 보다 작기 때문으로 보입니다.
>
> 그리고 아주 큰 숫자의 경우는 부동 소수점의 유효숫자와 관련하여 정확한 값을 내지 못하는 경우를 찾으면 될 것 같습니다.
> 테스트 해본 바로 scheme의 부동소숫점 표기는 IEEE 754 standard의 Double precision을 따르는 것으
> 로 보이는데 이 때문에 무한정 큰 숫자를 표시할 수는 없습니다.
>
> 부동소숫점 표기와 관련된 내용은 아래 두 링크를 참고..
>

> http://en.wikipedia.org/wiki/Double_precisionhttp://www.winapi.co.kr/clec/cpp2/18-1-4.htm