GCD
and Continued Fractions <§ë¼v¤ù> Ãö«Y¹Ï update:2007/05/07 01:41:18 ¤U¤È
´Á¥Z¾ã²z
<Books>
- A. Aho, J. Hopcroft, and J. Ullman, The
Design and Analysis of Computer Algorithms. Addison-Wesley, 1974
- D. E. Knuth,
The art of computer programming, Vol. 2, 2nd edition,
addison-Wesley, 1981.
- A. J. Menezes, Paul C. van Oorschot,
Scott A. Vanstone, Handbook of applied cryptography, CRC
Press, 1997
- C. K. Yap, Fundamental
Problems of Algorithmic Algebra, Oxford University Press, 2000
°É»~
from: http://www.cs.nyu.edu/cs/faculty/yap/book/
¡@
<Paper>
<GCD>
< Lehmer >
- [Lemer38] D. H. Lemer, "Euclid's algorithm for large
numbers," Am, Math. Mon., Vol. 45, pp.227-233,
1938.
- [Jebelean93] T. Jebelean,
"Improving the
Multiprecision Euclidean algorithm," DISCO'93,
pp. 45-58, 1993.
- [Sorenson95] J. Sorenson, "An Analysis of Lehmer's
Euclidean GCD Algorithm," ICSAC, 1995 [§ë¼v¤ù]
- [Jebelean95] T.
Jebelean, "A double-digit Lehmer-Euclid
algorithm for finding the GCD of long integers," Journal Symbolic Computation, Vol. 19,
pp.145-157, 1995
- [Sorenson04] J. P. Sorenson, "Lehmer's Algorithm for
Very Large Numbers," ANTS VI poster presentation;
abstract appeared in SIGSAM Bulletin, 2004.
- [DB04]B.
Daireaux and B. Vallee, "Dynamical
Analysis of the Parametrized Lehmer¡VEuclid Algorithm,"
Combinatorics, Probability and Computing,
Vol. 13, pp. 499-536, 2004.
< k-ary >
- [Sorenson94] J. Sorenson,
"Analysis of a left-shift binary
GCD algorithm" Journal of
Symbolic Computation,
Vol. 17, no. 6, pp. 473-486., 1994.
- [Sorenson94] J. Sorenson, "Two fast GCD algorithms," J. algorithms, Vol. 16, no. 1, pp. 110-144., 1994. [§ë¼v¤ù]
- [Weber95] K. Weber, "The accelerated integer
GCD algorithm," ACM Transactions on Mathematical SW,
Vol. 21, pp. 111-122, 1995. [§ë¼v¤ù]
- [SL97] M. S. Sedjelmaci , C. Lavault, "Improvements on the
accelerated integer GCD algorithm," Information Processing Letters, Elsevier Science,
,Vol. 61, no. 1, pp.31-36, Jan 1997 [§ë¼v¤ù]
- [WTM05] K. Weber, V. Trevisan, L. F.
Martins, "A modular integer GCD
algorithm," J. algorithms, Vol. 54, no. 2,
pp.152-167, 2005
< HGCD >
- [Schonhage71] A. Schonhage, "Schnelle
Berechung von Kettenbruchentwicklugen," Acta Informatica,
Vol. 1, pp.139-144, 1971.
- [TY90] K. Thull, C. K. Yap, "A unified approach to
HGCD algorithms for polynomials and integers," Manuscript.
Available from http://cs.nyu.edu/cs/faculty/yap/, 1990
- [Cesari98] G. Cesari, "Parallel Implementation
of sch ¹nhage's Integer GCD Algorithm,"ANTS-III
LNCS ,Vol. 1423, pp.64-76, 1998
- [Lichtblau05] D. Lichtblau, "Half-GCD and Fast
Rational Recovery,"
Proceedings of the 2005 International Symposium on Symbolic and
Algebraic Computation, 2005
- [Moller05] N. Moller, "On Sch ¹nhage's algorithm and subquadratic integer gcd computation,"
2005
< other >
- [Stein67] J. Stein, "Computational
problems associated with Racah algebra," J. Comp. Phys,
Vol. 1, pp.397-405, 1967.
- [Dixon70] J. D. Dixon, "The
number of steps in the Euclidean algorithm," J. Number Theory,
1970
- [Dixon71] J. D. Dixon, "A Simple Estimate for the
Number of Steps in the Euclidean Algorithm,"
The American Mathematical Monthly, 1971
- [BD71] J. L. Brown, R. L. Duncan, "The least remainder algorithm,"
Fibonacci Quarterly , Vol. 9, no. 4, pp.347-.50, 1971
- [YK75] A.C. Yao,
D.E. Knuth, "Analysis of the subtractive algorithm for greatest
common divisors," Proc. Natl. Acad. Sci. USA 72, pp. 4720-4722, 1975
- [Purdy83] G. B. Purdy, "A carry free algorithm
for finding the greatest common divisor of two integers",
Computers & Mathematics with Application, Vol. 9, no.
2, pp. 311-316, 1983
- [Norton85] G. H. Norton, "Extending the Binary GCD
Algoriihm," LNCS, Vol. 299, 1985
- [Norton87] G. Norton, "A shift-remainder GCD
algorithm," AAECC, pp.350-356, 1987
- [KMR87] R. Kannan, G. L. Miller, and L.
Rudolph, "Sublinear parallel
algorithm for computing the greatest common divisor of two integers,"
SIAMJC, Vol. 16, pp. 7-16, 1987.
- [Bshouty89] N. H. Bshouty, "Euclidean
GCD algorithm is not optimal," manuscript, 1989
- [PM91] S. N. Parikh, D. W. Matula, "A redundant binary
Euclidean GCD algorithm," Computer Arithmetic, 10th IEEE Symposium, pp.220-225, 1991 [§ë¼v¤ù]
- [Jebelean93] T. Jebelean, "A generalization of the
binary GCD algorithm," ISSAC, 1993
- [Hensley94] D. Hensley, "The number of steps in
the Euclidean algorithm," J. Number Theory,
Vol. 49 , pp. 142-182, 1994
- [Shallit94]
J. Shallit, "Origins of the analysis
of the Euclidean algorithm," Historia Math., Vol.
21, pp. 401-419, 1994
- [RS96] C. R Éssner, J.-P.Seifert, "The Complexity of
Approximate Optima for Greatest Common Divisor Computations,"
Proceedings of the 2nd International Algorithmic
Number Theory Symposium, ANTS-II, 1996.
- [Vallee98] B. Vallee, "The Complete Analysis of
the Binary Euclidean Algorithm," ANTS-III
LNCS ,Vol. 1423, pp.77-94, 1998
- [Vallee98] B. Vall Áe, "Dynamics of the binary Euclidean
algorithm: functional analysis and operators," Algorithmica,
Vol. 22, no. 4, pp. 660-685, 1998
- [Brent98] R. P. Brent, "Revisiting the Binary
Euclidean Algorithm," Manuscript. Available from http://web.comlab.ox.ac.uk/
- [HS99] G. Havas, J. Seifert, "The Complexity of the Extended GCD
Problem," LNCS, Vol.1672, pp.103-113, 1999.
- [AV00] A. Akhavi, B. Vall Áe, "Average Bit-Complexity of
Euclidean Algorithms," LNCS, Vol. 1853, pp.373-387, 2000
- [Sedjelmaci01] S.M. Sedjelmaci, "On A Parallel
Lehmer-Euclid GCD Algorithm," in Proc. of the
International Symposium on Symbolic and Algebraic Computation,
pp.303-308, 2001
- [Collins02] G. E. Collins, "A Fast Euclidean
Algorithm for Gaussian Integers," J. Symbolic
Computation, Vol. 33, pp.385-392, 2002
- [PW02] V. Y. Pan, X. Wang, "Acceleration of Euclidean
algorithm and extensions," Proceedings of the 2002
International Symposium on Symbolic and Algebraic Computation, pp.
207-213, 2002
- [PW03] V. Y. Pan, X. Wang, "Acceleration of Euclidean
algorithm and extensions and Rational number reconstruction,"
SIAM Journal on Computing, Vol 32, pp. 548-556, 2003
- [Vallee03] B. Vallee, "Dynamical analysis of a
class of Euclidean algorithms," TCS, Vol.
297, pp. 447-486, 2003
- [BV03-1] V. Baladi, B. Vallee, "Euclidean algorithms are
Gaussian," Journal of Number Theory, 2004
- [BV03-2] V. Baladi, B. Vallee, "Distributional Analyses
of Euclidean Algorithms," The First Workshop on
Analytic Algorithmics and Combinatorics(ANALCO04), 2004
- [PST04]
V. Piehl, J. P. Sorenson, N. Tiedeman, "Genetic algorithms for
the extended GCD problem," Available from http://euclid.butler.edu/~sorenson/papers/
, 2004
- [PW04] V. Y. Pan, X. Wang, "On rational number
reconstruction and approximation," SIAM Journal on
Computing, Vol 33, no. 2, pp. 502-503, 2004
- [Sorenson04-1] J. Sorenson, "An Analysis of the
Generalized Binary GCD Algorithm," Fields
Institute Communications, 2004
- [Sorenson04-2] J. Sorenson, "GCD Algorithms based on
Karatsuba Multiplication," Available from http://euclid.butler.edu/~sorenson/papers/
, 2004
- [SZ04] D Stehle, P Zimmermann, "A Binary Recursive GCD
Algorithm," LNCS, Vol. 3076,
pp. 411 - 425, 2004
- [Sedjelmaci04-1] S. M. Sedjelmaci, "A modular Reduction for
GCD computation," Journal of Computational and
Applied Mathematics, Vol. 162, pp.17-31, 2004
- [Sedjelmaci04-2]
S. M. Sedjelmaci, "The Accelerated Euclidean
Algorithm," Encuentro de Algebra Computationaly
Aplicaciones, pp.283-287, 2004 [§ë¼v¤ù]
- [DL05] B. Daireaux, L. Lhote, "Analysis of fast versions
of the Euclid algorithm," Manuscript,
2005
- [Vallee05] B. Vallee,
"Euclidean Dynamics," Discrete and
Continuous Dynamical Systems, (http://users.info.unicaen.fr/~brigitte/Publications/),
2005
- [LV06] L. Lhote, B. Vallee,"Sharp estimates for the
main parameters of the Euclid Algorithm," LNCS,
Vol 3887, pp. 689-702, 2006
<GCD of Many
Integers>
- [Bradley70] G. H. Bradley, "Algorithm and Bound for
the Greatest Common Divisor of n Integers," Numberical
Mathematics, Vol. 13, 1970
- [Johnson76] R. W. Johnson, "The algorithms of Euclid
and Jacobi," International Journal of Mathematical
Education in Science, Vol. 7, 1976
- [Waterman77] M. S. Waterman, "Multidimensional greatest
common divisor and Lehmer algorithms," BIT Numerical
Mathematics, Vol. 17, pp. 465 - 478, 1977
- [Jebelean93] T. Jebelean, "Comparing several GCD
algorithm," Proceedings of the 11th Symposium on
Computer Arithmetic, pp. 180-185, 1993.
- [MH95] B. S. Majewski, G. Havas, "A solution to the
extended gcd problem," ISSAC, pp.248-253, 1995
- [FH96]
D. Ford, G. Havas, "A New Algorithm and Refined Bounds for Extended Gcd Computation,"
LNCS, 1996
- [CFGH99] G. Cooperman, S. Feisel, J. V. Z. Gathen, G. Havas, "GCD of Many Integers (Extended Abstract),"
COCOON, Vol. 1627, pp.310-317, 1999
- [Havas03] G. Havas, "On the complexity of the
extended Euclidean algorithm (Extended Abstract)," Electronic
Notes in Theoretical Computer Science, Vol. 78, 2003
<Continued Fractions>
- [Jr47] M. H. Jr, "On the Sum and Product of Continued Fractions," The Annals of
Mathematics,
1947
- [Khinchin64] A. I. Khinchin, "Continued Fractions," University of
Chicago Press,
1964
- [Heilbronn69] H. Heilbronn, "On the average length of a class of
continued fractions," Number Theory and Analysis, Plenum, pp. 87-96,
1969
- [Dixon70] J. D. Dixon, "The Number of Steps in the Euclidean
Algorithm", J. Number Theory, Vol 2, pp. 414-422, 1970
- [Hickerson77] D. Hickerson, "Continued fractions and density results
for Dedekind sums," J. Reine Angew. Math. ,Vol. 290 , pp. 113-116,
1977
- [Schweiger82] F. Schweiger, "Continued fractions with odd and even
partial quotients," Mathematisches Institut der Universitat Salzburg,
Arbeitsbericht ,Vol. 2, 1982
- [Mayer91] D.H. Mayer, "Continued fractions and related
transformations," Ergodic Theory, Symbolic Dynamics and Hyperbolic
Spaces, 1991, pp. 175-222.
- [KL95] C. Kraaikamp, A. Lopes, "The Theta group and the
continued fraction expansion with even partial quotients,"
Geometriae Dedicata, Vol. 59, no. 3, 1995
- [FV96] P. Flajolet, B. Vallee ,"Continued Fraction
Algorithms, Functional Operators, and Structure Constants,"
INRIA, 1996
- [Vall Áe98] B. Vall Áe, "Fractions continues à
contrainees p Áriodiques," J. Number Theory,
Vol. 72, pp. 183-235, 1998
- [Vallee99] B. Vallee, "Unified Analysis of
Euclidean Algorithms," 1999
- [Brent99]
R. P. Brent, "Further analysis of the
Binary Euclidean algorithm," Technical Report, Oxford University Computing Laboratory,
1999
- [Brent00] R. P. Brent, "Twenty years' analysis of
the Binary Euclidean Algorithm," In A. W. Roscoe J.
Davies and J. Woodcock, editors, Millenial Perspectives in Computer
Science: Proceedings of the 1999 Oxford-Microsoft Symposium in honour of
Professor Sir Antony Hoare, pages 41¡V53,
Palgrave, New York, 2000.
- [Vallee00] B. Vallee, "Digits and Continuants in
Euclidean Algorithms. Ergodic Versus Tauberian Theorems.,"
Journal de Theorie des Nombres de Bordeaux, Vol 12, pp. 531-570,
2000
- [Lhote03] L. Lhote, "Efficient Computation of
a Class of Continued Fraction Constants," Algorithms
Seminar 2002-2004, pp. 71-74 , 2003
- [Lhote04] L. Lhote, "Computation of a Class or
Continued Fraction Constants," Analytic
Algorithmics and Combinatorics (ANALCO), 2004
An
Introduction to the Continued Fraction
A
Continued Fraction Calculator
<§ë¼v¤ù>
An
example for Lehmer¡¦s GCD.ppt
An
example for Lehmer¡¦s GCD-2.ppt
(¹J¨ì¤£¦P°Ó®É,¨ú¤¤¶¡È¬°°Ó)
An example of
HGCD.ppt
[Sorenson95] An
Analysis of Lehmer's Euclidean GCD Algorithm.ppt
Finite
Continued Fractions.ppt
[SL97]Improvements
on the accelerated integer GCD algorithm.ppt
[Sedjelmaci04]The Accelerated
Euclidean Algorithm.ppt (95/3/3)
HGCD.ppt (95/5/12)
[PM91]A Redundant
Binary Euclidean GCD Algorithm.ppt (95/5/19)
[Sorenson94]Two Fast GCD Algorithms.ppt(95/5/26)
[Weber95] The accelerated
integer GCD algorithm.ppt(95/6/30)
[Jebelean93] A
Generalization of the Binary GCD Algorithm (95/9/8)
[PW02] Acceleration
of Euclidean Algorithm and Extensions (95/9/15)
Right
extended k-ary GCD.doc
Lehmer GCD ¤Ó°±¤î±ø¥ó
HGCD_951019.ppt
¨D¼ªk¤Ï¤¸¯Àmod prime powers.doc
Generalized
Binary division.ppt (10/26)
¡@
< ÁY ¼g >
[TCS]
Theoretical Computer Science
[LNCS] Lecture Notes in Computer Science
[ICSAC] International Conference on Symbolic and Algebraic Computation,
[J.
algorithms] Journal of Algorithms
[J. Number
Theory] Journal of Number Theory
[AAECC] Algebraic
Algorithms and Error-Correcting Codes
[ISSAC]
International Symposium on Symbolic and Algebraic Computation
[INRIA] INSTITUT
NATIONAL DE RECHERCHE EN INFORMATIQUE ET AUTOMATIQUE
[SIAM]
Society
for Industrial and Applied Mathematics