이진 분할

수학에서 이항분할은 이성적인 용어로 여러 종류의 시리즈에 대한 수치평가를 빠르게 하는 기법이다.특히 합리적인 지점에서 초기하계열 평가에 활용할 수 있다.

방법

연속 영상 시리즈

${\displaystyle S(a,b)=\sum _{n=a}^{b}{\frac {p_{n}}{q_{n}}}}}}}$

여기서 p와_n q가_n 정수인 경우, 이진 분할의 목적은 다음과 같이 정수 P(a, b)와 Q(a, b)를 계산하는 것이다.

${\displaystyle S(a,b)={\frac {P(a,b)}{Q(a,b)}}.}$

분할은 m = [(a + b)/2]를 설정하고 P(a, m), P(m, b), Q(a, b)에서 P(a, b)와 Q(a, b)를 재귀적으로 계산한다.a와 b가 충분히 가까워지면 p_a...p와_b q_a...q에서_b 직접 P(a, b)와 Q(a, b)를 계산할 수 있다.

다른 방법과의 비교

바이너리 분할은 기간별 직접 합계보다 더 많은 메모리를 필요로 하지만 모든 발생 하위 제품의 크기가 감소하기 때문에 무증상적으로 더 빠르다.또한 합리적인 시리즈에 대한 가장 순진한 평가방식은 시리즈의 각 용어에 대해 완전정밀분할을 사용하는 반면, 이진 분할은 목표 정밀도에서 하나의 최종분할만을 필요로 한다. 이것은 더 빠를 뿐만 아니라 라운딩 오류를 제거하기 편리하다.이 방법을 최대한 활용하려면 Toom-Cook 및 Schönagage-Strassen과 같은 빠른 곱셈 알고리즘을 사용해야 한다. 일반적인 O(n²) 곱셈을 사용하는 경우, 이진 분할은 속도를 전혀 증가시키지 않거나 느리게 할 수 있다.

시리즈의 모든 세분화는 서로 독립적으로 계산될 수 있기 때문에, 이진 분할은 병렬화와 체크포인트에 도움이 된다.

덜 구체적인 의미에서, 이진 분할은 또한 문제를 항상 두 부분으로 나누는 분할과 정복 알고리즘을 가리킬 수도 있다.

참조

• 사비에르 구르돈 & 파스칼 세바.이항분할법
• 데이비드 5세추드노브스키 & 그레고리 5세추드노브스키.수학적 물리학과 숫자 이론의 서비스에서의 컴퓨터 대수학.컴퓨터 및 수학(Stanford, CA, 1986), 페이지 09–232, Dekker, New York, 1990.
• 브루노 하이블, 토마스 파파니콜라우.일련의 합리적인 숫자에 대한 빠른 다중 비교 평가.CLN 라이브러리 소스 코드를 사용하여 배포된 용지.
• 로지에, D.W.와 올버, F.W.J.수치특수평가연산수학 1943-1993: 연산수학 반세기, W.고츠치, 에드, 프락심포즈.응용 수학, AMS, v.48, 페이지 79–125(1994)
• 바흐, E.숫자-이론적 상수의 복잡성.정보, 프로크글자, N 62, 페이지 145–152 (1997년)
• Borwein, J.M., Bradley, D.M. 및 Crandall, R.E. Computing strategies for Riemann zeta 함수에 대한 연산 전략.컴퓨팅의 J.Appl. 수학, v.121, N 1-2, 페이지 247–296(2000)
• 카라츠바, E.A. 초월함수의 빠른 평가 (영어)러시아 원문) 프로블.inf. transform.27, 4번, 339-360(1991); Probl로부터의 번역.페레다치 inf. 27번, 4번, 76–99 (1991년).
• 에카테리나 가라쓰바.빠른 알고리즘과 FEE 방법