임의 정밀도 연산
컴퓨터 과학에서 임의 정밀도 연산(Arbitrary-precision arithmetic)은 큰 수 연산, 다중 정밀도 연산 또는 때로는 무한 정밀도 연산이라고도 불리며, 호스트 시스템의 가용 메모리에 의해서만 정밀도의 자릿수가 잠재적으로 제한되는 수에 대해 계산이 수행됨을 나타낸다. 이는 일반적으로 8비트에서 64비트의 정밀도를 제공하는 대부분의 산술 논리 장치(ALU) 하드웨어에서 발견되는 더 빠른 고정 소수점 연산과 대조된다.
여러 최신 프로그래밍 언어는 큰 수에 대한 내장 지원을 제공하며,[1][2][3][4] 다른 언어는 임의 정밀도 정수형 및 부동소수점 연산을 위한 라이브러리를 사용할 수 있다. 이 구현들은 프로세서 레지스터 크기와 관련된 고정된 비트 수로 값을 저장하는 대신, 일반적으로 가변 길이 배열의 자릿수를 사용한다.
임의 정밀도는 산술 속도가 제한 요소가 아니거나 매우 큰 수에 대한 정확한 결과가 필요한 응용 분야에 사용된다. 이는 많은 컴퓨터 대수학 시스템에서 제공하는 심볼릭 연산과 혼동해서는 안 된다. 심볼릭 연산은 π·sin(2)와 같은 표현식으로 숫자를 나타내며, 따라서 무한 정밀도로 모든 계산 가능한 수를 나타낼 수 있다.
응용 분야
[편집]일반적인 응용 분야는 공개 키 암호 방식이며, 그 알고리즘은 일반적으로 수백 자리의 정수 연산을 사용한다.[5][6] 또 다른 분야는 인위적인 한계와 오버플로가 부적절한 상황이다. 또한 고정 정밀도 계산 결과를 확인하고, 예를 들어 가우스 적분에 나타나는 와 같은 공식에 필요한 계수의 최적 또는 거의 최적의 값을 결정하는 데 유용하다.[7]
임의 정밀도 연산은 π과 같은 기본 수학 상수를 수백만 자리 이상으로 계산하고 자릿수 문자열의 특성을 분석하거나[8] 더 일반적으로 특정 질문을 분석적 방법으로 탐색하기 어려운 리만 제타 함수와 같은 함수의 정확한 동작을 조사하는 데에도 사용된다. 또 다른 예는 망델브로 집합에서 볼 수 있는 것과 같이 극도로 높은 확대율로 프랙탈 이미지를 렌더링하는 경우이다.
임의 정밀도 연산은 고정 정밀도 연산의 본질적인 한계인 오버플로를 피하는 데에도 사용될 수 있다. 자동차의 오도미터 디스플레이가 99999에서 00000으로 바뀌는 것과 유사하게, 숫자가 너무 커서 고정된 정밀도 수준에서 표현할 수 없을 때 고정 정밀도 정수는 오버플로를 나타낼 수 있다. 일부 프로세서는 대신 포화를 통해 오버플로를 처리할 수 있다. 이는 결과가 표현할 수 없는 경우, 가장 가까운 표현 가능한 값으로 대체됨을 의미한다. (16비트 부호 없는 포화 연산에서는 65535에 양수 값을 더하면 65535가 된다.) 일부 프로세서는 산술 결과가 사용 가능한 정밀도를 초과할 경우 예외를 생성할 수 있다. 필요한 경우 예외를 포착하고 복구할 수 있다. 예를 들어, 임의 정밀도 연산을 사용하여 소프트웨어에서 연산을 다시 시작할 수 있다.
많은 경우, 태스크 또는 프로그래머는 특정 응용 프로그램의 정수 값이 오버플로를 일으킬 만큼 커지지 않을 것임을 보장할 수 있다. 이러한 보장은 실용적인 한계에 기반할 수 있다: 학교 출석 프로그램은 4,000명의 학생이라는 태스크 한계를 가질 수 있다. 프로그래머는 중간 결과가 지정된 정밀도 경계 내에 유지되도록 계산을 설계할 수 있다.
리스프, 파이썬, 펄, 하스켈, 루비, 라쿠와 같은 일부 프로그래밍 언어는 모든 정수 연산에 임의 정밀도 숫자를 사용하거나 사용할 수 있는 옵션이 있다. 이를 통해 정수는 시스템의 가용 메모리에 의해서만 제한되는 어떤 크기로든 커질 수 있다. 비록 이것이 성능을 저하시키지만, 단순한 오버플로로 인한 잘못된 결과(또는 예외)에 대한 우려를 없애준다. 또한 특정 시스템의 워드 크기에 관계없이 모든 기계에서 산술 결과가 동일함을 거의 보장할 수 있게 한다. 프로그래밍 언어에서 임의 정밀도 숫자만을 독점적으로 사용하는 것은 언어를 단순화시키는데, 숫자는 숫자이며 다른 정밀도 수준을 나타내기 위해 여러 유형이 필요 없기 때문이다.
구현 문제
[편집]임의 정밀도 연산은 프로세서 레지스터에 완전히 맞는 숫자를 사용하는 연산보다 훨씬 느리다. 후자는 일반적으로 하드웨어 산술로 구현되는 반면, 전자는 소프트웨어로 구현되어야 하기 때문이다. 컴퓨터에 특정 연산(정수 나눗셈 또는 모든 부동 소수점 연산 등)을 위한 하드웨어가 부족하고 대신 소프트웨어가 제공되더라도, 이는 사용 가능한 하드웨어 레지스터와 밀접하게 관련된 숫자 크기, 즉 한두 워드만 사용한다. 1950년대와 1960년대의 특정 가변 워드 길이 컴퓨터들, 특히 IBM 1620, IBM 1401 및 하니웰 200 시리즈는 값의 경계를 나타내는 추가 비트와 함께 사용 가능한 저장 공간에 의해서만 제한되는 숫자를 조작할 수 있었다는 예외가 있다.
숫자는 고정 소수점 형식 또는 부동소수점 형식으로 임의의 지수를 곱한 유효 숫자로 저장될 수 있다. 그러나 나눗셈은 거의 즉시 무한 반복 자릿수 시퀀스(예: 십진법에서 4/7, 이진법에서 1/10)를 도입하므로, 이러한 가능성이 발생하면 표현이 만족스러운 크기에서 잘리거나 유리수가 사용된다. 즉, 분자와 분모에 큰 정수를 사용한다. 그러나 최대 공약수를 제거하더라도 유리수 연산은 매우 빠르게 다루기 어려워질 수 있다. 1/99 − 1/100 = 1/9900이고, 1/101을 더하면 결과는 10001/999900이다.
임의 정밀도 숫자의 크기는 실제로 사용 가능한 총 저장 공간과 계산 시간에 의해 제한된다.
임의 정밀도로 저장된 숫자에 대한 산술 연산을 효율적으로 수행하기 위해 수많은 알고리즘이 개발되었다. 특히 N 자릿수가 사용된다고 가정할 때, 큰 N에 대한 점근 복잡도를 최소화하기 위한 알고리즘이 설계되었다.
가장 간단한 알고리즘은 덧셈과 뺄셈이며, 여기서는 단순히 자릿수를 순서대로 더하거나 빼고 필요에 따라 올림수를 처리하여 O(N) 알고리즘( 점근 표기법 참조)을 산출한다.
비교 또한 매우 간단하다. 차이가 발견될 때까지 상위 자릿수(또는 기계어 단어)를 비교한다. 나머지 자릿수/단어를 비교할 필요는 없다. 최악의 경우는 (N)이지만, 유사한 크기의 피연산자로 훨씬 더 빨리 완료될 수 있다.
곱셈의 경우, 손으로 숫자를 곱하는 데 사용되는 가장 간단한 알고리즘(초등학교에서 가르치는 대로)은 (N2) 연산이 필요하지만, 곱셈 알고리즘은 고속 푸리에 변환에 기반한 쇤하게-슈트라센 알고리즘과 같이 O(N log(N) log(log(N))) 복잡도를 달성하는 알고리즘이 고안되었으며, 약간 더 나쁜 복잡도를 가지지만 더 작은 N에 대해 때로는 뛰어난 실제 성능을 보이는 알고리즘도 있다. 카라추바 알고리즘 곱셈이 그러한 알고리즘이다.
복잡도 추정치와 함께 알고리즘 목록은 수학 연산의 계산 복잡도를 참조하라.
사전 설정 정밀도
[편집]REXX 및 ooRexx와 같은 일부 언어에서는 계산을 수행하기 전에 모든 계산의 정밀도를 설정해야 한다. 파이썬 및 루비와 같은 다른 언어는 오버플로를 방지하기 위해 자동으로 정밀도를 확장한다.
예시
[편집]계승 계산은 매우 큰 숫자를 쉽게 생성할 수 있다. 이는 많은 공식(테일러 급수 등)에서 사용되는 데 문제가 되지 않는다. 왜냐하면 다른 항과 함께 나타나기 때문에, 평가 순서에 주의를 기울이면 중간 계산 값이 문제가 되지 않기 때문이다. 계승 값의 근사치가 필요한 경우 스털링 근사는 부동 소수점 연산을 사용하여 좋은 결과를 제공한다. 고정 크기 정수 변수의 가장 큰 표현 가능한 값은 아래 표에 나타난 것처럼 상대적으로 작은 인수에서도 초과될 수 있다. 부동 소수점 숫자도 곧 범위를 벗어나므로, 계산을 숫자의 로그로 다시 캐스팅하는 것이 도움이 될 수 있다.
그러나 큰 계승에 대한 정확한 값이 필요한 경우, 다음의 의사코드와 같이 특수 소프트웨어가 필요하다. 이 코드는 연속적인 계승 값인 1, 1×2, 1×2×3, 1×2×3×4 등을 계산하는 고전적인 알고리즘을 구현한다.
```
상수: Limit = 1000 % 충분한 자릿수. Base = 10 % 시뮬레이션된 연산의 기수. FactorialLimit = 365 % 해결할 목표 숫자, 365! tdigit: Array[0:9] of character = ["0","1","2","3","4","5","6","7","8","9"]
변수: digit: Array[1:Limit] of 0..9 % 큰 숫자. carry, d: Integer % 곱셈 중 보조 변수. last: Integer % 큰 숫자의 자릿수 인덱스. text: Array[1:Limit] of character % 출력을 위한 임시 공간.
digit[*] := 0 % 배열 전체를 지운다. last := 1 % 큰 숫자는 한 자릿수부터 시작하며, digit[1] := 1 % 유일한 자릿수는 1이다.
for n := 1 to FactorialLimit: % 1!, 2!, 3!, 4! 등을 순차적으로 생성한다.
carry := 0 % n을 곱하기 시작한다.
for i := 1 to last: % 모든 자릿수를 따라간다.
d := digit[i] * n + carry % 한 자릿수를 곱한다.
digit[i] := d mod Base % 결과의 하위 자릿수를 유지한다.
carry := d div Base % 다음 자릿수로 올림수를 전달한다.
while carry > 0: % 남은 올림수를 큰 숫자에 저장한다.
if last >= Limit: error("overflow")
last := last + 1 % 한 자릿수 추가.
digit[last] := carry mod Base
carry := carry div Base % 올림수에서 마지막 자릿수를 제거한다.
text[*] := " " % 이제 출력을 준비한다.
for i := 1 to last: % 이진수에서 텍스트로 변환한다.
text[Limit - i + 1] := tdigit[digit[i]] % 순서를 뒤집는다.
print text[Limit - last + 1:Limit], " = ", n, "!"
```
이 예제를 통해 여러 세부 사항을 논의할 수 있다. 가장 중요한 것은 큰 수 표현 방식의 선택이다. 이 경우, 자릿수에 정수 값만 필요하므로 고정 너비 정수 배열이 적절하다. 배열의 연속적인 요소가 기수의 더 높은 거듭제곱을 나타내도록 하는 것이 편리하다.
두 번째로 중요한 결정은 산술의 기수(여기서는 10)를 선택하는 것이다. 고려해야 할 사항이 많다. 스크래치패드 변수 d는 한 자릿수 곱셈의 결과와 이전 자릿수 곱셈의 올림수를 합한 값을 담을 수 있어야 한다. 10진법에서는 16비트 정수가 32767까지 허용하므로 확실히 적절하다. 그러나 이 예제는 n의 값이 한 자릿수로 제한되지 않는다는 점에서 속임수를 썼다. 이는 n > 3200 정도에서는 이 방법이 실패할 것이라는 결과를 초래한다. 더 일반적인 구현에서는 n도 여러 자릿수 표현을 사용한다. 지름길의 두 번째 결과는 여러 자릿수 곱셈이 완료된 후, 올림수의 마지막 값이 단일 자릿수가 아니라 여러 상위 자릿수로 전달되어야 할 수 있다는 것이다.
사람의 고려를 위해 결과를 10진수로 인쇄하는 문제도 있다. 기수가 이미 10이므로 배열 `digit`의 연속적인 자릿수를 인쇄하여 결과를 간단하게 표시할 수 있지만, 가장 높은 자릿수가 마지막에 나타난다(예: 123이 "321"로 나타남). 배열 전체를 역순으로 인쇄할 수 있지만, 이는 선행 0("00000...000123")이 있는 숫자를 표시하여 불쾌감을 줄 수 있으므로 이 구현은 공백으로 채워진 텍스트 변수에 표현을 만들고 이를 인쇄한다. 처음 몇 가지 결과(5자리마다 공백을 추가하고 주석을 달았다)는 다음과 같다.
| 계승 값 | 컴퓨터 정수의 도달 범위 | ||
|---|---|---|---|
| 1 = | 1! | ||
| 2 = | 2! | ||
| 6 = | 3! | ||
| 24 = | 4! | ||
| 120 = | 5! | 8-bit | 255 |
| 720 = | 6! | ||
| 5040 = | 7! | ||
| 40320 = | 8! | 16-bit | 65535 |
| 3 62880 = | 9! | ||
| 36 28800 = | 10! | ||
| 399 16800 = | 11! | ||
| 4790 01600 = | 12! | 32-bit | 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-bit | 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-bit | 3402 82366 92093 84634 63374 60743 17682 11455 |
| 1 03331 47966 38614 49296 66651 33752 32000 00000 = | 35! | ||
이 구현은 컴퓨터에 내장된 연산을 더 효율적으로 사용할 수 있다. 간단한 확장은 기수를 100으로 사용하는 것(출력 번역 과정에서 해당 변경 사항 적용)이거나, 충분히 넓은 컴퓨터 변수(예: 32비트 정수)가 있다면 10,000과 같은 더 큰 기수를 사용할 수 있다. 컴퓨터의 내장 정수 연산에 가까운 2의 거듭제곱 기수에서 작업하는 것이 유리하지만, 출력을 위한 십진법으로의 변환은 더 어려워진다. 일반적인 최신 컴퓨터에서는 덧셈과 곱셈이 피연산자의 값과 무관하게(피연산자가 단일 기계어 단어에 들어맞는 한) 일정한 시간이 걸리므로, 자릿수 배열의 각 요소에 가능한 한 많은 큰 숫자를 패킹하는 데 큰 이점이 있다. 컴퓨터는 또한 예제와 같이 나머지 연산과 나눗셈 연산을 두 번 수행할 필요 없이 곱셈 결과를 자릿수와 올림수로 분리하는 기능을 제공할 수 있으며, 거의 모든 산술 장치는 다중 정밀도 덧셈 및 뺄셈에 활용될 수 있는 올림수 플래그를 제공한다. 이러한 세부 사항은 기계어 코드 프로그래머의 주된 관심사이며, 적절한 어셈블리 언어 큰 숫자 루틴은 이러한 기능에 직접 접근할 수 없고 고수준 문장을 최적화 컴파일러를 사용하여 대상 기계의 모델에 매핑하는 고수준 언어 컴파일 결과보다 빠르게 실행될 수 있다.
한 자릿수 곱셈의 경우 작업 변수는 (기수−1)2 + 올림수 값을 담을 수 있어야 하며, 여기서 올림수의 최대값은 (기수−1)이다. 마찬가지로, 자릿수 배열을 인덱싱하는 데 사용되는 변수 자체도 너비가 제한된다. 인덱스를 확장하는 간단한 방법은 큰 숫자의 자릿수를 편리한 크기의 블록으로 처리하여 주소 지정이 (블록 i, 자릿수 j)와 같이 이루어지도록 하는 것이다. 여기서 i와 j는 작은 정수이거나, 인덱싱 변수에 큰 숫자 기술을 적용할 수도 있다. 궁극적으로, 기계 저장 용량과 실행 시간은 문제 크기에 제약을 가한다.
역사
[편집]IBM의 최초 비즈니스 컴퓨터인 1950년대 중반의 진공관 기계인 IBM 702는 1자리에서 511자리까지 모든 길이의 자릿수 문자열에 대해 정수 연산을 완전히 하드웨어로 구현했다. 임의 정밀도 연산의 가장 초기에 널리 사용된 소프트웨어 구현은 아마도 맥리스프에 있었을 것이다. 이후 1980년경, VAX/VMS 및 VM/CMS 운영체제는 한 경우에는 문자열 함수 모음으로, 다른 경우에는 EXEC 2 및 REXX 언어로 큰 수 기능을 제공했다.
초기 널리 퍼진 구현은 1959년부터 1970년까지의 IBM 1620을 통해 가능했다. 1620은 이산 트랜지스터를 사용한 십진 숫자 기계였지만, 두 자리부터 사용 가능한 메모리만큼의 길이까지의 자릿수 문자열에 대해 정수 연산을 수행하는 하드웨어(순람표 사용)를 가지고 있었다. 부동 소수점 연산의 경우, 가수부는 100자리 이하로 제한되었고, 지수부는 두 자리로만 제한되었다. 공급된 가장 큰 메모리는 60,000자리를 제공했지만, 1620용 포트란 컴파일러는 기본값이 만족스럽지 않은 경우 제어 카드에서 지정할 수 있었지만 10자리와 같은 고정된 크기를 사용했다.
소프트웨어 라이브러리
[편집]
임의 정밀도 연산 소프트웨어 목록 문서를 참고하십시오.대부분의 컴퓨터 소프트웨어에서 임의 정밀도 연산은 요청된 정밀도로 숫자를 저장하고 계산을 수행하는 자료형 및 서브루틴을 제공하는 외부 라이브러리를 호출하여 구현된다.
다양한 라이브러리는 임의 정밀도 숫자를 나타내는 방식이 다르며, 일부 라이브러리는 정수 숫자만 사용하고, 다른 라이브러리는 다양한 기수(10진수 또는 2진수 거듭제곱)로 부동소수점 숫자를 저장한다. 일부 라이브러리는 숫자를 단일 값으로 표현하는 대신 분자/분모 쌍(유리수)으로 저장하며, 일부는 계산 가능한 수를 완전히 표현할 수 있지만, 이는 저장 한도까지이다. 근본적으로 튜링 기계는 모든 실수를 표현할 수 없다. 의 크기가 의 크기를 초과하기 때문이다.
같이 보기
[편집]각주
[편집]- ↑ dotnet-bot. “BigInteger Struct (System.Numerics)”. 《docs.microsoft.com》 (미국 영어). 2022년 2월 22일에 확인함.
- ↑ “PEP 237 -- Unifying Long Integers and Integers”. 《Python.org》 (영어). 2022년 5월 23일에 확인함.
- ↑ “BigInteger (Java Platform SE 7 )”. 《docs.oracle.com》. 2022년 2월 22일에 확인함.
- ↑ “BigInt - JavaScript | MDN”. 《developer.mozilla.org》 (미국 영어). 2022년 2월 22일에 확인함.
- ↑ Jacqui Cheng (2007년 5월 23일). “Researchers: 307-digit key crack endangers 1024-bit RSA”.
- ↑ “RSA Laboratories - 3.1.5 How large a key should be used in the RSA cryptosystem?”. 2012년 4월 1일에 원본 문서에서 보존된 문서. 2012년 3월 31일에 확인함. recommends important RSA keys be 2048 bits (roughly 600 digits).
- ↑ Laurent Fousse (2006). Intégration numérique avec erreur bornée en précision arbitraire. Modélisation et simulation (보고서) (프랑스어). Université Henri Poincaré - Nancy I.
- ↑ R. K. Pathria (1962). 《A Statistical Study of the Randomness Among the First 10,000 Digits of Pi》. 《Mathematics of Computation》 16. 188–197쪽. doi:10.1090/s0025-5718-1962-0144443-7. 2014년 1월 10일에 확인함. A quote example from this article: "Such an extreme pattern is dangerous even if diluted by one of its neighbouring blocks"; this was the occurrence of the sequence 77 twenty-eight times in one block of a thousand digits.
더 읽어보기
[편집]- Knuth, Donald (2008). 《Seminumerical Algorithms》. 컴퓨터 프로그래밍의 예술 2 3판. Addison-Wesley. ISBN 978-0-201-89684-8., Section 4.3.1: The Classical Algorithms
- 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., Chapter 9: Fast Algorithms for Large-Integer Arithmetic
외부 링크
[편집]- 랜들 하이드의 The Art of Assembly 9.3장에서는 다중 정밀도 연산을 X86 어셈블리 예제와 함께 다룬다.
- 로제타 코드 작업 임의 정밀도 정수 95개 이상의 프로그래밍 언어가 임의 정밀도 연산을 사용하여 5**4**3**2 값을 계산하는 방식에 대한 사례 연구.