Square root for BigInteger in F# (taken from http://www.codeproject.com/KB/recipes/BigIntSqrRoot.aspx)

BigIntSqrt.fs

module Roots



open System

open System.Numerics



//*************************************************************************************

// Here are some constant BigIntegers to help with the log10 function.

let ten = 10I  // 10^1

let tenBillion = 10000000000I // 10^10

let googol = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000I // 10^100

let googolToTenth = googol * googol * googol * googol * googol * googol * googol * googol * googol * googol // 10^10000



//*************************************************************************************

// Take the integer logarithm of theNumber, base 10. 

let private log10 theNumber =

    if theNumber <= 0I then

        failwith "Logarithm of a non-positive number is not defined."

    // this inner functions counts the number of times divisor will divide num

    let rec divisions count (num : BigInteger) divisor =

        match num with

        | x when x < divisor -> count, num

        | _ -> divisions (count + 1I) (num / divisor) divisor

    let thousandsCount, rem1 = divisions 0I theNumber googolToTenth

    let hundredsCount, rem2 = divisions 0I rem1 googol

    let tensCount, rem3 = divisions 0I rem2 tenBillion

    1000I * thousandsCount + 100I * hundredsCount + ten * tensCount + fst(divisions 0I rem3 10I)





//*************************************************************************************

// Raises 10I to the power of a specified value.

// Warning: Be careful with passing in a value over 100000I (hundred thousand).

//          It could take a long time to complete.

// (BigInteger -> BigInteger)

let private power10 (exponent : BigInteger) =

    if exponent.Sign = -1 then

        0I

    else

        let rec expox (product : BigInteger) (pow : BigInteger) multiplier log10OfMult =

            match pow with

            | x when x < log10OfMult -> product, pow

            | _ -> expox (product * multiplier) (pow - log10OfMult) multiplier log10OfMult

        let pow10To1000, rem1 = expox 1I exponent googolToTenth 1000I

        let pow10To100, rem2 = expox 1I rem1 googol 100I

        let pow10To10, rem3 = expox 1I rem2 tenBillion 10I

        pow10To1000 * pow10To100 * pow10To10 * fst(expox 1I rem3 10I 1I)





//*************************************************************************************

// Take the integer square root of a specified value.

// Because this is dealing with integers the answere is truncated.

// An exception occurs if you pass in a negative value.

// (BigInteger -> BigInteger)

let bigintSqrt(bigNum : BigInteger) =

    let sqrtRoughGuess (num : BigInteger) =

        let log10x = log10 (num + 1I)

        let halfLog = (log10x + 1I) >>> 1

        (power10 halfLog)

    let rec converge prevGuess =

        let nextGuess = (bigNum / prevGuess + prevGuess) >>> 1

        match BigInteger.Abs (prevGuess - nextGuess) with

        | x when x < 2I -> nextGuess

        | _ -> converge nextGuess

    if bigNum.Sign = -1 then

        failwith "Square root of a negative number is not defined."

    else

        let root = converge (sqrtRoughGuess bigNum)

        if root * root > bigNum then

            root - 1I

        else

            root