The One Man MMO Project

The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary

The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary

Looking for a Fast Square Root

Last night I needed a square root function that would work on 64-bit unsigned integers. I have been using the standard library's *sqrt*, but my first thought was that an integer square root could be faster.

I looked around and found what was said to be a "fast" integer square root on Stack Overflow by Craig McQueen. I used the code as-is except that I changed it to use 64-bit unsigned ints because that was what I needed.

It seemed like a reasonably performance efficient algorithm, but I had always heard that sqrt, even in hardware, was slow. Because sqrt gets used a lot, I thought better safe than sorry, so this morning I decided to benchmark the integer algorithm against *sqrt* just to be sure.

- Int Elapsed 1506419us
- Float Elapsed 159330us
- Float+Cast Elapsed 182160us

It turns out that the hardware-based floating point

I'll keep the integer square root, but this post is going in the comments for it.

We were unable to retrieve our cookie from your web browser. If pressing F5 once to reload this page does not get rid of this message, please read this to learn more.

**You will not be able to post until you resolve this problem.**

Copyright (C)2009-2018 onemanmmo.com. All Rights Reserved

Homepage: www.onemanmmo.com email:one at onemanmmo dot com

Int Elapsed 571950us

Float Elapsed 38746us

Float + Cast Elapsed 56759us

Float is 14.76x faster, 10.08x with the static_cast.

Also, this was not the timing for one sqrt, but 4,000,000.

Homepage: omeg.pl email:

Sqrt float: 12583.508ms

Sqrt double: 12371.292ms

Fast uint sqrt: 24388.667ms

Fast ulong sqrt: 96830.309ms

That's for 1e9 loops with adding all sqrts together to prevent optimizer from ignoring the values. Also did the same test in C# for fun:

Sqrt double: 13547ms

Fast uint sqrt: 25701ms

Fast ulong sqrt: 121126ms

Not much difference. :)

Homepage: omeg.pl email:

Homepage: www.onemanmmo.com email:one at onemanmmo dot com