임의정밀산술

이 기사는 검증을 위해 추가 인용이 필요합니다. 신뢰할 수 있는 출처에 인용을 추가하여 이 기사를 개선하는 데 도움을 주세요. 출처가 없는 재료는 문제가 발생하여 제거될 수 있습니다. 출처 찾기 : "임의 정밀도 산술" – 뉴스 · 신문 · 서적 · 학자 · JSTOR (2007년 7월) (템플 제거 도움말)

부동소수점 형식들
IEEE 754
16비트:하프(바이너리16) 32비트: 싱글(2진수 32), 십진수 32 64비트: 더블(이진 64), 십진 64 128비트: 4배(2진수 128), 10진수 128 256비트: Octuple(바이너리256) 확장정밀도
다른.
미니플로트 bfloat 16 텐서플로트-32 마이크로소프트 바이너리 포맷 IBM 부동 소수점 아키텍처 PM버스 리니어-11 G.711 8비트 플로트
대안
임의 정밀도
v t

컴퓨터 과학에서 임의의 정밀도 산술은 비그넘 산술, 다중 정밀도 산술 또는 때로는 무한 정밀도 산술이라고도 하며, 호스트 시스템의 가용 메모리에 의해서만 정밀도의 자릿수가 제한되는 숫자에 대해 계산이 수행되는 것을 나타냅니다.이는 일반적으로 8비트에서 64비트 사이의 정밀도를 제공하는 대부분의 ALU 하드웨어에서 볼 수 있는 더 빠른 고정 정밀도 산술과 대조됩니다.

몇몇 현대 프로그래밍 언어들은 비그넘을 기본으로 지원하며,^[1][2][3][4] 다른 언어들은 임의의 정밀도의 정수와 부동 소수점 수학에 사용할 수 있는 라이브러리를 가지고 있습니다.이러한 구현은 프로세서 레지스터의 크기와 관련된 고정된 비트 수로 값을 저장하는 것이 아니라 일반적으로 숫자의 가변 길이 배열을 사용합니다.

임의의 정밀도는 산술의 속도가 제한 요소가 아닌 경우 또는 매우 큰 숫자로 정밀한 결과가 필요한 경우에 사용됩니다.많은 컴퓨터 대수 시스템에서 제공하는 기호 계산과 혼동되어서는 안 되며, 이는 수를 π·sin(2)와 같은 표현으로 나타내므로 계산 가능한 모든 수를 무한한 정밀도로 나타낼 수 있습니다.

적용들

일반적인 응용 프로그램은 공개 키 암호화이며, 알고리즘은 일반적으로 수백 자리 수의 정수와 함께 산술을 사용합니다.^[5][6]또 다른 하나는 인위적인 한계와 넘침이 부적절한 상황입니다.또한 고정 정밀도 계산 결과를 확인하고 공식에 필요한 계수에 대한 최적 또는 거의 최적 값을 결정하는 데 유용합니다.^[7] 예를 들어 가우시안 적분에 $\sqrt{\frac{\mathrm{나타나는}}{}}$$$13 {\$textstyle {\frac$ {$1}{3}}}.$

임의의 정밀 산술은 또한 π에서 수백만 또는 그 이상의 숫자와 같은 기본적인 수학 상수를 계산하고 숫자 문자열의 특성을 분석하거나 더 일반적으로 분석을 통해 특정 질문을 탐색하기 어려운 리만 제타 함수와 같은 함수의 정확한 동작을 조사하는 데 사용됩니다.방법들.또 다른 예는 Mandelbrot 세트에서 볼 수 있는 것과 같이 매우 높은 배율의 프랙탈 이미지를 렌더링하는 것입니다.

임의 정밀 산술은 또한 고정 정밀 산술의 고유한 한계인 오버플로우를 피하기 위해 사용될 수 있습니다.999999에서 00000으로 변경되는 5자리 주행 기록계의 디스플레이와 마찬가지로 고정된 정밀도에서 숫자가 너무 커지면 고정된 정수가 랩어라운드를 나타낼 수 있습니다.일부 프로세서는 대신 포화 상태에 의해 오버플로를 처리할 수 있습니다. 즉, 결과가 표현할 수 없는 경우 가장 가까운 표현 가능한 값으로 대체됩니다.(16비트 부호 없는 포화 상태에서 65535에 양의 양을 더하면 65535가 됩니다.)일부 프로세서는 산술 결과가 사용 가능한 정밀도를 초과할 경우 예외를 생성할 수 있습니다.필요한 경우 예외를 포착하여 복구할 수 있습니다. 예를 들어 임의의 정밀도 산술을 사용하여 소프트웨어에서 작업을 다시 시작할 수 있습니다.

많은 경우 태스크 또는 프로그래머는 특정 응용프로그램의 정수 값이 오버플로를 일으킬 만큼 충분히 커지지 않도록 보장할 수 있습니다.그러한 보장은 실용적인 한계에 근거할 수 있습니다: 출석 프로그램은 4,000명의 학생들의 과제 제한을 가질 수 있습니다.프로그래머는 중간 결과가 지정된 정밀도 경계 내에 유지되도록 계산을 설계할 수 있습니다.

리스프, 파이썬, 펄, 해스켈, 루비, 라쿠와 같은 일부 프로그래밍 언어는 모든 정수 연산에 임의의 정밀도를 사용하거나 사용할 수 있는 옵션이 있습니다.이를 통해 성능은 저하되지만 단순 오버플로우로 인해 잘못된 결과(또는 예외)가 발생할 가능성은 제거됩니다.또한 특정 기계의 단어 크기에 상관없이 모든 기계에서 산술 결과가 동일하다는 것을 보장할 수 있습니다.프로그래밍 언어에서 임의의 정밀도를 사용하는 것은 언어를 단순화하기도 하는데, 왜냐하면 숫자는 숫자이고 다양한 수준의 정밀도를 나타내기 위해 여러 유형이 필요하지 않기 때문입니다.

구현이슈

임의 정밀 산술은 프로세서 레지스터에 완전히 들어맞는 숫자를 사용하는 산술보다 상당히 느립니다. 후자는 보통 하드웨어 산술로 구현되는 반면 전자는 소프트웨어로 구현되어야 하기 때문입니다.컴퓨터에 특정 작업(예: 정수 나눗셈 또는 모든 부동 소수점 작업)을 위한 하드웨어가 부족하고 소프트웨어가 제공되는 경우에도 사용 가능한 하드웨어 레지스터와 밀접하게 관련된 숫자 크기(한 두 단어만 해당)를 사용합니다.예외도 있는데, IBM 1620, IBM 1401, Honeywell Liberator 시리즈와 같은 1950년대와 1960년대의 특정 가변 단어 길이 기계는 사용 가능한 스토리지로만 제한된 숫자를 값을 구분하는 추가 비트를 사용하여 조작할 수 있습니다.

숫자는 고정 소수점 형식으로 저장하거나 부동 소수점 형식으로 유의하고 임의의 지수를 곱하여 저장할 수 있습니다.그러나 나눗셈은 거의 즉시 숫자의 무한 반복 시퀀스를 도입하기 때문에 이러한 가능성이 발생하면 표현이 어느 정도 만족스러운 크기로 잘리거나 분자와 분모에 큰 정수를 사용하는 등 유리수를 사용할 수 있습니다.그러나 가장 큰 공약수를 나누어도 유리수를 가진 산술은 매우 빨리 다루기 어려워질 수 있습니다. 즉 1/99 - 1/100 = 1/9900입니다. 그 다음에 1/101을 더하면 결과는 10001/99900이 됩니다.

임의의 정밀한 숫자의 크기는 실제로 사용 가능한 총 스토리지와 계산 시간에 의해 제한됩니다.

임의의 정밀도로 저장된 숫자에 대한 산술 연산을 효율적으로 수행하기 위해 수많은 알고리즘이 개발되었습니다.특히 N자리를 사용한다고 가정하면 큰 N에 대한 점근적 복잡성을 최소화하는 알고리즘이 설계되었습니다.

가장 간단한 알고리즘은 덧셈과 뺄셈입니다. 숫자를 순서대로 더하거나 빼기만 하면 필요에 따라 전달되므로 O(N) 알고리즘이 생성됩니다(큰 O 표기 참조).

비교도 매우 간단합니다.차이가 발견될 때까지 고차 숫자(또는 기계어)를 비교합니다.나머지 숫자/단어를 비교할 필요가 없습니다.최악의 경우는$$θ${\$displaystyle$$\Theta}(N)이지만 일반적으로 훨씬 더 빠르게 진행됩니다.

곱셈의 경우$$손으로 숫자를 곱하는 데 사용되는 가장 간단한 $알고리즘$은 θ ${\$displaystyle$$\Theta} (N) 작업이 필요하지만 쇤하게-스트라센 알고리즘과 같이 O(N log(N) log(N) 복잡성을 달성하는 곱셈 알고리즘이 고안되었습니다.빠른 푸리에 변환을 기반으로 하며, 복잡성이 약간 더 나쁘지만 때때로 더 작은 N에 대해 더 우수한 실제 성능을 갖는 알고리즘도 있습니다.카라츠바 곱셈은 그런 알고리즘입니다.

나눗셈은 나눗셈 알고리즘을 참조하십시오.

복잡도 추정치와 함께 알고리즘 목록은 수학 연산의 계산 복잡도를 참조하십시오.

x86 어셈블리의 예는 외부 링크를 참조하십시오.

미리 설정된 정밀도

REXX와 같은 일부 언어에서는 계산을 수행하기 전에 모든 계산의 정밀도를 설정해야 합니다.Python, Ruby와 같은 다른 언어는 오버플로우를 방지하기 위해 자동으로 정밀도를 확장합니다.

예

인수의 계산은 매우 큰 수를 쉽게 생성할 수 있습니다.다른 용어와 함께 나타나므로 평가 순서에 주의를 기울이면 중간 계산 값이 문제가 되지 않기 때문에 많은 공식(예: 테일러 급수)에서 사용하는 데 문제가 되지 않습니다.요인 수의 근사값을 원하는 경우 스털링의 근사값은 부동 소수점 산술을 사용하여 좋은 결과를 제공합니다.고정 크기의 정수 변수에 대한 가장 큰 대표 값은 아래 표와 같이 비교적 작은 인수에 대해서도 초과될 수 있습니다.부동 소수점 숫자도 곧 어긋나므로 숫자의 로그로 계산을 다시 계산하는 데 도움이 될 수 있습니다.

그러나 큰 요인에 대한 정확한 값이 필요한 경우에는 다음 의사 코드와 같이 특수한 소프트웨어가 필요합니다. 이 소프트웨어는 고전적인 알고리즘을 구현하여 연속적인 요인 수 1, 1×2, 1×2×3, 1×2×3×4 등을 계산합니다.

상수: 제한 = 1000% 충분한 숫자.기본 = 10% 시뮬레이션된 산술의 기본값입니다.요인 한계 = 365% 해결할 목표 수, 365! tdigit:문자 = ["0",1",2",3",4",5",6",7",8",9"] 변수의 배열 [0:9] 숫자:배열[1:제한] 0.9 %의 큰 숫자. 운반, d: 곱셈 중 정수 % 보조자.마지막:정수 % 큰 숫자의 숫자로 인덱스를 지정합니다. 텍스트:배열[1:출력에 대한 문자 % Scratchpad의 한계]입니다. digit[*] := 0 % 전체 배열을 지웁니다.마지막 := 1 % 큰 숫자는 한 자리 숫자로 시작하여 [1] := 1 % 큰 숫자의 유일한 숫자는 1입니다. n : = 1 ~ 요인 설계 한계: % 1!, 2!, 3!, 4! 등을 생성하는 단계: = 0 % 운반: i : = 1 ~ 마지막: % 모든 숫자를 따라 단계를 수행합니다.d : = digit[i] * n + carry % 한 자릿수를 곱합니다. digit[i] : = dmod Base % 결과의 낮은 자릿수를 유지합니다. carry : = d div Base % 다음 자릿수로 이월합니다.harry > 0: % 남은 캐리를 큰 숫자로 저장합니다. last >= Limit : error ("overflow")가 마지막인 경우 := last + 1 % 한 자리 더. digit[last] := carry mod Base carry := carry div Base % 마지막 자리를 캐리에서 제거합니다. text[*] := " % 이제 출력을 준비합니다.i : = 1 ~ last : % 이진에서 텍스트로 변환. text [ Limit - i + 1 ] : = tdigit [ digit [ i ] % 순서를 반대로 변경합니다. 인쇄 텍스트 [ Limit - last + 1 : Limit ], " = ", n, "!"

보기에 있는 예제를 사용하여 여러 세부 사항에 대해 논의할 수 있습니다.가장 중요한 것은 빅 넘버의 대표성에 대한 선택입니다.이 경우 숫자에는 정수 값만 필요하므로 고정 너비 정수 배열이 적합합니다.배열의 연속 요소가 베이스의 더 높은 전력을 나타내도록 하는 것이 편리합니다.

두 번째로 중요한 결정은 산술의 기초를 선택하는 것입니다, 여기서 10.여러 가지 고려 사항이 있습니다.스크래치 패드 변수 d는 한 자릿수 곱셈에 이전 자릿수의 곱셈을 더한 결과를 유지할 수 있어야 합니다.10진법에서 16비트 정수는 최대 32767을 허용하므로 확실히 적합합니다.그러나 이 예제에서는 n의 값이 한 자리로 제한되지 않는다는 점에서 속임수를 사용합니다.이것은 n > 3200 정도에서 메소드가 실패하는 결과를 가져옵니다.보다 일반적인 구현에서는 n도 다자리 표현을 사용합니다.단축키의 두 번째 결과는 다자리 곱셈이 완료된 후 마지막 캐리 값을 한 자리 숫자가 아닌 여러 자리 숫자로 옮겨야 할 수 있다는 것입니다.

또한 인간의 고려를 위해 결과물을 10번 베이스로 인쇄하는 문제도 있습니다.베이스가 이미 10이기 때문에 배열 자릿수의 연속된 숫자를 인쇄하는 것만으로 결과를 나타낼 수 있지만, 가장 높은 순서의 숫자가 마지막에 표시됩니다(123이 "321"로 표시됨).전체 배열을 역순으로 인쇄할 수 있지만, 숫자에 선행 0("00000...")이 표시됩니다.000123")를 인식하지 못할 수 있으므로 이 구현은 공간 padded 텍스트 변수로 표현을 구축한 다음 이를 인쇄합니다.처음 몇 가지 결과(5번째 자리마다 간격을 두고 여기에 주석을 추가함)는 다음과 같습니다.

요인수		컴퓨터 정수 도달 범위
1 =	1!
2 =	2!
6 =	3!
24 =	4!
120 =	5!	8비트	255
720 =	6!
5040 =	7!
40320 =	8!	16비트	65535
3 62880 =	9!
36 28800 =	10!
399 16800 =	11!
4790 01600 =	12!	32비트	42949 67295
62270 20800 =	13!
8 71782 91200 =	14!
130 76743 68000 =	15!
2092 27898 88000 =	16!
35568 74280 96000 =	17!
6 40237 37057 28000 =	18!
121 64510 04088 32000 =	19!
2432 90200 81766 40000 =	20!	64비트	18446 74407 37095 51615
51090 94217 17094 40000 =	21!
11 24000 72777 76076 80000 =	22!
258 52016 73888 49766 40000 =	23!
6204 48401 73323 94393 60000 =	24!
1 55112 10043 33098 59840 00000 =	25!
40 32914 61126 60563 55840 00000 =	26!
1088 88694 50418 35216 07680 00000 =	27!
30488 83446 11713 86050 15040 00000 =	28!
8 84176 19937 39701 95454 36160 00000 =	29!
265 25285 98121 91058 63630 84800 00000 =	30!
8222 83865 41779 22817 72556 28800 00000 =	31!
2 63130 83693 36935 30167 21801 21600 00000 =	32!
86 83317 61881 18864 95518 19440 12800 00000 =	33!
2952 32799 03960 41408 47618 60964 35200 00000 =	34!	128비트	3402 82366 92093 84634 63374 60743 17682 11455
1 03331 47966 38614 49296 66651 33752 32000 00000 =	35!

이 구현은 산술에 내장된 컴퓨터를 보다 효과적으로 활용할 수 있습니다.간단한 에스컬레이션은 기본 100(출력을 위한 번역 프로세스의 해당 변경 사항)을 사용하거나, 컴퓨터 변수(예: 32비트 정수)가 충분히 넓은 경우 10,000과 같은 더 큰 기본을 사용할 수 있습니다.컴퓨터에 내장된 정수 연산에 더 가까운 2제곱 기반에서 작업하는 것은 장점을 제공하지만, 출력을 위해 소수 기반으로 변환하는 것은 더 어렵습니다.전형적인 현대 컴퓨터에서 덧셈과 곱셈은 피연산자의 값과 무관하게 일정한 시간이 소요되므로(피연산자가 단일 기계어로 적합한 한) 숫자 배열의 각 요소에 가능한 한 많은 큰 숫자를 패킹하는 데 큰 이득이 있습니다.컴퓨터는 예제와 같이 mod와 div의 두 가지 연산을 필요로 하지 않고도 제품을 디지털과 캐리로 분할할 수 있는 기능을 제공할 수 있으며, 거의 모든 산술 단위는 다중 정밀 가감산에서 활용할 수 있는 캐리 플래그를 제공합니다.이런 종류의 세부 사항은 기계 코드 프로그래머들의 목록이고, 적절한 어셈블리 언어 빅넘버 루틴은 고급 언어의 컴파일 결과보다 더 빨리 실행될 수 있습니다.이러한 기능에 대한 직접적인 액세스를 제공하지 않고, 대신 최적화 컴파일러를 사용하여 높은 수준의 문을 대상 시스템의 모델에 매핑합니다.

한 자릿수 곱셈의 경우 작업 변수는 (base-1)² + 캐리 값을 유지할 수 있어야 하며, 캐리의 최대값은 (base-1)입니다.마찬가지로, 숫자 배열을 인덱싱하는 데 사용되는 변수 자체는 폭이 제한됩니다.인덱스를 확장하는 간단한 방법은 i와 j가 작은 정수인 (블록 i, digit j)를 통해 주소를 지정하거나 인덱스 변수에 빅넘버 기술을 사용하는 것으로 확장할 수 있는 편리한 크기의 블록에서 빅넘버의 숫자를 처리하는 것입니다.궁극적으로 기계 저장 용량과 실행 시간은 문제 크기에 제한을 미칩니다.

역사

IBM의 첫 번째 비즈니스 컴퓨터인 IBM 702(진공관 기계)는 1950년대 중반에 1자리에서 511자리까지의 길이의 숫자 문자열에 정수 연산을 하드웨어로 완전히 구현했습니다.임의 정밀 산술의 최초의 광범위한 소프트웨어 구현은 아마도 Maclips의 것일 것입니다.그 후 1980년경, 운영 체제 VAX/VMS와 VM/CMS는 하나의 경우에는 문자열 함수의 집합으로, 다른 경우에는 EXEC 2와 REXX 언어로 bignum facility를 제공했습니다.

1959-1970년 IBM 1620을 통해 초기의 광범위한 구현이 가능했습니다.1620은 이산 트랜지스터를 사용하는 십진법의 기계였지만, 하드웨어(룩업 테이블을 사용하는)를 사용하여 2개에서 사용 가능한 메모리까지 길이의 숫자 문자열에 대해 정수 연산을 수행했습니다.부동 소수점 산술의 경우, 가수는 100자리 이하로 제한되었고, 지수는 두 자리로만 제한되었습니다.가장 큰 메모리는 60,000자리를 제공했지만, 1620용 포트란 컴파일러는 기본값이 만족스럽지 않을 경우 제어 카드에 지정할 수 있지만 10과 같은 고정된 크기로 설정되었습니다.

소프트웨어 라이브러리

대부분의 컴퓨터 소프트웨어에서 임의의 정밀도 산술은 데이터 유형과 서브루틴을 제공하는 외부 라이브러리를 호출하여 요청된 정밀도로 숫자를 저장하고 계산을 수행하는 방식으로 구현됩니다.

라이브러리마다 임의의 정밀한 숫자를 표현하는 방법이 다르며, 일부 라이브러리는 정수만을 사용하여 작동하며, 다른 라이브러리는 부동 소수점 숫자를 다양한 기저(소수점 또는 이진수)에 저장합니다.숫자를 단일 값으로 표현하는 대신 일부는 숫자를 분자/분모 쌍(이성)으로 저장하고 일부는 저장 제한이 있지만 계산 가능한 숫자를 완전히 표현할 수 있습니다.기본적으로 튜링 기계는 $R{\displaystyle \mathbb{}}$ ${\$$$\$mathbb$$${$R}$의 카디널리티가 $Z{\displaystyle \mathbb{}}${\$displaystyle$ \$mathbb {Z$}의$$ 카디널리티를 초과하므로 모든 실수를 나타낼 수 없습니다$.$

참고 항목

• 퓌러 알고리즘
• 카라츠바 알고리즘
• 혼합정밀산술
• 쇤하게-스트라센 알고리즘
• 톰-쿡 곱셈
• 리틀 엔디안 베이스 128

참고문헌

더보기

• Knuth, Donald (2008). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Addison-Wesley. ISBN 978-0-201-89684-8.Knuth, Donald (2008). Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (3rd ed.). Addison-Wesley. ISBN 978-0-201-89684-8.섹션 4.3.1: 고전적 알고리즘
• Derick Wood (1984). Paradigms and Programming with Pascal. Computer Science Press. ISBN 0-914894-45-5.
• Richard Crandall, Carl Pomerance (2005). Prime Numbers. Springer-Verlag. ISBN 9780387252827.Richard Crandall, Carl Pomerance (2005). Prime Numbers. Springer-Verlag. ISBN 9780387252827.제9장 대정수 연산을 위한 빠른 알고리즘

외부 링크

• Randall Hyde의 조립 기술 9.3장에서는 x86-조립의 예를 들어 다중 정밀 산술에 대해 논의합니다.
• 로제타 코드 작업 임의-정밀 정수 95개 이상의 프로그래밍 언어가 임의의 정밀 산술을 사용하여 5**4**3**2의 값을 계산하는 스타일의 사례 연구.