IJPAM: Volume 118, No. 1 (2018)

Title

A NOTE ON KNUTH'S IMPLEMENTATION OF EXTENDED
EUCLIDEAN GREATEST COMMON DIVISOR ALGORITHM

Authors

Anton Iliev$^1$, Nikolay Kyurkchiev$^2$, Angel Golev$^3$
$^{1,2,3}$Faculty of Mathematics and Informatics
University of Plovdiv Paisii Hilendarski
24, Tzar Asen Str., 4000 Plovdiv, BULGARIA

Abstract

In this note we give new and faster natural realization of Extended Euclidean Greatest Common Divisor (EEGCD) algorithm. The motivation of this work is that this algorithm is used in numerous scientific fields [36], [24]. Internet search engines show very high appearance of `greatest common divisor'. In our implementation we reduce the number of iterations and now they are 50% of Knuth's realization of EEGCD. For all algorithms we have use the implementations in Visual C# 2017 programming environment.


This paper is dedicated to Prof. Donald Knuth
on occasion on his 80th anniversary

History

Received: 2017-04-10
Revised: 2018-01-06
Published: February 14, 2018

AMS Classification, Key Words

AMS Subject Classification: 11A05, 68W01
Key Words and Phrases: greatest common divisor, extended Euclidean greatest common divisor, Knuth's algorithm, reduced number of iterations

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms, 1st ed., Addison-Wesley, Boston (1974).

2
A. Aho, J. Ullman, J. Hopcroft, Data Structures and Algorithms, 1st ed., Addison-Wesley, Boston (1987).

3
A. Akritas, A new method for computing polynomial greatest common divisors and polynomial remainder sequences, Numerische Mathematik, 52 (1988), 119-127.

4
A. Akritas, G. Malaschonok, P. Vigklas, On the Remainders Obtained in Finding the Greatest Common Divisor of Two Polynomials, Serdica Journal of Computing, 9 (2015), 123-138.

5
M. Alsuwaiyel, Algorithms: Design Techniques and Analysis, Lecture Notes Series on Computing, revised ed., World Scientific Publishing Company, Hackensack (2016).

6
L. Ammeraal, Algorithms and Data Structures in C++, John Wiley & Sons Inc., New York (1996).

7
S. Baase, A. Gelder, Computer Algorithms, Introduction to Design and Analysis, 3rd ed., Addison-Wesley, Boston (2000).

8
G. Brassard, P. Bratley, Fundamentals of Algorithmics, international ed., Pearson, (2015).

9
D. Bressoud, Factorization and primality testing, Springer Verlag, New York (1989).

10
F. Chang, Factoring a Polynomial with Multiple-Roots, World Academy of Science, Engineering and Technology, 47 (2008), 492-495.

11
Th. Cormen, Algorithms Unlocked, MIT Press, Cambridge (2013).

12
Th. Cormen, Ch. Leiserson, R. Rivest, Cl. Stein, Introduction to Algorithms, 3rd ed., The MIT Press, Cambridge (2009).

13
A. Drozdek, Data Structures and Algorithms in C++, 4th ed., Cengage Learning, Boston (2013).

14
J. Erickson, Algorithms, University of Illinois Press (2009).

15
J. Gareth, J. Jones, Elementary Number Theory, Springer-Verlag, New York (1998).

16
K. Garov, A. Rahnev, Textbook-notes on programming in BASIC for facultative training in mathematics for 9.-10. grade of ESPU, Sofia (1986). (in Bulgarian)

17
S. Goldman, K. Goldman, A Practical Guide to Data Structures and Algorithms Using JAVA, Chapman & Hall/CRC, Taylor & Francis Group, New York (2008).

18
A. Golev, Textbook on algorithms and programs in C#, University Press "Paisii Hilendarski", Plovdiv (2012).

19
M. Goodrich, R. Tamassia, D. Mount, Data Structures and Algorithms in C++, 2nd ed., John Wiley & Sons Inc., New York (2011).

20
R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, Boston (1994).

21
A. Iliev, N. Kyurkchiev, A Note on Knuth's implementation of Euclid's Greatest Common Divisor Algorithm, International Journal of Pure and Applied Mathematics, 117 (2017), 603-608.

22
A. Iliev, N. Valchanov, T. Terzieva, Generalization and Optimization of Some Algorithms, Collection of scientific works of National Conference "Education in Information Society", Plovdiv, ADIS, May 12-13, (2009), 52-58 (in Bulgarian),
http://sci-gems.math.bas.bg/jspui/handle/10525/1356

23
J. Kleinberg, E. Tardos, Algorithm Design, Addison-Wesley, Boston (2006).

24
D. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, 3rd ed., Addison-Wesley, Boston (1998).

25
H. Cohen, A Course in Computational Algebraic Number Theory, Springer, New York (1996).

26
Hr. Krushkov, Programming in C#, Koala press, Plovdiv (2017). (in Bulgarian)

27
A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., Pearson, Boston (2011).

28
A. Menezes, P. Oorschot, S. Vanstone, Handbook of Applied Cryptography, 5th ed., CRC Press LLC, New York (2001).

29
P. Nakov, P. Dobrikov, Programming =++Algorithms, 5th ed., Sofia (2015). (in Bulgarian)

30
A. Rahnev, K. Garov, O. Gavrailov, Textbook for extracurricular work using BASIC, MNP Press, Sofia (1985). (in Bulgarian)

31
A. Rahnev, K. Garov, O. Gavrailov, BASIC in examples and tasks, Government Press ``Narodna prosveta'', Sofia (1990). (in Bulgarian)

32
D. Schmidt, Euclid's GCD Algorithm (2014).

33
R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, Boston (2011).

34
S. Skiena, The Algorithm Design Manual, 2nd ed., Springer, New York (2008).

35
A. Stepanov, Notes on Programming (2007).

36
E. Weisstein, CRC Concise Encyclopedia of Mathematics, Chapman & Hall/CRC, New York (2003).

How to Cite?

DOI: 10.12732/ijpam.v118i1.3 How to cite this paper?

Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2018
Volume: 118
Issue: 1
Pages: 31 - 37


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).