Result Details

Multiplication Algorithm Based on Collatz function

BAŘINA, D. Multiplication Algorithm Based on Collatz function. THEORY OF COMPUTING SYSTEMS, 2020, vol. 64, no. 8, p. 1331-1337. ISSN: 1433-0490.

Type

journal article

Language

English

Authors

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

Abstract

This article presents a new multiplication algorithm based on the Collatz function. Assuming the validity of the Collatz conjecture, the time complexity of multiplying two n-digit numbers is O(kn), where the k is the number of odd steps in the Collatz trajectory of the first multiplicand. Most likely, the algorithm is only of theoretical interest.

Keywords

multiplication algorithm, division algorithm, computer arithmetic, Collatz conjecture

Published

2020

Pages

1331–1337

Journal

THEORY OF COMPUTING SYSTEMS, vol. 64, no. 8, ISSN 1433-0490

DOI

10.1007/s00224-020-09986-5

UT WoS

000533052700001

EID Scopus

2-s2.0-85084840441

BibTeX

@article{BUT163996,
  author="David {Bařina}",
  title="Multiplication Algorithm Based on Collatz function",
  journal="THEORY OF COMPUTING SYSTEMS",
  year="2020",
  volume="64",
  number="8",
  pages="1331--1337",
  doi="10.1007/s00224-020-09986-5",
  issn="1432-4350",
  url="https://www.fit.vut.cz/research/publication/12284/"
}

Files

Projects

IT4Innovations excellence in science, MŠMT, Národní program udržitelnosti II, LQ1602, start: 2016-01-01, end: 2020-12-31, completed
Moderní metody zpracování, analýzy a zobrazování multimediálních a 3D dat, BUT, Vnitřní projekty VUT, FIT-S-20-6460, start: 2020-03-01, end: 2023-02-28, completed

Research groups

Computer Graphics Research Group (RG GRAPH)

Departments

Department of Computer Graphics and Multimedia (DCGM)