Skip to main content
Erschienen in: Theory of Computing Systems 8/2020

15.05.2020

Multiplication Algorithm Based on Collatz Function

verfasst von: David Barina

Erschienen in: Theory of Computing Systems | Ausgabe 8/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Hercher, C.: Über die Länge nicht-trivialer Collatz-Zyklen. Die Wurzel, 6 and 7 (2018) Hercher, C.: Über die Länge nicht-trivialer Collatz-Zyklen. Die Wurzel, 6 and 7 (2018)
2.
Zurück zum Zitat Tao, T.: The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 (2011) Tao, T.: The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 (2011)
3.
Zurück zum Zitat Lagarias, J.C.: The 3x + 1 problem and its generalizations. The American Mathematical Monthly 92(1), 3–23 (1985)MathSciNetCrossRef Lagarias, J.C.: The 3x + 1 problem and its generalizations. The American Mathematical Monthly 92(1), 3–23 (1985)MathSciNetCrossRef
4.
Zurück zum Zitat Crandall, R.E.: On the “3x + 1” problem. Mathematics of Computation 32(144), 1281–1292 (1978)MathSciNetMATH Crandall, R.E.: On the “3x + 1” problem. Mathematics of Computation 32(144), 1281–1292 (1978)MathSciNetMATH
5.
Zurück zum Zitat 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 (1963–1999) (sorted by author). arXiv:math/​0309224 (2003)
7.
Zurück zum Zitat 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” 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”
8.
Zurück zum Zitat 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) 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)
9.
Zurück zum Zitat Lagarias, J.C., Weiss, A.: The 3x + 1 problem: Two stochastic models. Annals of Applied Probability 2(1), 229–261 (1992)MathSciNetCrossRef Lagarias, J.C., Weiss, A.: The 3x + 1 problem: Two stochastic models. Annals of Applied Probability 2(1), 229–261 (1992)MathSciNetCrossRef
10.
Zurück zum Zitat Karatsuba, A., Ofman, Y.: Multiplication of many-digital numbers by automatic computers. Physics – Doklady 7, 595–596 (1963). Originally published in 1962 Karatsuba, A., Ofman, Y.: Multiplication of many-digital numbers by automatic computers. Physics – Doklady 7, 595–596 (1963). Originally published in 1962
11.
Zurück zum Zitat 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 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.
Metadaten
Titel
Multiplication Algorithm Based on Collatz Function
verfasst von
David Barina
Publikationsdatum
15.05.2020
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 8/2020
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-020-09986-5

Weitere Artikel der Ausgabe 8/2020

Theory of Computing Systems 8/2020 Zur Ausgabe