우수 답변
첫 번째 방법
= UNICHAR (8730)은 Microsoft Excel에서 제곱근 기호를 제공합니다.
Excel 2016에서 테스트 됨
p>
두 번째 방법
- 삽입 탭으로 이동 을 클릭하고 Symbols 그룹에서 Symbol 을 클릭합니다.
- 기호 아래에서 부분 집합에서 수학 연산자를 선택하고 제곱근 기호를 사용합니다.
Answer
대부분의 최신 CPU는 기본적으로 제곱근 연산을 제공합니다. 따라서 일반적인 최신 하드웨어의 일반적인 프로그래밍 언어를 사용하면 거의 확실하게 작업이 궁극적으로 수행됩니다.
거의 모든 최신 범용 CPU에서 사용하는 방법에 대해 이야기 해 보겠습니다.
숫자 표현
우리가 가장 먼저 이해해야 할 것은 컴퓨터가 실제로 우리가 말하는 일종의 숫자를 어떻게 나타내는 지입니다. 그것들은 일종의 과학적 표기법으로 저장됩니다.
이제 -134.5와 같은 숫자가 -1.345 \ times 10 ^ {2}로 표시되는 곳에 익숙한 과학적 표기법입니다.
p>
0이 아닌 숫자는 개념적으로 세 부분으로 구성된이 형식으로 나타낼 수 있습니다. 기호 (즉, 숫자 양수 또는 음수), 가수 (1을 포함하지만 10을 포함하지 않는 1과 10 사이의 숫자,이 경우 1.345), 지수 (기수를 올릴 거듭 제곱입니다.이 경우 2; 지수는 일반적으로 음수이거나 0 일 수 있습니다.)
표현 거의 모든 현대 컴퓨터에서 사용하는 것은 숫자가 10 진수가 아닌 이진 표현을 사용하여 저장된다는 점을 제외하면 매우 유사합니다. 따라서 부호 비트와 0을 무시하면 (0의 제곱근을 찾는 것은 사소하고 음수의 제곱근은 실수가 아니기 때문에) 양수는 실제로 m \ times 2 ^ {e} 형식으로 저장됩니다. m은 1과 2 사이의 숫자입니다 (1은 포함하지만 2는 포함하지 않음).
이진 점을 이동할 수있는 방식 때문에이 표현을 “부동 소수점”이라고합니다. 이 모든 것이 중요한 이유는 CPU가 제곱근 계산을 돕기 위해 표현을 사용하기 때문입니다. 지수가 짝수라고 가정합니다. 그런 다음 :
\ sqrt {m \ times 2 ^ {2 \ epsilon}} = \ sqrt {m} \ times 2 ^ {\ epsilon}
마찬가지로, 지수가 홀수 :
\ sqrt {m \ times 2 ^ {2 \ epsilon + 1}} = \ sqrt {2} \ sqrt {m} \ times 2 ^ {\ epsilon}
m은 [1,2) 범위에 있습니다. 이것은 우리가 어떤 숫자의 제곱근을 계산하는 문제를 그 범위에있는 숫자의 제곱근 계산 중 하나로 줄였다는 것을 의미합니다. 또는 [1,4) 범위의 숫자 인 \ sqrt {2}를 미리 계산하지 않으려면. 어느 쪽이든 이제 해당 숫자 범위에서 잘 작동하는 방법을 사용할 수 있으므로 문제를 극적으로 단순화했습니다.
곱셈과 나눗셈
이제 여기까지 왔으므로 (다른 답변을 살펴본 경우) 해결책은 이제 Newton-Raphson 반복과 같은 방법을 사용하여 제곱을 계산하는 것이라고 생각할 수 있습니다. 뿌리. n의 제곱근을 계산하려면 초기 추측 x\_0을 선택하고 반복합니다.
x\_ {i + 1} = \ frac {1} {2} \ left (x\_i + \ frac {n} {x\_i } \ right)
이 대답은 틀 렸습니다 . 글쎄요, 그것이 당신에게 정답을 줄 것이라는 점에서 잘못된 것은 아닙니다. 하지만 자존심이 강한 CPU 설계자 (또는 소프트웨어로 구현해야하는 라이브러리 작성자)가 이런 방식으로 부동 소수점 제곱근을 구현하지 않는다는 점에서 잘못되었습니다.
2로 나누는 것은 매우 저렴합니다. 이진 연산 (베이스 2이므로 이진 점을 한 자리 이동). 그러나 다른 분할은 매우 비용이 많이 드는 작업이며이 경우 작업을 여러 번 수행해야합니다.
분할은 실제로 비용이 많이 들기 때문에 최신 CPU는 유사한 반복 알고리즘을 사용합니다. (실제로는 아님) Newton-Raphson 반복으로 나누기! 분명히 우리는 내부 루프에서 하드웨어에서이 작업을 수행하고 싶지 않습니다.
최신 컴퓨터 하드웨어에서는 수행하는 것이 훨씬 저렴합니다. 나눗셈 연산보다 곱셈 연산입니다. 이유는 설명하기가 조금 복잡합니다. 그것은 우리가 예전보다 훨씬 더 많은 트랜지스터를 칩에 넣을 수 있다는 사실과 관련이 있으며 곱셈은 많은 트랜지스터로 효율적으로 이동할 수있는 문제입니다. 자세한 내용에 관심이 있으면 월 레이스 나무 를 찾아보세요.
어쨌든 요점은 곱셈이 비교적 저렴한 연산이라는 것입니다. 따라서 나눗셈이 아닌 곱셈의 관점에서 제곱근 연산을 구현할 수 있다면 더 좋을 것입니다.
Newton-Raphson, 두 개를 가져 가세요
이제 첫 번째 핵심 통찰력이 있습니다. 제곱근을 계산하는 대신 제곱근의 역수 를 계산합니다. 즉, \ sqrt {n} 대신 \ frac {1} {\ sqrt {n}}를 계산합니다. 이것은 계산하기 훨씬 쉬운 숫자라는 것이 밝혀졌습니다. 제곱근이 필요한 경우이 숫자에 n을 곱하면 완료됩니다.
역수 제곱근에 대한 Newton-Raphson 방법은 다음과 같습니다. . x\_0이 \ frac {1} {\ sqrt {n}}에 대한 초기 추정치 인 경우 다음을 반복합니다.
x\_ {i + 1} = \ frac {1} {2} x\_i \ left (3- n {x\_i} ^ 2 \ right)
다시 말하지만, 2로 나누는 것은 상당히 저렴하고 다른 모든 것은 곱셈과 덧셈 / 뺄셈입니다.
이것은 구현하기에 좋은 방법입니다. 소프트웨어에서. 또한, 많은 실제 상황 (예 : 피타고라스 정리를 사용하여 벡터 정규화)에서 역수 제곱근이 제곱근보다 실제로 더 유용하다는 점을 지적 할 가치가 있습니다. root.
그러나 이것은 일반적으로 하드웨어에서 구현되는 방식이 아닙니다.
Goldschmidt의 알고리즘
이제 제곱근과 역수 제곱근을 함께 계산하는 Goldschmidt의 알고리즘을 볼 수 있습니다.
주어진 b\_0 = n, b\_n = b\_0 {와 같은 일련의 숫자 Y\_i를 찾을 수 있다면 Y\_0} ^ 2 {Y\_1} ^ 2 \ cdots {Y\_ {n-1}} ^ 2가 1에 접근하면 y\_n = {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}}이 \ frac에 접근합니다. {1} {\ sqrt {b\_0}} 및 x\_n = b\_0 {Y\_0} {Y\_1} \ cdots {Y\_ {n-1}}는 \ sqrt {b\_0}에 접근합니다.
우리가 사용하는 시리즈는 본질적으로 Newton-Raphson 업데이트 단계 :
\ begin {align *} b\_i & = b\_ {i-1} {Y\_ {i-1}} ^ 2 \\ Y\_i & = \ frac {1} {2 } (3-b\_i) \ end {align *}
그리고 그런 다음 제곱근을 추적 할 수 있습니다.
\ begin {align *} x\_0 & = n Y\_0 \\ x\_ {i} & = x\_ {i-1} Y\_i \ end {align *}
역수 제곱근 :
\ begin {align *} y\_0 & = Y\_0 \\ y\_ {i} & = y\_ {i-1} Y\_i \ end {align *}
그러나 우리가 x\_i와 y\_i를 추적한다면 b\_i = x\_ {i-1} y\_ {i-1}을 관찰하십시오. 따라서 실제로 b\_i를 추적 할 필요가 없습니다.
\ begin {align *} Y\_i & = \ frac {1} {2} \ left (3-b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1-b\_i \ right) \\ & = 1 + \ frac {1} {2} \ left (1-x\_ {i-1} y\_ {i-1} \ right ) \ end {align *}
이제 Y\_i를 추적 할 필요도 없습니다.
\ begin {align *} x\_i & = x\_ {i-1} \ 왼쪽 (1 + \ frac {1} {2} \ left (1-x\_ {i-1} y\_ {i-1} \ 오른쪽) \ 오른쪽) \\ & = x\_ {i-1} + x\_ {i- 1} \ frac {1} {2} \ left (1-x\_ {i-1} y\_ {i-1} \ 오른쪽) \\ y\_i & = y\_ {i-1} \ left (1 + \ frac {1 } {2} \ left (1-x\_ {i-1} y\_ {i-1} \ 오른쪽) \ 오른쪽) \\ & = y\_ {i-1} + y\_ {i-1} \ frac {1} { 2} \ left (1-x\_ {i-1} y\_ {i-1} \ right) \ end {align *}
여기에는 제거 할 수있는 중복 계산이 있으며 다음을 제안합니다. 연산. \ frac {1} {\ sqrt {n}}에 대한 근사값으로 Y가 주어지면 다음을 설정합니다.
\ begin {align *} x\_0 & = n Y \\ y\_0 & = Y \ end {align * }
그런 다음 반복 :
\ begin {align *} r\_i & = \ frac {1} {2} \ left (1-x\_i y\_i \ right) \\ x\_ {i +1} & = x\_i + x\_i r\_i \\ y\_ {i + 1} & = y\_i + y\_i r\_i \ end {align *}
2로 나누는 것이 저렴하더라도 우리는 그것을 피할 수 있습니다 y\_i 대신 h\_i = \ frac {1} {2} y\_i를 추적합니다. 이것이 Goldschmidt의 알고리즘입니다.
Y가 \ frac {1} {\ sqrt {n}}에 대한 근사치라고 가정합니다. 설정 :
\ begin {align *} x\_0 & = n Y \\ h\_0 & = \ frac {Y} {2} \ end {align *}
그런 다음 반복 :
\ begin {align *} r\_i & = \ frac {1} {2}-x\_i h\_i \\ x\_ {i + 1} & = x\_i + x\_i r\_i \\ h\_ {i + 1} & = h\_i + h\_i r\_i \ end {align *}
그런 다음 x\_i는 \ sqrt {n}로 수렴하고 h\_n은 \ frac {1} {2 \ sqrt {n}}로 수렴합니다.
하드웨어에서 구현
지금까지는 훌륭했습니다. 확실히 매우 간단한 알고리즘입니다. 하지만 더 나은 이유는 무엇입니까?
최신 CPU에는 종종 융합 곱하기라고하는 최적화 된 곱하기-누적 작업 을 수행하는 빠른 회로가 있습니다. 추가 또는 줄여서 FMA. 이전에 Wallace 트리에 대한 참조를 검색했다면 FMA가 직선 곱셈 연산만큼 효율적일 수 있음을 분명히 알 수 있습니다.
FMA는 가장 유용한 기본 요소 중 하나입니다. 예를 들어 다항식을 평가해야하는 경우 :
p (x) = a\_0 + a\_1 x + a\_2 x ^ 2 + \ cdots a\_n x ^ n
Horner s 규칙은 기본적으로 FMA의 무리입니다.
\ begin {align *} p\_ {n-1} & = a\_ {n-1} + x a\_n \\ p\_ {n-2} & = a\_ {n-2} + x p\_ {n-1} \\ & \ vdots \\ p\_1 & = a\_1 + x p\_2 \\ p\_0 & = a\_0 + x p\_1 \ end {align *}
Goldschmidt 알고리즘의 내부 루프는 3 개의 FMA이며 다른 것은 없습니다.이것이 이점이되는 이유입니다. 한 종류의 회로 (아마도 하나의 회로 만 있으면됩니다. 두 번째 두 FMA는 독립적이므로 파이프 라이닝의 이점을 누릴 수 있음)와 일부 제어 로직 만 있으면 모든 것을 구현할 수 있습니다. 그리고 이것은 다른 많은 연산에 유용한 회로이므로 제곱근 연산에만 많은 하드웨어를 낭비하지 않습니다.
퍼즐의 두 번째 마지막 부분은 좋은 이니셜을 얻는 방법입니다. 짧은 대답은 테이블 조회를 사용하는 것이 가장 좋은 방법이라는 것입니다. 작은 범위의 제곱근 만 찾고 있기 때문에 적당한 크기의 테이블조차도 매우 효율적입니다.
퍼즐의 마지막 부분은 다음과 같습니다. 완료시기를 어떻게 알 수 있습니까? 반복? 이에 대한 답은 우리가 사용하는 숫자의 정밀도와 초기 추정치가 얼마나 좋은지 알고 있다는 것입니다. 이를 통해 사전에 필요한 최대 반복 횟수를 계산할 수 있습니다. 따라서 우리는 실제로 그렇게 반복하지 않고 고정 된 횟수 만 반복합니다.