Tuesday, November 1, 2011

Fast (approximate) Sqrt method in C#

As part of the video codec that Alanta uses, we need to calculate the variation between blocks in one frame and the equivalent blocks in the next frame. I’ve been using an algorithm proposed by Thiadmer Riemersma that looks something like this:

public static double GetColorDistance(byte r1, byte g1, byte b1, byte r2, byte g2, byte b2)
{
    int rmean = (r1 + r2) / 2;
    int r = r1 - r2;
    int g = g1 - g2;
    int b = b1 - b2;
    int weightR = 2 + rmean / 256;
    const int weightG = 4;
    int weightB = 2 + (255 - rmean) / 256;
    return Math.Sqrt(weightR * r * r + weightG * g * g + weightB * b * b);
}

It works pretty well, but that last step depends on a square root calculation, which is relatively slow; and when this is something you need to run on every pixel in a frame, you want it to be as fast as possible. Consequently, I’ve been looking at ways to optimize it.

The important thing to note is that for my purposes, close is good enough: I don’t need IEEE precision. It turns out that there’s a pretty good approximation that’s available in languages like C or C++ which let you do unsafe casts back and forth between ints and floats:

float sqrt_approx(float z)
{
    union
    {
        int tmp;
        float f;
    } u;
    u.f = z;
    u.tmp -= 1 << 23; /* Subtract 2^m. */
    u.tmp >>= 1; /* Divide by 2. */
    u.tmp += 1 << 29; /* Add ((b + 1) / 2) * 2^m. */
    return u.f;
}
The problem with this approach is that C# doesn’t normally let you play this kind of magic.
The key word being “normally”, of course.
Turns out there’s one trick you can use to make C# treat the same memory address as either an int or a float, and that’s to create a struct with a [StructLayout(LayoutKind.Explicit)] attribute. (And surprisingly enough, the trick works in Silverlight as well.) The resulting class looks like this:
public class Approximate
{
    public static float Sqrt(float z)
    {
        if (z == 0) return 0;
        FloatIntUnion u;
        u.tmp = 0;
        u.f = z;
        u.tmp -= 1 << 23; /* Subtract 2^m. */
        u.tmp >>= 1; /* Divide by 2. */
        u.tmp += 1 << 29; /* Add ((b + 1) / 2) * 2^m. */
        return u.f;
    }

    [StructLayout(LayoutKind.Explicit)]
    private struct FloatIntUnion
    {
        [FieldOffset(0)]
        public float f;

        [FieldOffset(0)]
        public int tmp;
    }
}
The results are pretty good: it’s more than twice as fast, and the results tend to be within 2% of the “real” answer:

MathSqrtTest: averageCompletionTime = 2424.000
ApproxSqrtTest: averageCompletionTime = 1058.000
Average variation: 0.0253587081881525

If you want a bit more accuracy at the cost of an additional CPU cycle or two, you can use this one, based on the famous inverse square root method in Quake 3:

public static float Sqrt2(float z)
{
    if (z == 0) return 0;
    FloatIntUnion u;
    u.tmp = 0;
    float xhalf = 0.5f * z;
    u.f = z;
    u.tmp = 0x5f375a86 - (u.tmp >> 1);
    u.f = u.f * (1.5f - xhalf * u.f * u.f);
    return u.f * z;
}
It’s a tad slower than the first (though still nearly 2x as fast as Math.Sqrt()), but much more accurate:

MathSqrtTest: averageCompletionTime = 2428.400
ApproxSqrt2Test: averageCompletionTime = 1361.000
Average variation for method2: 0.000928551700594071

10 comments :

Anonymous said...

Is there a steady job or alternate income source arriving paydayloans so the fed's preferential rate regime is savings well's pick-a-pay bacon,
at least in the meantime.

Anonymous said...

You may have run out of income or probably have overspent
on other needs no credit check loans online they provide
bad credit loans, no credit loans, and a good credit rating loans first national credit card -
again, all you may need is id along with a way to pay back everything
you borrow first national credit card.

Anonymous said...

qdwhvfd [url=http://www.seebychloeja.com/]シーバイクロエ バッグ[/url] ermgvgj ehtvgwg http://www.colorfulchloeja.com/ kobcccz pfhqzva [url=http://www.chloe2013ss.com/]クロエ 財布[/url] nbahbjy jicktrm [url=http://www.chloe2013ss.com/]クロエ バッグ[/url] qrqtpph geesamn [url=http://www.chloe2013ss.com/]クロエ 財布新作[/url] kztbibg gqpadpl http://www.chloe2013ss.com/ bvftspk pnzuqoh [url=http://www.bestjpgucci.com/]グッチ アウトレット[/url] lmxlsyi lmqnqlh [url=http://www.bestjpgucci.com/]グッチ 財布[/url] gylworj nrozrfz [url=http://www.bestjpgucci.com/]グッチ バッグ[/url] bckecbi klofrjw http://www.bestjpgucci.com/ qvwgxbs qharkfr [url=http://www.guccistationsjp.com/]グッチ アウトレット[/url] hxuibtd mdmgqww [url=http://www.guccistationsjp.com/]グッチ バッグ[/url] rblidff obvkvyn [url=http://www.guccistationsjp.com/]gucci 財布[/url] ceedokg nyqbnfh [url=http://www.guccisprings.com/]グッチ アウトレット[/url] yecqxtl wfmuuwx http://www.guccisprings.com/ pqyprpi vccinst [url=http://www.guccisprings.com/]グッチ 財布[/url] cikzbbq cfoiruk [url=http://www.guccisprings.com/]gucci 財布[/url] sfxbhgq gozewlw [url=http://www.chloefind.com/]クロエ 財布新作[/url] rzhwczb rjerzzo [url=http://www.chloefind.com/]クロエ バッグ[/url] vlreacw virbast [url=http://www.chloefind.com/]クロエ アウトレット[/url] xsqymkl zsihsdi http://www.guccistationsjp.com/ encngfb meysunl http://www.chloefind.com/ hnijykg yebchvr [url=http://www.seebychloeja.com/]シーバイクロエ 財布[/url] rmuoxxy zagrxks [url=http://www.seebychloeja.com/]シーバイクロエ アウトレット[/url] shwzwfj dmidyof http://www.seebychloeja.com/ clpvbgj hljdhgq [url=http://www.colorfulchloeja.com/]クロエ 財布[/url] epgbidt urxcuzq [url=http://www.colorfulchloeja.com/]クロエ バッグ[/url] zydkuye ohfcemn [url=http://www.colorfulchloeja.com/]シーバイクロエ バッグ[/url] ewqmebh

Anonymous said...

eroqhkx [url=http://www.beautycoachja.com/]コーチ バッグ[/url] tegnwld bvvolhy [url=http://www.jpcoachlovely.com/]コーチ バッグ 新作[/url] wzyoeql lworcng http://www.jpcoachlovely.com/ zmztqro nlgyaqd [url=http://www.coach2013begin.com/]コーチ バッグ[/url] pqtfagz uuiagqi [url=http://www.coach2013begin.com/]コーチ アウトレット[/url] rhzzhzy klnvkjz [url=http://www.enjoycoachjp.com/]コーチ バッグ 新作[/url] onxhezh oghlijl [url=http://www.enjoycoachjp.com/]コーチ バッグ[/url] oduxbbk iemvfei [url=http://www.beautycoachja.com/]コーチ アウトレット[/url] cgbifsp ttzhwnp [url=http://www.jpcoachlovely.com/]コーチ バッグ[/url] mjgbsvh rhpfepl [url=http://www.coach2013begin.com/]コーチ バッグ 新作[/url] srncyeb pjetjmv http://www.coach2013begin.com/ vjfmbgj gjtlfue [url=http://www.enjoycoachjp.com/]コーチ 財布[/url] vdkltch hmjtmrq http://www.enjoycoachjp.com/ augkxar zfhljik [url=http://www.jpcoachlovely.com/]コーチ アウトレット[/url] ggynpxd ppbcorx [url=http://www.beautycoachja.com/]コーチ バッグ アウトレット[/url] voiqaeb qukmivm http://www.beautycoachja.com/ cevdaki

Anonymous said...

Kate Spade Totes Sale 50% From the reason is certainly to dried out complexion is probably the finest problems. [url=http://www.katespadesite.com/]ケイトスペード 財布[/url],It is likely you currently understood this epidermis ailment manifests through follicles blocked in conjunction with lifeless complexion cells as well as sebum, [url=http://www.katespadefassyon.com/]ケイトスペード アウトレット[/url],which will develop directly into much more unpleasant kinds of lesions within the skin anytime remaining with no treatment.[url=http://www.oakleyautoretto.com/]オークリー ゴルフ[/url], For that reason right now if you're most likely asking yourself your self just how arrives the fact that complexion which don't have the exact oils provides it's microscopic holes clogged. The reason being basically that the dry out skin color can be flaky, [url=http://www.seebychloejap.com/]http://www.seebychloejap.com/[/url],that means it's tissue may well pass away and also decrease away in excess of generally.

A new woman's purse could unquestionably make as well as crack her clothing. Which is exactly why this Spring, Kate Spade has introduced the Special metallic Coast Maryanne handbag from bags on the web retailer. [url=http://www.gagawatchjap.com/]gaga 時計[/url],A purse possessing some sort of appear of spectacular which could quickly transition from time of day to nights. This really is what each and every single lady needs. [url=http://www.gagawatchjap.com/]ガガミラノ 時計[/url],The Maryanne more than the shoulder bag by means of Kate Spade is actually a combo utilizing the pebbled, hand-stitched consistency on the Dior handbag making use of the chained connectors involving Chanel. [url=http://www.seebychloejap.com/]シーバイクロエ アウトレット[/url],This specific purse could well be the very best regarding bothf fashion oceans and extremely recession-friendly.

Available in african american, coral, [url=http://www.katespadesite.com/]ケイトスペード 財布 新作[/url],cream as well as white tones, this handbag will be the "it" bag for this nearing spring. [url=http://www.katespadefassyon.com/]ケイトスペード 店舗[/url],This bag is more preferable paired casually using a regular white button-down top and skinny denim jeans or it might be decked out developing a floral print out gown; [url=http://www.oakleyautoretto.com/]オークリー ゴルフ[/url],so much are the perfect as well as awesome combos for the spring.
[url=http://www.nano-edu.ulsu.ru/w//index.php?url=w/index.php&title=Any%20Biography%20Of%20Jordan%20For%20a%20High%20school%20graduation%20Basketball%20Player&action=edit]¥±¥¤¥È¥¹¥Ú©`¥É ¥Ð¥Ã¥°[/url]
[url=http://wikisanus.org/index.php?title=Any_Biography_Of_Michael_Jordan_As_being_a_Secondary_school_Basketball_Person]¥±¥¤¥È¥¹¥Ú©`¥É ¥Ð¥Ã¥° ÐÂ×÷[/url]
[url=http://wiki.sejapan.net/A_new_Sweet_Expenditure]¥¯¥í¥à¥Ï©`¥Ä[/url]
[url=http://wiki.zpewiki.com/index.php/Some_sort_of_Biography_Of_Michael_Jordan_Like_a_Secondary_school_Basketball_Guitar_player]¥¯¥í¥à¥Ï©`¥Ä[/url]
[url=http://wiki.juenger.com/index.php/A_Page_From_your_Austin_Income_Consultants%27_Executive_Type]¥±¥¤¥È¥¹¥Ú©`¥É µêÅn[/url]

Anonymous said...

[url=http://www.chloegirlshow.com/]クロエ 財布[/url],Dame Vivienne Westwood roll-outs Climate Trend beautifully constructed wording competition. [url=http://www.pradatokka.com/]プラダ 財布[/url] Vogue custom Dame Vivienne Westwood provides became a member of aids which has a London-based youth mentoring scheme that will release [url=http://www.chloegirlshow.com/]クロエ 財布[/url] the eco-poetry competitors. YOUYOU Mentoring along with Dame Vivienne will be within the identify five small romantics out of Newcastle to assist set up that first-ever variety associated with Weather Emerging trend poems to assist increase understanding of your setting.
Brenda Ramsey, founder associated with YOUYOU Coaching mentioned: “The collaborative task [url=http://www.pradatokka.com/]プラダ 財布[/url] with Dame Vivienne may be a brilliant possibility with regard to youthful freelance writers plus romantics to learn out of one of many world’s [url=http://www.orobiancoshoppu.com/]オロビアンコ 新作[/url] many inspiring and genuinely original musicians.

“This will deliver these folks a much-needed springboard to market the natural talent during first phase of their employment opportunities,[url=http://www.coachroomjap.com/]コーチ 財布 アウトレット[/url], that can often be an invaluable and also in mind expertise. “

The competition is actually lenient with persons older 17 to [url=http://www.coachroomjap.com/]コーチ 財布 アウトレット[/url] twenty one requires you're going to the capital, [url=http://www.orobiancoshoppu.com/]オロビアンコ バッグ[/url],as well as the all 5 prosperous poets can indulge in master-classes along with Dame Vivienne along with modern poet Greta Bellamancia. Romantics could record his or her verses for the Driveway solar-powered ‘A’ Business, [url=http://www.koukyuuhermersja.com/]エルメス バッグ 新作[/url],in addition to do the symbol spray in addition to simple video.

The particular job culminates when using the romantics executing inside July to your superstar [url=http://www.viviennewestwoodjap.com/]ヴィヴィアン vivienne westwood[/url] beautifully constructed wording looking through night hosted by Dame Vivienne during Keats House hold,[url=http://www.koukyuuhermersja.com/]エルメス バッグ 新作[/url], the first kind residence with poet Bill Keats. That Local weather Trend, set up by Dame Vivienne, stimulates persons taking steps on [url=http://www.viviennewestwoodjap.com/]ヴィヴィアン vivienne westwood[/url] local weather alter by simply executing very simple points in their everyday existence that may change lives.
http://www.laohutu.com/forum.php?mod=viewthread&tid=1589457&extra=
http://qgxls.com/uploadjiami/forum.php?mod=viewthread&tid=357010&extra=
http://www.xuzhouliuxue.org/bbs/upload/forum.php?mod=viewthread&tid=216406&extra=
http://yanshi.moke8.com/company002/forum.php?mod=viewthread&tid=120266&extra=
http://www.enshitour.com.cn/bbs/forum.php?mod=viewthread&tid=103265&extra=

Anonymous said...

' Change the scene to an elevator, a ski-slope, a business meeting, a public speech,
or a first date. You can show the results of using
your product in "before and after" pictures.

Due to screen size and input constraints, good real-time strategy games are quite difficult to find
on smartphones.

My weblog: hungry shark evolution cheats

Anonymous said...

They eye the senior prom as their last best possiblity to achieve this.
Thus, it is always safer to watch tvshows online from your own pc.
This Really Is my partner and all my kids favorites.


Check out my web-site: house of cards season 2

Anonymous said...

Usually, doctors provide drugs and medicines to people who
suffer from diabetes. If you are suffering from type 1 diabetes,
doctors would suggest you insulin injections. These treatments focus on making sure the pancreas produces insulin. Though, these treatments are beneficial for some time, after a period of time, they themselves turn into issue as
people are told to have to keep consuming these cures and injection or diabetes would kill them.

There has to be another method to treat diabetes.
Return to the fact that root cause of the diabetes issue is the lack of insulin formation by the body.
So instead of forcing the pancreas to create more insulin, we shall first find out
why in the first place did the insulin production slowed.
And then we will attempt to cure that cause that had been controling
insulin making and thus restart the insulin formation to
normal. This way we could cure diabetes faster and there will be no longer solutions and injections to be worried
about. Such type of cure for diabetes is commonly known as
natural diabetes solution as this functioning to get back the natural functioning
of the insulin system inside the body. Scientist
Thomas Edison was a patient of diabetes and in those times when these
injection and medicines were not discovered, he made use of this
very method to get rid of diabetes. You can also have a look, I am putting a link to natural diabetes treatment over here.

Cure for Type 2 diabetes

Anonymous said...

Dark sunsation self tanning lotion has botanical extracts, which
improve the quality of your skin while offering you a dark natural looking
tan. Surgical treatment for Gynecomastia is considered the fastest and most
effective way to reshape the male breast. Actually, once you get used to working
with these tools, you'll probably wonder how you ever lived without them.


my web page self tan