Some related functions to integer GCD and coprimality. (English) Zbl 1268.11162
Bonomo, Flavia (ed.) et al., LAGOS’11 – VI Latin-American algorithms, graphs, and optimization symposium. Extended abstracts from the symposium, Bariloche, Argentina, March 28–April 1, 2011. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 37, 135-140 (2011).
Summary: We generalize a formula of B. E. Litow [“Parallel Complexity of Integer Coprimality”, Electronic Colloquium on Computational Complexity, Report No. 9 (1998); http://eccc.hpi-web.de/report/1998/009/download/)] and propose several new formula linked with the parallel Integer Coprimality, Integer GCD and Modular Inverse problems as well. Particularly, we find a new trigonometrical definition of the GCD of two integers \(a,b\geq 1\):
\[
\gcd(a,b) = \frac1{\pi}\int_0^\pi \cos[(b-a)x]\sin^2(abx)\sin(ax)\sin(bx)\,dx
\]
.
For the entire collection see [Zbl 1239.05004].
For the entire collection see [Zbl 1239.05004].
MSC:
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W10 | Parallel algorithms in computer science |
References:
| [1] | Chor, B.; Goldreich, O., An improved parallel GCD, Algorithmica, 5, 1-10 (1990) · Zbl 0689.68046 |
| [2] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press · Zbl 0936.11069 |
| [3] | Hardy, G. H.; Ramanujan, S., Asymptotic formulae in combinatorial analysis, Proc. London Math. Soc., 17, 75-115 (1918) · JFM 46.0198.04 |
| [4] | Hardy, G. H.; Littlewood, J. E., A new solution of Waringʼs problem, Q. J. Math., 48, 272-293 (1919) · JFM 47.0114.01 |
| [5] | Karp, R.; Ramachandran, V., Parallel Algorithms for Shared-memory Machines, (Van Leeuwen, J., Algorithms and Complexity. Algorithms and Complexity, Handbook of Theoretical Computer Science, vol. A (1990), Elsevier and MIT Press) · Zbl 0900.68267 |
| [6] | B. Litow, Parallel Complexity of Integer Coprimality, Electronic Colloquium on Computational Complexity, Report No. 9, 1998.; B. Litow, Parallel Complexity of Integer Coprimality, Electronic Colloquium on Computational Complexity, Report No. 9, 1998. |
| [7] | Schönhage, A., Schnelle Berechnung von Kettenbruchentwicklugen, Acta Informatica, 1, 139-144 (1971) · Zbl 0223.68008 |
| [8] | Sedjelmaci, S. M., A Parallel Extended GCD Algorithm, Journal of Discrete Algorithms, 6, 526-538 (2008) · Zbl 1193.11118 |
| [9] | S.M. Sedjelmaci, On a Sieve Function for Coprimality and Modular Inverse, Preprint, LIPN, Univ. of Paris 13, http://www-lipn.univ-paris13.fr/ sedjelmaci; S.M. Sedjelmaci, On a Sieve Function for Coprimality and Modular Inverse, Preprint, LIPN, Univ. of Paris 13, http://www-lipn.univ-paris13.fr/ sedjelmaci |
| [10] | Sorenson, J., Two Fast GCD Algorithms, J. of Algorithms, 16, 110-144 (1994) · Zbl 0815.11065 |
| [11] | Vinogradov, I. M., Method of Trigonometrical Sums in the Theory of Numbers (2004), Dover Publications: Dover Publications Mineola, NY · Zbl 1093.11001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
