[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Schnelle Multiplikation großer Zahlen

Fast multiplication of large numbers

  • Published:
Computing Aims and scope Submit manuscript

Zusammenfassung

Es wird ein Algorithmus zur Berechnung des Produktes von zweiN-stelligen Dualzahlen angegeben. Zwei Arten der Realisierung werden betrachtet: Turingmaschinen mit mehreren Bändern und logische Netze (aus zweistelligen logischen Elementen aufgebaut).

Summary

An algorithm is given for computing the product of twoN-digit binary numbers byO (N lgN lg lgN) steps. Two ways of implementing the algorithm are considered: multitape Turing machines and logical nets (with step=binary logical element.)

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Literatur

  1. Cook, S. A.: On the Minimum Computation Time of Functions. Dissertation, Harvard Universität (1966).

  2. Cook, S. A., andS. O. Aanderaa: On the Minimum Computation Time of Functions. Trans. AMS142, 291–314 (1969).

    Google Scholar 

  3. Cooley, J. W., andJ. W. Tukey: An Algorithm for the Machine Calculation of ComplexFourier Series. Math. Comp.19, 297–301 (1965).

    Google Scholar 

  4. Karacuba, A., (undJ. Ofman): Multiplikation vielstelliger Zahlen mit Rechenautomaten (russisch). Dokl. Akad. Nauk SSSR145, 293–294 (1962).

    Google Scholar 

  5. Knuth, D. E.: The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, Chapter 4: Arithmetic. Addison-Wesley. 1969.

  6. Schönhage, A.: Multiplikation großer Zahlen. Computing1, 182–196 (1966).

    Google Scholar 

  7. Toom, A. L.: Die Komplexität eines logischen Netzes, das die Multiplikation ganzer Zahlen realisiert. Dokl. Akad. Nauk SSSR150, 496–498 (1963).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Fachbereich Mathematik, Universität Konstanz, Postfach 733, BRD-775, Konstanz, Deutschland

    A. Schönhage

  2. Seminar für Angewandte Mathematik, Universität Zürich, Freiestraße 36, CH-8000, Zürich, Schweiz

    V. Strassen

Authors
  1. A. Schönhage
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. V. Strassen
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Part of the research of the second author was done at the Department of Statistics, University of California, Berkeley. He wishes to thank the National Science Foundation for their support (NSF GP-7454).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Schönhage, A., Strassen, V. Schnelle Multiplikation großer Zahlen. Computing 7, 281–292 (1971). https://doi.org/10.1007/BF02242355

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02242355

Search

Navigation