Detail publikace

Convergence verification of the Collatz problem

BAŘINA, D.

Originální název

Convergence verification of the Collatz problem

Typ

článek v časopise ve Web of Science, Jimp

Jazyk

angličtina

Originální 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

Autoři

BAŘINA, D.

Vydáno

1. 3. 2021

ISSN

1573-0484

Periodikum

Journal of Supercomputing

Ročník

77

Číslo

3

Stát

Spojené státy americké

Strany od

2681

Strany do

2688

Strany počet

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/"
}

Dokumenty

postprint.pdf
Barina2020_Article_ConvergenceVerificationOfTheCo.pdf