• DocumentCode
    2181996
  • Title

    Multiplication is the easiest nontrivial arithmetic function

  • Author

    Alt, Helmut

  • fYear
    1983
  • fDate
    7-9 Nov. 1983
  • Firstpage
    320
  • Lastpage
    322
  • Abstract
    It is shown that floating point (or integer) multiplication can be reduced to the evalution of a very large class of functions including most of the nontrivial functions used in practice. That means that whenever any such function can be evaluated by boolean circuits of size S(n), then multiplication can be done with circuits of size O(S(n)). as well.
  • Keywords
    Circuits; Computer science; Convergence; Digital arithmetic; Polynomials; Size measurement;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1983., 24th Annual Symposium on
  • Conference_Location
    Tucson, AZ, USA
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-0508-1
  • Type

    conf

  • DOI
    10.1109/SFCS.1983.36
  • Filename
    4568094