Detail publikace

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.
Název česky
Ověření konvergence Collatzova problému
Typ
článek v časopise
Jazyk
anglicky
Autoři
Bařina David, Ing., Ph.D. (UPGM)
Klíčová slova

Collatz domněnka, optimalizace softwaru, paralelní počítání, teorie čísel

Abstrakt

Tento článek představuje nový algoritmický přístup pro výpočetní ověření konvergence Collatzova problému. Hlavním přínosem článku je nahrazení obrovských předpočítaných tabulek obsahujících O(2^N) záznamů malými lookup tabulkami obsahujícími pouze O(N) prvků. Námi vytvořená jednovláknová implementace na CPU dokáže ověřit 4,2×10^9 128bitových čísel za sekundu na počítači s procesorem Intel Xeon Gold 5218 a naše paralelní implementace v OpenCL dosahuje rychlosti 2,2×10^11 128bitových čísel za sekundu na grafické kartě NVIDIA GeForce RTX 2080. Kromě ověřování konvergence zaznamenává náš program také maximální hodnoty trajektorií.

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="1573-0484",
  url="https://www.fit.vut.cz/research/publication/12315/"
}
Nahoru