Publication result detail

Convergence verification of the Collatz problem

BAŘINA, D.

Original Title

Convergence verification of the Collatz problem

English Title

Convergence verification of the Collatz problem

Type

WoS Article

Original 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.

English 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.

Keywords

Collatz conjecture, software optimization, parallel computing, number theory

Key words in English

Collatz conjecture, software optimization, parallel computing, number theory

Authors

BAŘINA, D.

RIV year

2022

Released

01.03.2021

ISBN

1573-0484

Periodical

JOURNAL OF SUPERCOMPUTING

Volume

77

Number

3

State

United States of America

Pages from

2681

Pages to

2688

Pages count

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

Documents

postprint
publisher's version