Detail výsledku

Convergence verification of the Collatz problem

BAŘINA, D. Convergence verification of the Collatz problem. JOURNAL OF SUPERCOMPUTING, 2021, vol. 77, no. 3, p. 2681-2688. ISSN: 1573-0484.
Typ
článek v časopise
Jazyk
anglicky
Autoři
Bařina David, Ing., Ph.D., UPGM (FIT)
Abstrakt

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.

Klíčová slova

Collatz conjecture, software optimization, parallel computing, number theory

Rok
2021
Strany
2681–2688
Časopis
JOURNAL OF SUPERCOMPUTING, roč. 77, č. 3, ISSN 1573-0484
DOI
10.1007/s11227-020-03368-x
UT WoS
000544846600001
EID Scopus
2-s2.0-85087382041
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="0920-8542",
  url="https://www.fit.vut.cz/research/publication/12315/"
}
Soubory
Projekty
IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, zahájení: 2016-01-01, ukončení: 2020-12-31, ukončen
Moderní metody zpracování, analýzy a zobrazování multimediálních a 3D dat, VUT, Vnitřní projekty VUT, FIT-S-20-6460, zahájení: 2020-03-01, ukončení: 2023-02-28, ukončen
Výzkumné skupiny
Výzkumná skupina počítačové grafiky (VZ GRAPH)
Pracoviště
Ústav počítačové grafiky a multimédií (UPGM)
Nahoru