1

I want to calculate the square root of some integer without using any floating point arithmetic. The catch, however, is that I don't want to discard precision from the output. That is to say, I do not want a rounded integer as the result, I would like to achieve the decimal point value as well, at least to two significant digits. As an example:

sqrt(9) = 3
sqrt(10) = 3.16
sqrt(999999) = 999.99

I've been thinking about it but I haven't particularly come up with solutions, nor has searching helped much since most similar questions are just that, only similar.

Output is acceptable in any form which is not a floating point number and accurately represents the data. Preferably, I would have two ints, one for the portion before the decimal and one for the portion after the decimal.

I'm okay with just pseudo-code / an explained algorithm, if coding C would be best. Thanks

Michael Yousef
  • 602
  • 3
  • 11
  • 22
  • 2
    If you haven't problems with overflow/wrap-around, you can multiply by 10 [edit: 10000, not 10] and calculate the integer square root. This, however, yields a truncated result (not a correctly rounded one). – mafso Jun 12 '14 at 13:21
  • 1
    You haven't said how you want the result to be represented. Since the question is “without using any floating point arithmetic”, you should start by defining that. It comes before any explanation or algorithm. – Pascal Cuoq Jun 12 '14 at 13:21
  • @mafso I think you mean 10000. – Pascal Cuoq Jun 12 '14 at 13:23
  • [here](http://stackoverflow.com/questions/16532697/finding-a-square-root-using-only-integers) – Yann Jun 12 '14 at 13:24
  • @PascalCuoq. Of course, thanks for correction! – mafso Jun 12 '14 at 13:24
  • "... I don't want to discard precision from the output" - you are aware that e.g. `sqrt(3)` would require infinite precision on a base-2 system, whether or not you use floating point, right? You're going to have to round off results to some precision. But if you don't want to use floating point, perhaps a suitable fixed-point algorithm would be what you want... Although on today's hardware, I'm not sure how much performance benefit that would have over native floating point... – twalberg Jun 12 '14 at 14:06
  • @twalberg - Obviously I can't store infinite precision, so discussing that is a moot point. Again, I stated "at least two significant digits", so I'm clearly accepting at 3.00. As far as getting any performance benefit, that's not what I'm trying to achieve here. – Michael Yousef Jun 12 '14 at 14:28
  • 1
    to get a better rounded result, multiply by 1000^2 to get 3 decimal digits and round – phuclv Jun 12 '14 at 14:40

1 Answers1

0

You can calculate an integer numerator and an integer denominator, such that the floating-point division of the numerator by the denominator will yield the square root of the input number.

Please note, however, that no square-root method exists such that the result is 100% accurate for every natural number, as the square root of such number can be an irrational number.

Here is the algorithm:

Function (input number, input num_of_iterations, output root):
    Set root.numerator   = number
    Set root.denominator = 1
    Run num_of_iterations:
        Set root = root-(root^2-number)/(root*2)

You might find this C++ implementation useful (it also includes the conversion of the numerator divided by the denominator into a numerical string with predefined floating-point precision).

Please note that no floating-point operations are required (as demonstrated at the given link).

barak manos
  • 29,648
  • 10
  • 62
  • 114
  • 1
    That algorithm does seem to converge pretty quickly, but the extended precision integers are critical to it even working, and the numbers seem to quickly become relatively prime, which means they tend to get huge after a few iterations (e.g. `sqrt(42)` invokes relatively prime numbers on the order of 10^223 by iteration 8, although iteration 7 is already accurate to 10 decimal places), so performance may not be great if you are going for high accuracy... – twalberg Jun 12 '14 at 16:24
  • @twalberg: From my experience, 4 iterations are in most cases sufficient for achieving a pretty good accuracy at a relatively low performance cost. You may set the initial value of `numerator` to `2^BitCount(number)` in order to get a "better starting point" (I tried to keep it simple, so I set it to the value of `number` instead). Of course, the use of some kind of `BigInteger` class is inevitable here. – barak manos Jun 12 '14 at 16:33