제곱근 함수는 어떻게 구현됩니까?
제곱근 함수는 어떻게 구현됩니까?
C ++로 이진 검색 을 사용한 간단한 구현
double root(double n){
double lo = 0, hi = n, mid;
for(int i = 0 ; i < 1000 ; i++){
mid = (lo+hi)/2;
if(mid*mid == n) return mid;
if(mid*mid > n) hi = mid;
else lo = mid;
}
return mid;
}
참고 while루프가 가장 일반적인 이진 검색을하지만 개인적으로 내가 사용하여 선호 for진수를 처리 할 때, 그것을 처리하는 특별한 경우를 저장하고 그런 작은 루프에서 매우 정확한 결과를 얻을 수 1000또는 500(둘 다 거의 모든 숫자에 대해 동일한 결과를 줄 것이다 그러나 안전을 위해).
편집 : 제곱근 계산에 특화된 다양한 특수 목적 방법에 대해서는 이 Wikipedia 기사 를 확인하십시오 .
Intel 하드웨어에서는 종종 하드웨어 SQRT 명령어 위에 구현됩니다. 일부 라이브러리는 바로 그 결과를 그대로 사용하고, 일부 라이브러리는 코너 케이스에서 더 정확하게 만들기 위해 몇 번의 Newton 최적화를 거치게 될 수 있습니다.
FDLIBM (Freely Distributable LIBM)은 sqrt의 문서화 된 버전을 가지고 있습니다. e_sqrt.c .
정수 산술을 사용하는 하나의 버전과 한 번에 한 비트를 수정하는 반복 공식이 있습니다.
또 다른 방법은 Newton의 방법을 사용합니다. 흑마 법과 룩업 테이블로 시작하여 처음 8 비트를 얻은 다음 반복 공식을 적용합니다.
y_{i+1} = 1/2 * ( y_i + x / y_i)
여기서 x는 우리가 시작한 숫자입니다. 이것은 헤론의 방법에 대한 바빌로니아 의 방법입니다. 그것은 AD 1 세기에 알렉산드라의 영웅으로 거슬러 올라갑니다.
Fast inverse square root 또는 reciproot 라는 또 다른 방법이 있습니다 . 이것은 1 / sqrt (x)의 값을 찾기 위해 "사악한 부동 소수점 비트 레벨 해킹"을 사용합니다. i = 0x5f3759df - ( i >> 1 );그것은 mantisse와 exponent를 사용하여 float의 이진 표현을 이용합니다. 우리의 숫자 x가 (1 + m) * 2 ^ e이면, 여기서 m은 가수이고 e는 지수이고 결과는 y = 1 / sqrt (x) = (1 + n) * 2 ^ f입니다. 로그 작성
lg(y) = - 1/2 lg(x)
f + lg(1+n) = -1/2 e - 1/2 lg(1+m)
따라서 결과의 지수 부분이 숫자의 지수 인 -1/2임을 알 수 있습니다. 흑 마법은 기본적으로 지수에 대해 비트 단위 이동을 수행하고 가수에 선형 근사를 사용합니다.
좋은 첫 번째 근사값을 얻었 으면 Newton의 방법을 사용하여 더 나은 결과를 얻고 마지막으로 마지막 숫자를 수정하기 위해 비트 수준 작업을 수행 할 수 있습니다.
이것은 Newton 알고리즘의 구현입니다 . https://tour.golang.org/flowcontrol/8을 참조 하십시오 .
func Sqrt(x float64) float64 {
// let initial guess to be 1
z := 1.0
for i := 1; i <= 10; i++ {
z -= (z*z - x) / (2*z) // MAGIC LINE!!
fmt.Println(z)
}
return z
}
다음은 매직 라인에 대한 수학적 설명입니다. 다항식 $ f (x) = x ^ 2-a $의 근을 구한다고 가정합니다. Newton의 방법에 따라 초기 추측 값 $ x_0 = 1 $로 시작할 수 있습니다. 다음 추측은 $ x_1 = x_0-f (x_0) / f '(x_0) $입니다. 여기서 $ f'(x) = 2x $입니다. 따라서 새로운 추측은
$ x_1 = x_0-(x_0 ^ 2-a) / 2x_0 $
sqrt (); 기능 뒤에서.
항상 그래프의 중간 지점을 확인합니다. 예 : sqrt (16) = 4; sqrt (4) = 2;
이제 sqrt (10) ==와 같이 16 또는 4 안에 입력을 제공하면?
2와 4의 중간 점 즉 = x를 찾은 다음 다시 x와 4의 중간 점을 찾습니다 (이 입력에서 하한은 제외됨). 완벽한 답을 얻을 때까지이 단계를 반복합니다. 즉, sqrt (10) == 3.16227766017. 그것은 b / w 2와 4입니다.이 모든 내장 함수는 미적분, 미분 및 통합을 사용하여 생성됩니다.
Python에서 구현 : 루트 값의 바닥은이 함수의 출력입니다. 예 : 8의 제곱근은 2.82842 ...입니다.이 함수는 '2'를 출력합니다.
def mySqrt(x):
# return int(math.sqrt(x))
if x==0 or x==1:
return x
else:
start = 0
end = x
while (start <= end):
mid = int((start + end) / 2)
if (mid*mid == x):
return mid
elif (mid*mid < x):
start = mid + 1
ans = mid
else:
end = mid - 1
return ans
제곱근을 계산하려면 (내장 math.sqrt 함수를 사용하지 않음) :
SquareRootFunction.java
public class SquareRootFunction {
public double squareRoot(double value,int decimalPoints)
{
int firstPart=0;
/*calculating the integer part*/
while(square(firstPart)<value)
{
firstPart++;
}
if(square(firstPart)==value)
return firstPart;
firstPart--;
/*calculating the decimal values*/
double precisionVal=0.1;
double[] decimalValues=new double[decimalPoints];
double secondPart=0;
for(int i=0;i<decimalPoints;i++)
{
while(square(firstPart+secondPart+decimalValues[i])<value)
{
decimalValues[i]+=precisionVal;
}
if(square(firstPart+secondPart+decimalValues[i])==value)
{
return (firstPart+secondPart+decimalValues[i]);
}
decimalValues[i]-=precisionVal;
secondPart+=decimalValues[i];
precisionVal*=0.1;
}
return(firstPart+secondPart);
}
public double square(double val)
{
return val*val;
}
}
MainApp.java
import java.util.Scanner;
public class MainApp {
public static void main(String[] args) {
double number;
double result;
int decimalPoints;
Scanner in = new Scanner(System.in);
SquareRootFunction sqrt=new SquareRootFunction();
System.out.println("Enter the number\n");
number=in.nextFloat();
System.out.println("Enter the decimal points\n");
decimalPoints=in.nextInt();
result=sqrt.squareRoot(number,decimalPoints);
System.out.println("The square root value is "+ result);
in.close();
}
}
long long int floorSqrt(long long int x)
{
long long r = 0;
while((long)(1<<r)*(long)(1<<r) <= x){
r++;
}
r--;
long long b = r -1;
long long ans = 1 << r;
while(b >= 0){
if(((long)(ans|1<<b)*(long)(ans|1<<b))<=x){
ans |= (1<<b);
}
b--;
}
return ans;
}
바빌로니아 방식이라는 것이 있습니다.
static float squareRoot(float n)
{
/*We are using n itself as
initial approximation This
can definitely be improved */
float x = n;
float y = 1;
// e decides the accuracy level
double e = 0.000001;
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x;
}
자세한 정보 링크 : https://www.geeksforgeeks.org/square-root-of-a-perfect-square/
따라서 내장 된 ceil 또는 round 함수를 사용할지 여부에 대한 사양이없는 경우 Newton-Raphson 메서드를 사용하여 부호없는 숫자의 제곱근을 찾는 Java의 재귀 적 접근 방식이 있습니다.
public class FindSquareRoot {
private static double newtonRaphson(double N, double X, double oldX) {
if(N <= 0) return 0;
if (Math.round(X) == Math.ceil(oldX))
return X;
return newtonRaphson(N, X - ((X * X) - N)/(2 * X), X);
}
//Driver method
public static void main (String[] args) {
System.out.println("Square root of 48.8: " + newtonRaphson(48.8, 10, 0));
}
}
나는 sqrt 함수도 만들고 있는데, 100000000 반복은 14 초가 걸리지 만 여전히 sqrt의 1 초에 비해 아무것도 없습니다.
double mysqrt(double n)
{
double x = n;
int it = 4;
if (n >= 90)
{
it = 6;
}
if (n >= 5000)
{
it = 8;
}
if (n >= 20000)
{
it = 10;
}
if (n >= 90000)
{
it = 11;
}
if (n >= 200000)
{
it = 12;
}
if (n >= 900000)
{
it = 13;
}
if (n >= 3000000)
{
it = 14;
}
if (n >= 10000000)
{
it = 15;
}
if (n >= 30000000)
{
it = 16;
}
if (n >= 100000000)
{
it = 17;
}
if (n >= 300000000)
{
it = 18;
}
if (n >= 1000000000)
{
it = 19;
}
for (int i = 0; i < it; i++)
{
x = 0.5*(x+n/x);
}
return x;
}
그러나 가장 빠른 구현은 다음과 같습니다.
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
float mysqrt(float n) {return 1/Q_rsqrt(n);}
Golang에서 내 솔루션을 따릅니다.
package main
import (
"fmt"
)
func Sqrt(x float64) float64 {
z := 1.0 // initial guess to be 1
i := 0
for int(z*z) != int(x) { // until find the first approximation
// Newton root algorithm
z -= (z*z - x) / (2 * z)
i++
}
return z
}
func main() {
fmt.Println(Sqrt(8900009870))
}
클래식 / 일반 솔루션을 따릅니다.
package main
import (
"fmt"
"math"
)
func Sqrt(num float64) float64 {
const DIFF = 0.0001 // To fix the precision
z := 1.0
for {
z1 := z - (((z * z) - num) / (2 * z))
// Return a result when the diff between the last execution
// and the current one is lass than the precision constant
if (math.Abs(z1 - z) < DIFF) {
break
}
z = z1
}
return z
}
func main() {
fmt.Println(Sqrt(94339))
}
참고 URL : https://stackoverflow.com/questions/3581528/how-is-the-square-root-function-implemented
'code' 카테고리의 다른 글
| ngSubmit은 Angular 2 형식으로 페이지를 새로 고칩니다. (0) | 2020.12.03 |
|---|---|
| 런타임에 사용자 정의 파일에 기록하도록 log4j 구성 (0) | 2020.12.03 |
| 함수 내에서 클래스를 만들고 포함하는 함수의 범위에 정의 된 함수에 액세스 (0) | 2020.12.02 |
| 파이썬에서 희소 3D 행렬 / 배열? (0) | 2020.12.02 |
| 하위 프로세스를 사용할 때 Python에서 티 동작을 복제하는 방법은 무엇입니까? (0) | 2020.12.02 |