Top

Theory of Computing Systems

Published in:

15-05-2020

Multiplication Algorithm Based on Collatz Function

Author: David Barina

Published in: Theory of Computing Systems | Issue 8/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article An Improved FPT Algorithm for Independent Feedback Vertex Set

next article On Envy-Free Revenue Approximation for Combinatorial Buyers with Budgets

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Hercher, C.: Über die Länge nicht-trivialer Collatz-Zyklen. Die Wurzel, 6 and 7 (2018)

Tao, T.: The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 (2011)

Lagarias, J.C.: The 3x + 1 problem and its generalizations. The American Mathematical Monthly 92(1), 3–23 (1985)MathSciNetCrossRef

Crandall, R.E.: On the “3x + 1” problem. Mathematics of Computation 32(144), 1281–1292 (1978)MathSciNetMATH

Lagarias, J.C.: The 3x + 1 problem: An annotated bibliography (1963–1999) (sorted by author). arXiv:math/0309224 (2003)

Lagarias, J.C.: The 3x + 1 problem: An annotated bibliography, II (2000-2009). arXiv:math/math/0608208 (2006)

Chamberland, M.: Una actualizacio del problema 3x + 1. Butlleti de la Societat Catalana de Matematiques 22(2), 1–27 (2003). An English version “An Update on the 3x + 1 Problem”

Oliveira e Silva, T.: Empirical verification of the 3x + 1 and related conjectures. In: Lagarias, J.C. (ed.) The Ultimate Challenge: The 3x + 1 Problem, pp 189–207. American Mathematical Society (2010)

Lagarias, J.C., Weiss, A.: The 3x + 1 problem: Two stochastic models. Annals of Applied Probability 2(1), 229–261 (1992)MathSciNetCrossRef

10.

Karatsuba, A., Ofman, Y.: Multiplication of many-digital numbers by automatic computers. Physics – Doklady 7, 595–596 (1963). Originally published in 1962

11.

Toom, A.: The complexity of a scheme of functional elements realizing the multiplication of integers. Soviet Mathematics – Doklady 3, 714–716 (1963). Originally published in RussianMATH

12.

Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7(3), 281–292 (1971)MathSciNetCrossRef

Title: Multiplication Algorithm Based on Collatz Function
Author: David Barina
Publication date: 15-05-2020
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 8/2020
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-020-09986-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 8/2020

An Improved FPT Algorithm for Independent Feedback Vertex Set

On Envy-Free Revenue Approximation for Combinatorial Buyers with Budgets

Satisfiability Algorithm for Syntactic Read-k-times Branching Programs

Dichotomy for Holant∗ Problems on the Boolean Domain

Premium Partner