Adobe PDF
(441.59 kB)
| Title Details: | |
|
Integers |
|
| Authors: |
Poulakis, Dimitrios |
| Reviewer: |
Tzanakis, Nikolaos |
| Subject: | MATHEMATICS AND COMPUTER SCIENCE > MATHEMATICS > NUMBER THEORY MATHEMATICS AND COMPUTER SCIENCE > MATHEMATICS > NUMBER THEORY > COMPUTATIONAL NUMBER THEORY MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > ALGORITHMS AND COMPLEXITY |
| Keywords: |
Computational Number Theory
Eukleidian Algorithm Greatest Common Divisor Lenth Of An Integer |
| Description: | |
| Abstract: |
In this chapter we study the basic properties of the divisibility of integer numbers and the time of execution of theirs elementary arithmetical operations. More precisely, we begin from the Euclidean division, we prove the unicity of g-adic expansion of an integer
(where g is a fixe positive number) and we introduce the notion of the length of an integer. Next, we deal with the notion of binary digital operation, we compute the number of binary digital operation needed for the execution of elementary arithmetical operations and we introduce the reader to the algorithms and theirs running time. We give examples of elementary algorithms and the Karatsuba algorithm for fast integer multiplication. We introduce the notions of greatest common divisor and the least common multiple of two integers and we give theirs basic properties. Furthermore, we present the extended Euclidean algorithm and we compute its running time. Finally, we study the solvability of the linear Diophantine equation. |
| Table of Contents: |
Chapter 1 is divided to the following sections:
1.1 Euclidean Division 1.2 Binary Digital Operations 1.3 Αlgorithms 1.3.1 Asymptotic Notations 1.3.2 Types of algorithms 1.4 Faster Multiplication 1.5 Greatest Common Divisor 1.6 Euclidean Algorithm 1.7 Exercices Bibliography |
| Technical Editors: |
Karakostas, Anastasios |
| Type: |
Chapter |
| Creation Date: | 2015 |
| Item Details: | |
| License: |
http://creativecommons.org/licenses/by-nc-nd/3.0/gr |
| Handle | http://hdl.handle.net/11419/1046 |
| Bibliographic Reference: | Poulakis, D. (2015). Integers [Chapter]. In Poulakis, D. 2015. Computational Number Theory [Undergraduate textbook]. Kallipos, Open Academic Editions. https://hdl.handle.net/11419/1046 |
| Language: |
Greek |
| Is Part of: |
Computational Number Theory |
| Number of pages |
40 |
| Publication Origin: |
Kallipos, Open Academic Editions |