Publication Details

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.

Czech title

Ověření konvergence Collatzova problému

Type

journal article

Language

English

Authors

Bařina David, Ing., Ph.D. (DCGM)

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

Journal of Supercomputing, vol. 77, no. 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/"
}

Files