RSS Feed

제곱근의 반올림

Problem 255

출제 일시 : 2020-11-15 00:04:13

자연수 n반올림된 제곱근n의 제곱근에 가장 가까운 정수로 정의합니다.

헤론(Heron)의 방법을 정수에 적용한 다음 과정을 통하여 n의 반올림된 제곱근을 구할 수 있습니다:

d는 자연수 n의 자릿수입니다.
d가 홀수라면, $x_0 = 2 \times 10^{(d-1)/2}$라 합니다.
d가 짝수라면, $x_0 = 7 \times 10^{(d-2)/2}$라 합니다.
다음을 반복하다가:

$$x_{k+1} = \Biggl\lfloor{\dfrac{x_k + \lceil{n / x_k}\rceil}{2}}\Biggr\rfloor$$

$x_{k+1} = x_k$가 되면 종료합니다.

예를 들어, n = 4321의 반올림된 제곱근을 구해 보겠습니다.
n은 4자릿수이므로, $x_0 = 7 \times 10^{(4-2)/2} = 70$입니다.
$$x_1 = \Biggl\lfloor{\dfrac{70 + \lceil{4321 / 70}\rceil}{2}}\Biggr\rfloor = 66\\ x_2 = \Biggl\lfloor{\dfrac{66 + \lceil{4321 / 66}\rceil}{2}}\Biggr\rfloor = 66$$ $x_2 = x_1$이므로, 종료합니다.
단 두 번의 반복만에 4321의 반올림된 제곱근이 66임을 구했습니다(실제 제곱근은 65.7343137…입니다).

이 방법을 사용하면 반복 횟수가 놀랍도록 적습니다.
예를 들어, 5자리 자연수(10,000 ≤ n ≤ 99,999)의 반올림된 제곱근을 구하는데 평균적으로 겨우 3.2102888889 회의 반복만 필요합니다(평균값은 소수점이하 10자리까지 반올림하였습니다).

위에 기술된 과정을 사용하여 14자리 자연수 1013n < 1014 의 반올림된 제곱근을 구하는데 필요한 평균 반복 횟수는 얼마입니까?
답은 소수점이하 10자리까지 반올림하여 제출하세요.

참고: 기호 $\lfloor x \rfloor$와 $\lceil x \rceil$는 각각 바닥(floor) 함수천장(ceiling) 함수입니다.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.