A TIGHT BOUND FOR APPROXIMATING THE SQUARE ROOT
dc.contributor.author | Bshouty, N. | eng |
dc.contributor.author | Mansour, Y. | eng |
dc.contributor.author | Tiwari, P. | eng |
dc.contributor.author | Schieber, B. | eng |
dc.date.accessioned | 2008-02-27T16:49:50Z | |
dc.date.available | 2008-02-27T16:49:50Z | |
dc.date.computerscience | 1999-05-27 | eng |
dc.date.issued | 1995-05-01 | eng |
dc.description.abstract | We prove an $OMEGA$(loglog(1/$epsilon$)) lower bound on the depth of any computation tree and any RAM program with operations {$+, -, *, /, left floor cdot right floor, not, and, or, xor$}, unlimited power of answering YES/NO questions, and constants {0,1} that computes $sqrt x$ to accuracy $epsilon$, for all $x \(mo $ [1,2]. Since Newton method achieves such an accuracy in $O$(loglog(1/$epsilon$)) depth, our bound is tight. | eng |
dc.description.notes | We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca | eng |
dc.identifier.department | 1995-570-22 | eng |
dc.identifier.doi | http://dx.doi.org/10.11575/PRISM/30474 | |
dc.identifier.uri | http://hdl.handle.net/1880/45753 | |
dc.language.iso | Eng | eng |
dc.publisher.corporate | University of Calgary | eng |
dc.publisher.faculty | Science | eng |
dc.subject | Computer Science | eng |
dc.title | A TIGHT BOUND FOR APPROXIMATING THE SQUARE ROOT | eng |
dc.type | unknown | |
thesis.degree.discipline | Computer Science | eng |