title: SCALA: Function for Square root of BigInt
body: <p>I searched internet for a function to find exact square root of BigInt using scala programming language. I didn't get one, But saw one Java Program and I converted that function into Scala version. It is working but I am not sure, whether it can handle very large BigInt. But it returns BigInt only. Not BigDecimal as Square Root. It shows there is some bit manipulation done in the code with some hard coding of numbers like <code>shiftRight(5), BigInt("8") and shiftRight(1)</code>. I can understand the logic clearly, But not the hard coding of these bitshift numbers and the number 8. May be these bitshift functions are not available in scala, and thats why it is needed to convert to java BigInteger at few places. These hard coded numbers may impact the precision of the result.I just changed the java code into scala code just copying the exact algorithm. And here is the code I have written in scala: </p>
  
  <pre><code>   def sqt(n:BigInt):BigInt = {
        var a = BigInt(1)
        var b = (n&gt;&gt;5)+BigInt(8)
        while((b-a) &gt;= 0) {
            var mid:BigInt = (a+b)&gt;&gt;1
            if(mid*mid-n&gt; 0) b = mid-1
            else a = mid+1
           }
        a-1
     }
  </code></pre>
  
  <p>My Points are:</p>
  
  <ol>
  <li>Can't we return a BigDecimal instead of BigInt? How can we do that?</li>
  <li>How these hardcoded numbers <code>shiftRight(5), shiftRight(1) and 8</code> are related 
  to precision of the result.</li>
  </ol>
  
  <p>I tested for one number in scala REPL: The function <code>sqt</code> is giving exact square root of the squared number. but not for the actual number as below:</p>
  
  <pre><code>scala&gt; sqt(BigInt("19928937494873929279191794189"))
  res9: BigInt = 141169888768369
  
  scala&gt; res9*res9
  res10: scala.math.BigInt = 19928937494873675935734920161
  
  scala&gt; sqt(res10)
  res11: BigInt = 141169888768369
  
  scala&gt;
  </code></pre>
  
  <p>I understand <code>shiftRight(5) means divide by 2^5 ie.by 32 in decimal</code> and so on..but why 8 is added here after shift operation? why exactly 5 shifts? as a first guess?</p>