수천 자릿수의 정수 제곱근을 찾기 위해 프로그램을 작성해야합니다. 그런 많은 수를 저장하고 나눌 데이터 유형이 없기 때문에 Newton Raphson을 사용할 수 없습니다. C에서 긴 배열을 사용하여 숫자를 저장하고 있습니다. 어쩌면 자릿수를 반복하여 제곱근을 찾는 알고리즘이 있습니까?아주 큰 숫자의 정수 제곱근을 찾기위한 효율적인 알고리즘은 무엇입니까?
편집 :
GMP와 같은 외부 라이브러리를 사용할 수 없습니다.
학교에서 가르치는 제곱근을 계산하기 위해 긴 나누기 방법을 구현할 수 있습니다. 이 메소드를 기본 10에 구현할 수 있으며 결과는 왼쪽에서 오른쪽으로 숫자별로 계산됩니다. 정수 부분이 계산되면 중지 할 수 있습니다.
이 방법을 시도했지만 문제는 제수가 커지다는 것입니다. 그리고 만약 주어진 숫자가 1000 자릿수라면, 나누고 나머지를 찾는 것은 매우 어려울 것입니다. – Naman
숫자를 C- 문자열 (문자 배열은 'NUL'문자로 끝남)에 저장할 수 있으며 우리가 논문에서 수행 한 방식대로 산술 연산을 수행 할 수 있습니다. 나는 추가와 곱셈을 위해 [이 예제] (http://codepad.org/T2AcSJzN) 년 전 썼다. 점차적으로 필자는 기능을 추가하고 프로파일 링의 도움으로 여분의 시간을 줄였으며 몇 개월 만에 효율적으로 많은 수의 라이브러리가 완성되었습니다. 써드 파티 대형 정수 라이브러리를 사용하지 않으려면 기본적인 산술 개념을 사용하여 직접 작성하고 견고하고 효율적으로 만드십시오. –
이 방법의 경우 곱하기 및 빼기 작업 만 필요합니다. –
대상 번호를 입력 할 수있는 경우 은에 하나 이상의 큰 번호를 저장해야합니다. Newton-Raphson의 경우 숫자를 반으로하고 더할 수 있어야합니다. 부서를 사용하지 않고 숫자를 반으로 줄이는 방법을 생각해보십시오.
ETA : 수정 : 배수는 배가 및 빼기로 피할 수 있습니다.
당신은 당신의 '의 bignum'구현에 매우 비현실적인 제약을 많이 갖고있는 것 같다. 이진 검색을 제안 할 수 있습니까? 반복 할 때마다 반값 값 mid = (hi + lo)/2을 찾고 검색 공간을 [hi, mid] 또는 [mid, lo]으로 제 공합니다.
참조 [위키 피 디아 (http://en.wikipedia.org/wiki/Methods_of_computing_square_roots). –
@alexvii 소수 자리에 주어진 방법은 x (20 * p + x)를 찾아야하지만 내 자리가 크기 때문에 p도 커지며 그러한 값을 계산하는 것은 매우 느릴 수 있습니다. 그런 큰 숫자를 늘릴 필요가없는 방법이 있는지 궁금합니다. – Naman
외부 라이브러리를 가져올 수 있습니까? [GNU 다중 정밀 산술 라이브러리] (https://gmplib.org/)이기 때문에. –