How fast can we multiply large integers on an actual computer?

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


We provide two complexity measures that can be used to measure the running time of algorithms to compute multiplications of long integers. The random access machine with unit or logarithmic cost is not adequate for measuring the complexity of a task like multiplication of long integers. The Turing machine is more useful here, but fails to take into account the multiplication instruction for short integers, which is available on physical computing devices. An interesting outcome is that the proposed refined complexity measures do not rank the well known multiplication algorithms the same way as the Turing machine model.

Original languageEnglish (US)
Title of host publicationLATIN 2014
Subtitle of host publicationTheoretical Informatics - 11th Latin American Symposium, Proceedings
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783642544224
StatePublished - 2014
Event11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay
Duration: Mar 31 2014Apr 4 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8392 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Latin American Theoretical Informatics Symposium, LATIN 2014

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'How fast can we multiply large integers on an actual computer?'. Together they form a unique fingerprint.

Cite this