Calculate square root of a BigInteger (System.Numerics.BigInteger)

by

Check if BigInteger is not a perfect square has code to compute the integer square root of a Java BigInteger. Here it is translated into C#, as an extension method.

    public static BigInteger Sqrt(this BigInteger n)
    {
        if (n == 0) return 0;
        if (n > 0)
        {
            int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2)));
            BigInteger root = BigInteger.One << (bitLength / 2);

            while (!isSqrt(n, root))
            {
                root += n / root;
                root /= 2;
            }

            return root;
        }

        throw new ArithmeticException("NaN");
    }

    private static Boolean isSqrt(BigInteger n, BigInteger root)
    {
        BigInteger lowerBound = root*root;
        BigInteger upperBound = (root + 1)*(root + 1);

        return (n >= lowerBound && n < upperBound);
    }

Informal testing indicates that this is about 75X slower than Math.Sqrt, for small integers. The VS profiler points to the multiplications in isSqrt as the hotspots.

More Related Contents:

  1. Big integers in C#
  2. BigInteger to Hex/Decimal/Octal/Binary strings?
  3. working with incredibly large numbers in .NET
  4. Where is my System.Numerics namespace?
  5. byte[] to unsigned BigInteger?
  6. How can I use bigint with C#?
  7. How to convert it to string back? [closed]
  8. What does “myBody.velocity.y” mean? [closed]
  9. Get property value from string using reflection
  10. LINQ : Dynamic select
  11. Await on a completed task same as task.Result?
  12. A field initializer cannot reference the non-static field, method, or property?
  13. When should I use Async Controllers in ASP.NET MVC?
  14. How to use a WSDL
  15. unable to cast COM object of type ‘microsoft.Office.Interop.Excel.ApplicationClass’ to ‘microsoft.Office.Interop.Excel.Application'”
  16. What is the “right” way to bring a Windows Forms Application to the foreground?
  17. how to stop flickering C# winforms
  18. Pass multiple complex objects to a post/put Web API method
  19. CompositeCollection + CollectionContainer: Bind CollectionContainer.Collection to property of ViewModel that is used as DataTemplates DataType
  20. Looking for an example of a custom SynchronizationContext (Required for unit testing)
  21. Cannot delete file when used in DataContext
  22. How to check if a socket is connected/disconnected in C#?
  23. How to convert object to Dictionary in C#?
  24. Query XDocument with xmlns attribute (namespace)
  25. What is the easiest way to do inter-process communication (IPC) in C#? [closed]
  26. What is nullable type in c#?
  27. Entity Framework Code First: How can I create a One-to-Many AND a One-to-One relationship between two tables?
  28. Conditional dependency resolver on run-time (.net Core)
  29. Which objects can I use in a finalizer method?
  30. Can I reuse HttpWebRequest without disconnecting from the server?

Leave a Comment