Detail publikace

Convergence verification of the Collatz problem

BAŘINA, D.

Originální název

Convergence verification of the Collatz problem

Anglický název

Convergence verification of the Collatz problem

Jazyk

en

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.

Anglický 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.

Dokumenty

BibTex


@article{BUT168171,
  author="David {Bařina}",
  title="Convergence verification of the Collatz problem",
  annote="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.",
  address="NEUVEDEN",
  chapter="168171",
  doi="10.1007/s11227-020-03368-x",
  edition="NEUVEDEN",
  howpublished="online",
  institution="NEUVEDEN",
  number="3",
  volume="77",
  year="2021",
  month="march",
  pages="2681--2688",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}