Loading...
Please wait, while we are loading the content...
Similar Documents
A Binary Recursive Gcd Algorithm
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Stehlé, Damien Zimmermann, Paul |
| Abstract | The binary algorithm is a variant of the Euclidean algorithm that performs well in practice. We present a quasi-linear time recursive algorithm that computes the greatest common divisor of two integers by simulating a slightly modified version of the binary algorithm. The structure of the recursive algorithm is very close to the one of the well-known Knuth-Schönhage fast gcd algorithm, but the description and the proof of correctness are significantly simpler in our case. This leads to a simplification of the implementation and to better running times. |
| File Format | |
| Language | English |
| Publisher Date | 2002-01-01 |
| Publisher Institution | INRIA |
| Access Restriction | Open |
| Subject Keyword | QUASI-LINEAR TIME COMPLEXITY GCD COMPUTATION EUCLIDEAN ALGORITHM KNUTH-SCHöNHAGE ALGORITHM info Computer Science [cs] Other [cs.OH] |
| Content Type | Text |
| Resource Type | Article |
