이진 GCD 알고리즘

Binary GCD algorithm
바이너리 GCD 알고리즘을 사용하여 36과 24의 최대 공통 디비저(GCD)를 찾는 시각화. 따라서 GCD는 22 × 3 = 12이다.

2진수 GCD 알고리즘은 스타인의 알고리즘 또는 2진수 유클리드 알고리즘으로도 알려져 있으며,[1][2] 두 개의 비음수 정수의 최대 공통점수를 계산하는 알고리즘이다. 스타인의 알고리즘은 기존의 유클리드 알고리즘보다 단순한 산술 연산을 사용한다. 그것은 분열을 산술 이동, 비교, 뺄셈으로 대체한다.

비록 현대의 알고리즘은 1967년 이스라엘의 물리학자 겸 프로그래머인 요제프 스타인에 의해 처음 출판되었지만,[3] 기원전 2세기에 고대 중국에서 알려졌을지도 모른다.[4][5]

알고리즘.

알고리즘은 다음과 같은 ID를 반복적으로 적용함으로써 두 개의 비음수 v와 u의 GCD를 찾는 문제를 줄인다.

  • gcd(0, v) = v, 모든 것이 0을 나누고, v가 v를 나누는 가장 큰 숫자이기 때문이다. 마찬가지로 gcd(u, 0) = u.
  • gcd(2u, 2v) = 2·gcd(u, v)
  • gcd(2u, v) = gcd(u, v), v가 홀수인 경우(2는 공통 구분자가 아님) 마찬가지로 gcd(u, 2v) = gcd(u, v) u가 홀수인 경우 gcd(u, v)이다.
  • gcd(u, v) = gcd(u - v , min(u, v)), u와 v가 모두 홀수인 경우.

실행

위의 알고리즘 설명은 수학적으로 정확하지만, 실행형 소프트웨어 구현은 일반적으로 몇 가지 주목할 만한 방법으로 그것과 다르다.

  • 단일 비트시프트와 0을 원시 비트시프트에 유리한 2의 시험 분할을 방지한다. 이는 기능상으로는 ID 3을 반복적으로 적용하는 것과 동일하지만 훨씬 빠르다.
  • 알고리즘을 반복적으로 표현하기 보다는 반복적으로 표현: 반복적인 작업을 피하기 위해 구현을 할 수 있으며, 시작 시 ID 2를 호출하고, ID 3과 4만 구현하면 되는 루프로 들어갈 때 두 숫자가 홀수라는 불변으로 유지된다.
  • 루프의 몸통을 출구 조건(v == 0)을 제외하고 분기가 없는 상태로 만들기: 아래 예에서 u와 v의 교환은 조건부 움직임으로 압축된다;[6] 고정하기 어려운 분기는 성능에 크고 부정적인 영향을 미칠 수 있다.[7][8]

다음은 그러한 차이를 예시하는 러스트 알고리즘의 구현으로, 유틸에서 채택되었다. 

펍;gcd(mut u:u64,mut v:u64)-> fn u64{사용 std::cmp::분, 사용 std::멤::스왑;//기지 사례:gcd(n, 0))gcd(0, n))n만약 == 0{반환 v;} 다른 만약 v== 0{반환 u.}을 끓여를 사용하여 정체성 2,3:// 이gcd(2ⁱ u, 2ʲ v))2ᵏ gcd(u, v)와 u, v홀수 및 k=min(나는, j)을 끓여2ᵏ 가장 큰 권력의 둘은 구분되고 둘 다 너 그리고 v.t나는)u.trailing_zeros()입니다;>>)거야. j)v.trailing_zeros(), v><>)j, k=min(나는, j), 루프{//너 그리고 v루프 debug_assert을 시작할 때!(u%2== 1,"u={}를 넘어서",마);debug_assert!(v%2== 1,"v={}를 넘어서", v);스왑 필요하다면 그렇게 아냐<>//^'v'만약>v{swap(&mut u,&mut v)이상하다는 말.}을 끓여사용 iden.Tity 4(gcd(u, v))gcd(.v-u , min(u, v))  v -= u;  // Identity 1: gcd(u, 0) = u  // The shift by k is necessary to add back the 2ᵏ factor that was removed before the loop  if v == 0 {  return u << k;  }  // Identity 3: gcd(u, 2ʲ v) = gcd(u, v) (u has not changed since the beginning of the loop, so it is still known to be odd)  v >>= v.trailing_zeros();  } }

효율성

알고리즘에는 O(n) 스텝이 필요하며, 여기서 n은 두 단계 중 큰 숫자의 비트 수입니다. 매 2단계마다 피연산자 중 적어도 1개의 인수가 2가 감소하기 때문이다. 각 단계에는 몇 개의 산술 연산(O(1)이 작은 상수를 가지고 있음)만 필요하다. 각 산술 연산은 단 하나의 기계 연산을 의미하므로 기계 연산의 수는 log log(max(u, v)), 즉 n.

그러나 이 알고리즘의 점근법은 산술 연산(추상 및 시프트)이 각각 임의 크기의 숫자(표현 단어당 기계 연산 1개)에 대해 선형 시간을 갖기 때문에 O(n2)이다.[9] 이것은 유클리드 알고리즘과 동일하지만, Akhavi와 Vallée의 보다 정밀한 분석은 바이너리 GCD가 약 60%의 비트 연산을 사용하는 것을 증명했다.[10]

확장

이진 GCD 알고리즘은 추가 정보를 출력하거나, 임의로 큰 정수를 보다 효율적으로 다루거나, 정수가 아닌 도메인에서 GCD를 계산하기 위해 여러 가지 방법으로 확장할 수 있다.

확장형 바이너리 GCD 알고리즘은 확장형 유클리드 알고리즘과 유사하게 첫 번째 종류의 확장에 적합하며, 이는 GCD 외에 Bézout 계수(즉, a/u + b/v = gcd(u, v)와 같은 정수 a와 b를 제공하기 때문이다.[11][12][13]

큰 정수의 경우, 가장 좋은 점근 복잡성은 O(log n M(n)이며, N(n)의 n비트 곱셈 비용이다. 이는 거의 선형에 가깝고, 2진수 GCD 알고리즘의 O(n2)보다 훨씬 작다. 구체적인 구현은 약 64킬로비트(예: 8×1019265 이상)보다 더 큰 숫자에 대한 기존 알고리즘을 능가할 뿐이다. 이것은 빠른 정수 곱셈을 위한 Schönagage-Strassen 알고리즘의 아이디어를 이용하여 이진 GCD 알고리즘을 확장함으로써 달성된다.[14]

2진수 GCD 알고리즘도 가우스 정수, 아이젠슈타인 정수,[15][16] 2차 링,[17][18][19] 임의 고유 인수 도메인 등 자연수 이외의 영역으로 확장되었다.

과거설명

고대 중국 한나라 시대에는 분수를 줄이기 위한 방법으로 두 개의 숫자의 GCD를 계산하는 알고리즘이 알려져 있었다.

가능하면 반감하고, 그렇지 않으면 분모와 분자를 취하여 큰 것 중에서 작은 것을 뺀 다음, 같은 것을 만들기 위해 교대로 한다. 같은 수만큼 줄인다.

— Fangtian - Land surveying, The Nine Chapters on the Mathematical Art

"만약 가능하다면 절반으로 줄 수 있다"는 문구가 애매모호하다.[4][5]

  • 두 숫자 중 하나가 짝수가 되었을 때 이 방법이 적용되는 경우, 알고리즘은 이진 GCD 알고리즘이다.
  • 두 숫자가 짝수일 때만 적용되는 경우, 알고리즘은 유클리드 알고리즘과 유사하다.

참고 항목

참조

  1. ^ Brent, Richard P. (13–15 September 1999). Twenty years' analysis of the Binary Euclidean Algorithm. 1999 Oxford-Microsoft Symposium in honour of Professor Sir Antony Hoare. Oxford.
  2. ^ Brent, Richard P. (November 1999). Further analysis of the Binary Euclidean algorithm (Technical report). Oxford University Computing Laboratory. arXiv:1303.2772. PRG TR-7-99.
  3. ^ Stein, J. (February 1967), "Computational problems associated with Racah algebra", Journal of Computational Physics, 1 (3): 397–405, Bibcode:1967JCoPh...1..397S, doi:10.1016/0021-9991(67)90047-2, ISSN 0021-9991
  4. ^ a b Knuth, Donald (1998), Seminumerical Algorithms, The Art of Computer Programming, vol. 2 (3rd ed.), Addison-Wesley, ISBN 978-0-201-89684-8
  5. ^ a b Zhang, Shaohua (2009-10-05). "The concept of primes and the algorithm for counting the greatest common divisor in Ancient China". arXiv:0910.0095 [math.HO].
  6. ^ Godbolt, Matt. "Compiler Explorer". Retrieved 10 July 2021.
  7. ^ Kapoor, Rajiv (2009-02-21). "Avoiding the Cost of Branch Misprediction". Intel Developer Zone.
  8. ^ Lemire, Daniel (2019-10-15). "Mispredicted branches can multiply your running times".
  9. ^ "GNU MP 6.1.2: Binary GCD".
  10. ^ Akhavi, Ali; Vallée, Brigitte (2000), "Average Bit-Complexity of Euclidean Algorithms", Proceedings ICALP'00, Lecture Notes Computer Science 1853: 373–387, CiteSeerX 10.1.1.42.7616
  11. ^ 크누스 1998, 페이지 646, 섹션 4.5.2의 연습 39에 답한다.
  12. ^ Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). "§14.4 Greatest Common Divisor Algorithms" (PDF). Handbook of Applied Cryptography. CRC Press. pp. 606–610. ISBN 0-8493-8523-7. Retrieved 2017-09-09.
  13. ^ Cohen, Henri (1993). "Chapter 1 : Fundamental Number-Theoretic Algorithms". A Course In Computational Algebraic Number Theory. Graduate Texts in Mathematics. Vol. 138. Springer-Verlag. pp. 17–18. ISBN 0-387-55640-0.
  14. ^ Stehlé, Damien; Zimmermann, Paul (2004), "A binary recursive gcd algorithm" (PDF), Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, pp. 411–425, CiteSeerX 10.1.1.107.8612, doi:10.1007/978-3-540-24847-7_31, ISBN 978-3-540-22156-2, MR 2138011, INRIA Research Report RR-5050.
  15. ^ Weilert, André (July 2000). "(1+i)-ary GCD Computation in Z[i] as an Analogue to the Binary GCD Algorithm". Journal of Symbolic Computation. 30 (5): 605–617. doi:10.1006/jsco.2000.0422.
  16. ^ Damgård, Ivan Bjerre; Frandsen, Gudmund Skovbjerg (August 12–15, 2003). Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers. 14th International Symposium on the Fundamentals of Computation Theory. Malmö, Sweden. pp. 109–117. doi:10.1007/978-3-540-45077-1_11.{{cite conference}}: CS1 maint: 날짜 형식(링크)
  17. ^ Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (June 13–18, 2004). Binary GCD Like Algorithms for Some Complex Quadratic Rings. Algorithmic Number Theory Symposium. Burlington, VT, USA. pp. 57–71. doi:10.1007/978-3-540-24847-7_4.{{cite conference}}: CS1 maint: 날짜 형식(링크)
  18. ^ Agarwal, Saurabh; Frandsen, Gudmund Skovbjerg (March 20–24, 2006). A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. 7th Latin American Symposium on Theoretical Informatics. Valdivia, Chile. pp. 30–42. doi:10.1007/11682462_8.{{cite conference}}: CS1 maint: 날짜 형식(링크)
  19. ^ Wikström, Douglas (July 11–15, 2005). On the l-Ary GCD-Algorithm in Rings of Integers. Automata, Languages and Programming, 32nd International Colloquium. Lisbon, Portugal. pp. 1189–1201. doi:10.1007/11523468_96.{{cite conference}}: CS1 maint: 날짜 형식(링크)

추가 읽기

확장된 이진 GCD 및 알고리즘의 확률론적 분석을 다룬다.

베즈아웃 계수를 출력하는 확장 바이너리 GCD 알고리즘, 레머의 GCD 알고리즘의 변형을 이용한 다중정밀 정수의 효율적인 처리, GCD와 실수의 지속적인 분수확대 관계 등 다양한 주제를 다룬다.

기능 분석의 렌즈를 통한 평균 사례에서의 알고리즘의 분석: 알고리즘의 주요 매개변수는 동적 시스템으로 주조되며, 그 평균값은 시스템 전송 운영자의 불변측정값과 관련이 있다.

외부 링크