e에서 2조 자리까지 계산하는 가장 빠른 방법은 무엇입니까?
나는 e에서 2조(2,000,000,000)자리를 계산하고 싶습니다.이것은 퓨레 1,8TiB 정도 됩니다.방금 GMP를 이용한 테일러 시리즈 확장 알고리즘을 구현했습니다(코드는 여기서 확인 가능).
유감스럽게도 메모리가 부족해서인지 내 컴퓨터에서 4000개 이상의 용어를 합하면 충돌이 발생합니다.
컴퓨터 e의 현재 기술 상태는 어떻습니까?어떤 알고리즘이 가장 빠릅니까?살펴볼 가치가 있는 오픈 소스 구현이 있습니까?y-cruncher는 언급하지 말아주세요. 비공개 소스입니다.
저는 당신이 언급한 y-cruncher 프로그램의 저자이기 때문에 2센트를 추가하겠습니다.
이처럼 큰 업무를 처리하기 위해 해결해야 하는 가장 큰 두 가지 장벽은 다음과 같습니다.
- 기억
- 런타임 복잡도
기억
2조 자리는 극단적입니다. 별말씀을요.이는 지난 2010년 곤도 시게루 씨와 저 자신이 세운 현재 기록의 두 배입니다. (y-cruncher를 사용하여 1조 자리 수를 계산하는 데 9일 이상이 걸렸습니다.
일반적으로 말하면 십진법으로 약 1.8 TiB입니다.포장된 이진법 표현에서 773 GiB입니다.
이 크기의 숫자를 연산하려면 스크래치 메모리를 세지 않고 각 연산에 대해 773 GiB가 필요합니다.
실현 가능하게 말하자면, y-cruncher는 이 연산을 모두 램으로 수행하기 위해 실제로 8.76 TiB의 메모리가 필요합니다.따라서 다른 구현에서도 동일한 조건을 제공하거나 최대 2배의 요소가 필요할 것으로 예상할 수 있습니다.
그렇다고 램은 충분하지 않을 겁니다NUMA를 많이 사용한다고 해도 디스크를 사용하는 것이 대안입니다.그러나 효율성을 높이기 위해서는 메모리를 캐시로 취급하고 메모리와 디스크 간에 전송되는 모든 데이터를 마이크로 관리해야 하기 때문에 이는 사소한 것이 아닙니다.
런타임 복잡도
여기 또 다른 문제가 있습니다.2조 자리 수의 경우 매우 빠른 알고리즘이 필요합니다.단순한 빠른 알고리즘이 아닌 준선형 런타임 알고리즘.
현재 시도가 실행되는 시점은O(N^2). 그래서 여러분이 충분한 기억력을 가지고 있었다고 해도, 여러분의 일생 동안 그것은 끝나지 않을 것입니다.
컴퓨팅에 대한 표준 접근 방식e정밀도 높은 런 인O(N log(N)^2)다음과 같은 알고리즘을 결합합니다.
- Taylor 영상 시리즈 확장에 대한 이진 분할
e. - FFT 기반 큰 곱셈
다행히도, GMP는 이미 FFT 기반의 큰 곱셈을 사용하고 있습니다.그러나 두 가지 중요한 기능이 부족합니다.
- 메모리가 충분하지 않을 때 디스크를 사용하기 위한 핵심 외(swap) 계산.
- 평행선이 아닙니다.
두 번째 포인트는 더 오래 기다리면 되기 때문에 중요하지 않습니다.하지만 모든 실용적인 목적을 위해서는, 당신은 아마 당신 자신의 것을 출시해야 할 것입니다.제가 y-cruncher를 쓸 때도 그랬습니다.
그 외에도 다음과 같이 처리해야 할 여러 가지 느슨한 부분이 있습니다.
- 마지막 분할에는 뉴턴의 방법과 같은 빠른 알고리즘이 필요할 것입니다.
- 이진법으로 계산하려면 래딕스 변환을 해야 합니다
- 계산에 많은 시간과 리소스가 소요되는 경우 하드웨어 장애를 처리하기 위해 내결함성을 구현해야 할 수도 있습니다.
(2) 를를 데한 항 할 수 .e그 숫자로 말입니다.이를 통해 2조 번째 자리에서 반올림 오류를 방지하기 위해 필요한 정밀도의 추가 자릿수를 추정할 수 있습니다.
스털링의 근사치에서 계산한 것이 맞다면 10조에서 2조의 역수는 1,000억 개의 계승의 역수에 대한 것입니다.따라서 필요한 조건(1,000억)은 이 정도입니다.하지만 그보다 이야기가 조금 낫습니다. 왜냐하면 그보다 훨씬 이전에 용어 계산에 있는 숫자들을 많이 버릴 수 있기 때문입니다.
부터.e역수의 합으로 계산되며, 모든 항이 유리하므로 반복 소수점으로 표현할 수 있습니다.따라서 용어의 소수 확장은 (a) 지수, (b) 반복되지 않는 부분, (c) 반복되는 부분이 됩니다.이런 식으로 용어를 살펴보면 몇 가지 효율성을 활용할 수 있습니다.
아무튼 행운을 빌어요!
언급URL : https://stackoverflow.com/questions/13313933/what-is-the-fastest-way-to-calculate-e-to-2-trillion-digits
'programing' 카테고리의 다른 글
| AWS KMS 플러그인을 통한 정지 상태의 MariaDB Encryption - Key Rotation이 작동하지 않습니까? (0) | 2023.10.01 |
|---|---|
| Excel VBA의 동적 함수 호출 (0) | 2023.10.01 |
| jQuery를 사용하여 "삭제" 키 누르기 (0) | 2023.10.01 |
| 도커 이미지 컨텐츠를 보는 방법 (0) | 2023.10.01 |
| jQuery를 사용하여 '어떤' ajax 요청이 완료되는지 탐지하려면 어떻게 해야 합니까? (0) | 2023.10.01 |