fork download
copy 
  1.  
  2. using System;
  3.  
  4. public class IntegerSquareRoot
  5. {
  6.     public static long IntegerSqrt(long n)
  7.     {
  8.         if (n < 0)
  9.             throw new ArgumentOutOfRangeException(nameof(n), "Input must be non-negative.");
  10.         if (n == 0 || n == 1)
  11.             return n;
  12.  
  13.         // Initial guess using MathF.ReciprocalSqrtEstimate
  14.         float reciprocalSqrtEstimate = MathF.ReciprocalSqrtEstimate((float)n);
  15.         float initialGuess = 1.0f / reciprocalSqrtEstimate;
  16.  
  17.         // Refine the guess using Newton-Raphson iterations
  18.         double guess = initialGuess;
  19.         for (int i = 0; i < 5; i++) // 5 iterations for better precision with long
  20.         {
  21.             guess = (guess + n / guess) * 0.5;
  22.         }
  23.  
  24.         // Convert the refined guess to a long
  25.         long result = (long)guess;
  26.  
  27.         // Ensure the result is correct
  28.         if (result * result > n)
  29.             result--;
  30.         return result;
  31.     }
  32.  
  33.     public static void Main()
  34.     {
  35.         // Test cases
  36.         Console.WriteLine(IntegerSqrt(0));  // Output: 0
  37.         Console.WriteLine(IntegerSqrt(1));  // Output: 1
  38.         Console.WriteLine(IntegerSqrt(2));  // Output: 1
  39.         Console.WriteLine(IntegerSqrt(3));  // Output: 1
  40.         Console.WriteLine(IntegerSqrt(4));  // Output: 2
  41.         Console.WriteLine(IntegerSqrt(5));  // Output: 2
  42.         Console.WriteLine(IntegerSqrt(48)); // Output: 6
  43.         Console.WriteLine(IntegerSqrt(49)); // Output: 7
  44.         Console.WriteLine(IntegerSqrt(9223372036854775807)); // Output: 3037000499
  45.     }
  46. }
  47.  
Success #stdin #stdout 0.06s 28788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
1
1
1
2
2
6
7
3037000499
https://ideone.com/CI1P4K
language:
C# (NET 6.0)
created:
156 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!