CODEWITHSUNDEEP
c#square-root
J Fabian Meier
J Fabian Meier

Reputation: 35795

Fast Integer Square Root

Is there any faster or more direct way of computing the integer square root:

http://en.wikipedia.org/wiki/Integer_square_root

in C# as

private long LongSqrt(long value)
{
    return Convert.ToInt64(Math.Sqrt(value));
}

?

Upvotes: 7

Views: 9714

Answers (3)

Reroute
Reroute

Reputation: 273

If you can live with a small absolute error, you will struggle to beat this (error term grows 1 bit per every odd power of 2 above 9)

uint16_t sqrtFav(uint32_t num) {
    if (num == 0) {
        return 0;
    }
    uint8_t bitpos = (32 - __builtin_clzl(num)) >> 1; // Find the (MSB + 1) / 2
    return ((num >> (bitpos + 1)) + (1 << (bitpos - 1))); // offseting bitpos to remove the need to average
}

This is my own creation reached while trying to optimize for motion control acceleration curves, where relative error matters more than absolute.

The clz can be replaced with whichever compilers built in you prefer, its just a quick way to reach it on the AVR platform I was developing for.

Its constant time on micro controllers with a barrel shifter, and relatively cheap on any that lack them, under 200 cycles for the full uint32_t range on an 8 bit AVR,

You can scale the variable sizes for 64, 128bit, etc,

Upvotes: -1

SunsetQuest
SunsetQuest

Reputation: 8817

(Years late but maybe this will help someone else. However, I have spent some time on this topic.)

Fastest approximate square root (just like the one listed)...

// ApproxSqrt - Result can be +/- 1
static long ApproxSqrt(long x)
{
    if (x < 0)
        throw new ArgumentOutOfRangeException("Negitive values are not supported.");

    return (long)Math.Sqrt(x);
}

If you want something that would be accurate to all 64 bits...

// Fast Square Root for Longs / Int64 - Ryan Scott White 2023 - MIT License
static long Sqrt(long x)
{
    if (x < 0)
        throw new ArgumentOutOfRangeException("Negitive values are not supported.");

    long vInt = (long)Math.Sqrt(x);
    if (vInt * vInt > x)
        vInt--;
    return vInt;
}

For ulong / UInt64 ...

// Fast Square Root for Unsigned Longs - Ryan Scott White 2023 - MIT License
static ulong Sqrt(ulong x)
{
    ulong vInt = (ulong)Math.Sqrt(x);
    ulong prod = vInt * vInt;
    if (prod > x || prod == 0)
        vInt--;
    return vInt;
}

Upvotes: 2

Thomas Jungblut
Thomas Jungblut

Reputation: 20969

If you know the range in advance you can create a lookup index for a squared value and its integer square root.

Here is some simple code:

// populate the lookup cache
var lookup = new Dictionary<long, long>();
for (int i = 0; i < 20000; i++)
{
    lookup[i * i] = i;
}

// build a sorted index
var index = new List<long>(lookup.Keys);
index.Sort();

// search for a sample 27 
var foundIndex = index.BinarySearch(27);
if (foundIndex < 0)
{
    // if there was no direct hit, lookup the smaller value
    // TODO please check for out of bounds that might happen
    Console.WriteLine(lookup[index[~foundIndex - 1]]);
}
else
{
    Console.WriteLine(lookup[foundIndex]);
}

// yields 5

You can get around the dictionary lookup by creating a parallel second list, if you want it to be more efficient.

Upvotes: 3

Related Questions