Publication Details
Convergence verification of the Collatz problem
BAŘINA David. Convergence verification of the Collatz problem. The Journal of Supercomputing, vol. 77, no. 3, 2021, pp. 2681-2688. ISSN 1573-0484.
Czech title
Ověření konvergence Collatzova problému
Type
journal article
Language
english
Authors
Bařina David, Ing., Ph.D. (DCGM FIT BUT)
Keywords
Collatz conjecture, software optimization, parallel computing, number theory
Abstract
This article presents a new algorithmic approach for computational convergence verification of the Collatz problem. The main contribution of the paper is the replacement of huge precomputed tables containing O(2^N) entries with small lookup tables comprising just O(N) elements. Our single-threaded CPU implementation can verify 4.2×10^9 128-bit numbers per second on Intel Xeon Gold 5218 CPU computer, and our parallel OpenCL implementation reaches the speed of 2.2×10^11 128-bit numbers per second on NVIDIA GeForce RTX 2080. Besides the convergence verification, our program also checks for path records during the convergence test.
Published
2021
Pages
2681-2688
Journal
The Journal of Supercomputing, vol. 77, no. 3, ISSN 1573-0484
Publisher
Springer Verlag
DOI
UT WoS
000544846600001
EID Scopus
BibTeX
@ARTICLE{FITPUB12315, author = "David Ba\v{r}ina", title = "Convergence verification of the Collatz problem", pages = "2681--2688", journal = "The Journal of Supercomputing", volume = 77, number = 3, year = 2021, ISSN = "1573-0484", doi = "10.1007/s11227-020-03368-x", language = "english", url = "https://www.fit.vut.cz/research/publication/12315" }
Files