Detail publikace

Convergence verification of the Collatz problem

BAŘINA David. Convergence verification of the Collatz problem. The Journal of Supercomputing, roč. 77, č. 3, 2021, s. 2681-2688. ISSN 1573-0484.
Název česky
Ověření konvergence Collatzova problému
Typ
článek v časopise
Jazyk
angličtina
Autoři
Bařina David, Ing., Ph.D. (UPGM FIT VUT)
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
The Journal of Supercomputing, roč. 77, č. 3, ISSN 1573-0484
Vydavatel
Springer Verlag
DOI
10.1007/s11227-020-03368-x
UT WoS
000544846600001
EID Scopus
2-s2.0-85087382041
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"
}
Soubory
Nahoru