Reference Books D

GCD and Continued Fractions <投影片> 關係圖 update:2007/05/07 01:41:18 下午期刊整理

<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 [投影片]
[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–Euclid 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. [投影片]
[Weber95] K. Weber, "The accelerated integer GCD algorithm," ACM Transactions on Mathematical SW, Vol. 21, pp. 111-122, 1995. [投影片]
[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 [投影片]
[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 [投影片]
[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 2^nd 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 [投影片]
[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

[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

[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–53, 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