Square rooting is as difficult as multiplication

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 1979 English Publisher:Springer Science and Business Media LLCJournal:Computing, volume 21, pages 221-232 (issn: 0010-485X, eissn: 1436-5057,

Copyright policy )

Authors: Helmut Alt;

doi: 10.1007/bf02253055

Square rooting is as difficult as multiplication

- Summary
- Subjects
- Metrics

Abstract

It is shown that multiplication of numbers and square rooting have the same complexity, i. e. from a program for multiplication one can construct a program for square rooting with the same asymptotic time complexity (1 step≦1 bit-operation) and vice versa. It follows from the Schonhage-Strassen algorithm that square rooting can be performed in 0 (n logn log logn) bit-operations.

Related Organizations

Saarland University
Germany

Keywords

Asymptotic Time Complexity, Analysis of algorithms and problem complexity, Schoenhage- Strassen Algorithm, Multiplication, Square Rooting

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	14
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average