프로그래밍 언어가 거대한 숫자 산술을 처리하는 방법

Question

64 비트 프로세서로 작동하는 컴퓨터의 경우 처리 할 수있는 최대 숫자는 2 = 18,446,744,073,709,551,616입니다. Java 또는 C, C++ 프로그래밍 언어는이 값보다 큰 숫자의 산술을 어떻게 처리합니까? 모든 레지스터는 단일 피스로 보유 할 수 없습니다. 이 문제는 어떻게 다루어 졌습니까?

Answer 1

일반적으로 언어 자체는 고정밀, 고정밀 다수 수 계산을 처리하지 않습니다. 라이브러리이 대체 연산 방법을 사용하여 원하는 작업을 수행 할 가능성이 훨씬 높습니다.

예를 들어 (저는 지금 당장 이것을 작성하고 있습니다), 그러한 라이브러리는 수작업으로 많은 수의 산술을 수행하는 데 사용할 수있는 실제 기술을 에뮬레이트 할 수 있습니다. 이러한 라이브러리는 일반적으로 기본 제공 산술을 사용하는 것보다 느리며 이지만 추가 정밀도와 정확성이 요구되는 경우가 있습니다.

Answer 2

잘못된 것으로 가정합니다. 하나의 레지스터에 을 처리 할 수있는 가장 큰 숫자는이며 64 비트입니다. 그러나 일부 스마트 프로그래밍 기술을 사용하면 수십 개의 64 비트 숫자를 연속적으로 결합하여 거대한 6400 비트 숫자를 생성하고 더 많은 계산을 수행 할 수 있습니다. 하나의 레지스터에 숫자를 넣는 것만 큼 빠르지는 않습니다.

심지어 이전의 8 및 16 비트 프로세서도이 트릭을 사용하여 번호가 다른 레지스터로 넘치도록했습니다. 그것은 수학을 더욱 복잡하게 만들지 만 가능성을 끝내지는 못합니다.

그러나 이러한 고정밀 수학은 매우 드뭅니다. 미국의 전체 국가 부채를 계산하고 짐바브웨 달러로 결과를 저장하려는 경우에도 64 비트 정수는 여전히 충분히 크다고 생각합니다. 그것은 저의 예금 계좌의 금액을 포함 할만큼 충분히 큽니다.

Answer 3

생각한 실험으로 숫자를 문자열로 저장한다고 상상해보십시오. 이 임의의 긴 숫자를 추가, 곱하기 등의 기능이 있습니다.

실제로 이러한 숫자는 더 효율적인 공간 방식으로 저장됩니다.

Answer 4

하나의 기계 크기의 숫자를 숫자로 생각하고 초등 학교에서 여러 자리 곱하기 알고리즘을 적용하십시오. 그런 다음 전체 수를 레지스터에 보관할 필요가 없습니다. 숫자는 레지스터에 그대로 유지됩니다.

Answer 5

레지스터 크기보다 큰 숫자에 대한 계산을 수행하는 데는 많은 전문 기술이 있습니다. 이 중 일부는이 위키 피 디아의 문서에 설명되어 있습니다.

C 및 C++과 같은 저급 언어는 원하는 라이브러리에 많은 계산을 남깁니다. 주목할만한 하나는 GNU Multi-Precision library입니다. Python과 같은 고급 언어와 다른 언어는 이것을 언어 핵심으로 통합하므로 일반 숫자와 매우 큰 숫자는 프로그래머와 동일합니다.

Answer 6

대부분의 언어는 정수 배열로 저장합니다. 이 큰 숫자에 2를 더하거나 빼면 라이브러리는 배열의 모든 정수 요소를 별도로 추가/제거하고 carry/borrow를 처리합니다. 내부적으로 작동하는 방식이므로 학교에서 수동으로 추가/제거하는 것과 같습니다.

일부 언어는 정수 배열 대신 실제 텍스트 문자열을 사용합니다. 정수 배열은 덜 효율적이지만 텍스트 표현으로 변환하는 것이 더 간단합니다.

Answer 7

실제로 Ada는 유형이없는 상수 ("명명 된 숫자")에 대해서만 기본적으로이를 지원합니다. 실제 변수의 경우, 임의의 길이의 패키지를 찾아야합니다. Arbitrary length integer in Ada

Answer 8

더 많거나 적음 과 동일합니다. 학교에서는 한자리 추가, 곱셈, 뺄셈 및 나누기를 기억했습니다. 그런 다음 여러 자릿수 문제를 일련의 한 자릿수 문제로 수행하는 방법을 배웠습니다.

원하는 경우 간단한 알고리즘에 대한 지식과 한자리 수 시간 테이블을 사용하여 두 개의 20 자리 숫자를 곱할 수 있습니다.

Answer 9

엄청난 숫자를 처리하는 프로그래밍 언어는 32, 64 또는 128 비트 CPU에 최적화 된 정상적인 작업을 능가하는 사용자 정의 숫자 기본 요소를 사용합니다. 이 숫자는 특히 컴퓨터 보안 및 수학 연구에 유용합니다.

GNU Multiple Precision Library은 아마도 이러한 접근 방식 중 가장 완벽한 예일 것입니다.

배열을 사용하여 더 큰 숫자를 처리 할 수 ​​있습니다. 웹 브라우저에서이 기능을 사용해보십시오. 웹 브라우저의 자바 스크립트 콘솔에서 다음 코드를 입력 : 자바 스크립트

console.log(9999999999999998 + 1) 
// expected 9999999999999999 
// actual 10000000000000000 oops! 

자바 스크립트 9999999999999998 위의 일반 정수를 처리하지 않습니다 실패

점하는. 그러나 자신의 수를 작성하는 것은이 계산 작업을 충분히 간단하게 만드는 것입니다. 다음은 a custom number adder class in JavaScript을 사용한 예입니다. 사용자 지정 숫자 클래스는

당신은 무슨 일이 일어나고 있는지의 세부 정보를 볼 수 class Num { ... }에 코드에서 볼 수 작동 방법

// Require a custom number primative class 
const {Num} = require('./bases') 

// Create a massive number that JavaScript will not add to (correctly) 
const num = new Num(9999999999999998, 10) 

// Add to the massive number 
num.add(1) 

// The result is correct (where plain JavaScript Math would fail) 
console.log(num.val) // 9999999999999999 

를 사용하여 테스트를 통과

;

클래스 :

• 는 Num 클래스는 단일 Digit 클래스의 배열을 포함하지만 여기에 사용되는 논리의 기본 개요이다.
• Digit 클래스는 단일 숫자 값을 포함하고, 로직은 Carry flag

단계를 처리하기 : 선택된 번호 문자열

로 설정되어

1. 각 디지트가 켜져 Digit 클래스로 변환되어 숫자 배열로 Num 클래스에 저장됩니다.
2. Num이 증가하면, 어레이의 제 Digit (가장 오른쪽의 수) Digit 값 플러스 Carry flag가 Base 동등한 경우
3. O를 그 왼쪽 옆 Digit가 증가 될 불리는, 현재 번호에 리셋되고
4. 0은 ...

는 물류는 기계 수준에서 무슨 일이 일어나고 있는지 매우 유사하다 배열의 왼쪽 가장 자리에있는 모든 방법을 반복하지만, 여기가 억제 할 수 있습니다. 당신은 할 수있다 read more about about how digits are carried here; 이것은 모든베이스의 번호에 적용 할 수 있습니다.