Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
private unsafe static BigInteger Sqrt(BigInteger num, BigInteger n)
{
var squaresUnder100 = new Dictionary<int, int> { { 1, 1 }, { 2, 4 }, { 3, 9 }, { 4, 16 }, { 5, 25 }, { 6, 36 }, { 7, 49 }, { 8, 64 }, { 9, 81 } };
var pairCount = 0;
var pairs = GetSqrtPairs(num, out pairCount);
// Find the largest integer whose square is smaller than or equal to the current pair.
var pairSq = (BigInteger)1;
foreach (var sq in squaresUnder100)
{
if (sq.Value <= pairs[0])
{
pairSq = sq.Key;
}
else
{
break;
}
}
// Check if we only want the first digit.
if (n == 1)
{
return pairSq;
}
var currentRes = (BigInteger)pairSq;
var i = 0;
var z = squaresUnder100[(int)pairSq] - currentRes; z = z == 0 ? 1 : 0;
var currentDigits = 1;
while (true)
{
var a = (z * 100) + pairs[i + 1];
var y = currentRes * 20;
var x = 0;
for (var k = 1; k < 10; k++)
{
if ((y + k) * k <= a)
{
x = k;
}
else
{
break;
}
}
z = a - ((y + x) * x);
// Update current output.
currentRes *= 10;
currentRes += x;
currentDigits++;
// Check if we've reached the desired accuracy, and return if so. Otherwise, continue calculating...
if (currentDigits == n)
{
Marshal.FreeHGlobal((IntPtr)pairs);
return currentRes;
}
if (i + 2 != pairCount)
{
i++;
}
}
}
private unsafe static byte* GetSqrtPairs(BigInteger num, out int pairCount)
{
var data = num.ToString();
if (data.Length % 2 != 0)
{
data = "0" + data;
}
var pairsStn = Regex.Split(data, @"(\d{2})").Where(pair => !String.IsNullOrEmpty(pair)).ToArray();
var ptr = (byte*)Marshal.AllocHGlobal(pairsStn.Length + 2 + 4);
for (var i = 0; i < pairsStn.Length; i++)
{
ptr[i] = Byte.Parse(pairsStn[i]);
}
ptr[pairsStn.Length] = 0;
ptr[pairsStn.Length + 1] = 0;
pairCount = pairsStn.Length + 2;
return ptr;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.