Přístupnostní navigace
E-application
Search Search Close
Publication detail
BAŘINA, D.
Original Title
Convergence verification of the Collatz problem
Type
journal article in Web of Science
Language
English
Original 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.
Keywords
Collatz conjecture, software optimization, parallel computing, number theory
Authors
Released
1. 3. 2021
ISBN
1573-0484
Periodical
Journal of Supercomputing
Year of study
77
Number
3
State
United States of America
Pages from
2681
Pages to
2688
Pages count
8
URL
https://www.fit.vut.cz/research/publication/12315/
BibTex
@article{BUT168171, author="David {Bařina}", title="Convergence verification of the Collatz problem", journal="Journal of Supercomputing", year="2021", volume="77", number="3", pages="2681--2688", doi="10.1007/s11227-020-03368-x", issn="1573-0484", url="https://www.fit.vut.cz/research/publication/12315/" }