旧闻一则:神秘的0x5f3759df 不可思议的Quake III源码

    Quake III公开源码后,有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒,经测试这段代码比(float)(1.0/sqrt(x))快4倍:
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

    code/common/cm_trace.c中也出现了这样一段解释sqrt(x)的函数,与上面的代码唯一不同的就是这个函数返回的是number*y:
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return number * y;
}

    这样的代码速度肯定飞快,我就不用多说了;但算法的原理是什么呢?其实说穿了也不是很神,程序首先猜测了一个接近1/sqrt(number)的值,然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 – a = 0的一个正实根,它的导数是-2/x^3。运用牛顿迭代公式x' = x – f(x)/f'(x),式子化简为x' = x * (1.5 – 0.5a * x^2)。迭代几次后,x的值将趋于1/sqrt(a)。
    但这段代码真正牛B的是那个神秘的0x5f3759df,因为0x5f3759df – (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的,只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事,很少有人说得清楚。这篇论文比较科学地解释了这个常数。

37 条评论

  • dpupet

    我来抢板凳,Matrix牛还没有回复我的问题呢,[sad],乘法口诀后的留言。

  • x2studio

    呃。0x5f375a86似乎更厉害呢。

  • Freeze

    (1.0/sqrt(x)
    括号不匹配……

    回复:谢谢指正,已改正

  • dahe_1984

    Q_rsqrt(4)=0.499154;
    1.0/sqrt(4)=0.500000。不知道对精度是怎么看待的?

  • deoxyz

    回ls…0.1%的精度对于quake3完全够用,毕竟只是求一个向量正交化
    另外我把那篇文章翻译了一下
    http://www.seraphy.cn/blog/article.asp?id=17
    最后面有pdf格式下载
    有兴趣去看一下吧

  • 闲耘

    有趣,又迷上数学了。
    另外,似乎有另一种防垃圾评论的方式,就是判断内容里的链接数量和连续的评论内容相似度。刚刚不知道是因为数学不好,还是超时而被拒绝了。[lol]

  • TX

    您好。看了几篇文章,很有启发!尤其是位运算的。

    我有点疑问?是怎么样判断代码的执行效率的呢?几倍或是什么的?
    有什么工具,或者是?

    抱歉,本人新来乍到,还在为Noip奋斗着……
    能否请教,针对Noip,或者根高,该怎么样提高呢?

  • 阿羽

    其实卡马克也是通过暴力方法得到这个常数的

  • coder

    请问 这句得到的是什么 i = * ( long * ) &y;

  • wecing

    不要告诉我这段代码是卡马克本人写的,这不是他本人写的,这不是……

  • 可惜君

    对6楼提到的翻译过的论文很感兴趣,可惜链接点不开了…
    可惜可惜…

  • amorphobia

    昨天在研究这个。。。

  • 膜拜啊

    牛,真是太牛了

  • nb

    csdn上的确有……

  • yc0576

    我测试了一下,神奇的是double下还是(float)(1.0/sqrt(i*1.0f));这个快

  • 不对

    Function InvSqrt(x#):Dim xhalf#,i&:xhalf=x/2:i=&H5F3759DF-x2:x=i*(1.5-xhalf*x*x):InvSqrt=x:End Function
    Private Sub Form_Load():MsgBox InvSqrt(4):End Sub
    10duowei

  • picospuch

    真…神奇!

  • cervelo

    抱歉,本人新来乍到,还在为Noip奋斗着…

  • Youth.霖

    报告,文中“牛顿迭代法”的链接失效了

  • 口工漫画大全妖气全彩

    写的太经典了,我竟无言以对。

  • milf

    Woah! I’m really loving the template/theme of this blog.
    It’s simple, yet effective. A lot of times it’s difficult to get that
    “perfect balance” between user friendliness and visual appearance.

    I must say that you’ve done a amazing job with this.
    In addition, the blog loads extremely quick for me on Chrome.

    Excellent Blog!

  • orgy porn

    Good web site you have here.. It’s hard to find good quality writing like
    yours these days. I seriously appreciate people like you!
    Take care!!

  • porn tube

    The other day, while I was at work, my sister stole my iphone and tested to see if it can survive a twenty five foot drop, just so she can be a youtube sensation. My iPad is now broken and she has 83 views.
    I know this is totally off topic but I had to share it
    with someone!

  • 2611

    Breat hook surgwry wireSexy young girliesVery youg porrn linksAree boack ggirls fuun to fuckUniviswion upskirtsMilkmaid hentaiSweett mature milf101 nude teensHomemad teen seex tapeGoood andd eevil pornOrgasm
    scenes inn moviesFlights to stt thomas virgin islandsSportss tooo
    time connsuming for teensFreee videdo voyeur solo femaleStrip wire for 110vac plugHoow much dokes a las vwgas stripper makeFreee cam2cam hoik uup milfAnime baare bottom spankingOldss pussyPorn nudde prickWomjan wwith thhe biggest pussyButy pin upsDomain oof
    darkness eroticaBeautiful lesbian maturePicturs oof janet jacksobs bare breastQueer
    dhqrma voicees oof ggay buddhistsEric dawne reebecca gayhearet nude
    videoGreat grandma nakedSpank the redd monkeyOuties vaginaSeexy korean feetAsian gidl japanKates erotic storiesNartuto fuck gamesBlack dick asiansSexy sandals heelsTeenn fucking oldd womenSwinger couple 2010 jjelsoft
    enterprises ltdBianca beauchamp before boolb jobFuck mme wjth a straponGifls rubbing her boss pussyIn opder patie ussy
    sexy silky thumbTransgennder raceBoob chubby
    fatFucked tits smallDicck strokingNaksd women hidden cameraAfrican american swingerPorn straight guuy gayKyera nightley nnude agnes monica xxx Dormm orgasmFree ssex movies utorontoYoung adsult pregnancyHappy endkngs sex
    sceneYoung adults noot ass much faithCrazy masturbation techniquesCauther penisAss blacck lack
    dick stretchinMilf handjob pornhubGranny riding cock wildlyAsian hot chicksSexx of mateernal twinsLissa gastineau nude photosForcced mmmf xxxBesst
    masszage vibrator forr womenBreast too breaast rbbing duelsFamily
    nurism sexListt of gayy themned documentariesEscoirt evwrett waJeans videos sexyCrossdress
    pofn movieOriginal petition for change off nam
    off an adultGir lnnaruto hentaiHoly davidson nakedJanije kelly lesbian pictureAdult movie with a plotDewpthrot cuum shotsGaay marvin musicFacial brown spotEboony secretasry xxxCraigslist nw indiaqna erotic serviceGeril
    pussyBoody gloves bikiniPics oof shavesd pjbic designsSeex asia comicPeee spotYmlite kicxks
    asss netTop portn film 2008Deluxe batrery electric breaast pumpSpringftield illlinois gaay communityScott stne fucks pussyVenezuelqn gay pornMedical exmination tto
    detgermine sexual activityNats fuck heavan mp3Pornn
    stars likke it bbig lihelle marieSayaa cllens nudesXxx virrgins shavedCulture electfric exploring
    geisha japans popularPenthouise nude girls frtee galleriesSeexy phone chatAsian amateur ffmSexy bllack legMorpns annd
    breast enlargementAmatedur associatin michigan softballGayy for playSttate agee oof sexual consentNakled celerityMatute chubby
    women over 18What causess diarrhea in adultsNudee mivie
    stars phhoto galleryFree video weet vaginaStraighten curve
    penisInterrracial milf porn thumbnailsVintage motor manualsNude ssculpture maleGayy orientationAduylt sruifer siteSeex oddasyAmateur bondazge videos free galleryBloow jjob compititionNasty aass holeCatherime ddmour oraql sex you tubeSusan dusrden nakedSelf sucking een boysGomexs
    pussyVintage porn loveliesBonage spread eagle clamped nipplesEscort servie listingsHoliday
    party adultHiigh aas fuck jonlajoieRed pussy stateNudde
    teenage bboy picturesThaai bbeauties pornSexy revealing shrt bralessUsaa free sexx movieTeens whho perpetrate domesfic violnce
    characteristicsCoron nemec gayThee breast indexFree hair masterbationFucking sexx girll photo
    galleryTiime ten tpgNuude scenes of celebrityBiig amatier porn videosToorture male titsXxxx interracil teensBlonde cute soccer moom suck fuckPettite girl fuckedBrutly face fuckedComic evil sexPost private nude picturesBlacj
    gugs fck white colkege girlsAerican breqst surgeonMalodorius vaginalMasturbation like being nakedAdupt movvie passFender
    vintage bss guitarsJayy andd silentbob fuckAdult spa illinoisSymptoms off m s inn adultsGivve a gjrl an orgasmFlorida adult educatio directorsMatyure bitch iin heelsRomee
    epiusode 6 penisFree vireo lesbian bondageGigg harbor big titsMatuure che ssi fannoBottom line
    innovationVaginaal lubrficant suppositoryGuard natyional pijss testMy bigg breasts
    areNuude bponde visit petrol stationMy fiurst tkme gayy storiesCraigslist male
    sexFacial cleansing padFrree tinks ffor cash videosFloydadea
    texas registered seex offendersCollege reality sex partyBedroom cooll decorating idewa teenMuscular boyfriend fucs hot girlBadd girls iss in pornErotic naugghty sex storyBlyythe ddanner nuse
    mr skinCann yyou get pregnan iif thee cohdom dkes not breakCookiing
    asianJapanese eerotic anameErotic masssge japanAgeeless bbwLarg breasts inn t shirtsSex tips invo 101Naked
    guilsStrict mom tgpFuuck thhem youngBbw dating sinles
    100 freeGlamour phboto shoot adult celebrityDaphne bpake gets spankedBreast ulyrasound resourcesBoob haircdut
    hardcoreGayy brothers have sexsexAnall sexx video tubeVideos boys
    jjerk off

  • 67490

    Huge ttit sex photoMaturde lesbian young girl picsAsian wet
    videoAdult fforum kurtadamBrother cums insude sisters pussyAdult teaching strategiesErrotic smokeFille hoset bow jobsAdult star ashantiGay pride/vaMaaure female nudesPleasuure unbound ebookWife tries neew sexual stuffSearch fttv karky nudde picturesFeish 2010 jwlsoft enterprises ltdBleahh nude
    beach sceneErotica hot hot seex shot storiesOnne hot toy nudeBbw fawcesitting
    forumBaise annal gayYoumg adult horeror novelsDiseased diick booterFree streaming
    mobile xxxx tubesErotic stories about breastsFreee
    televisiion carton porrn videoHung gay guysSexx instructionsAkaa video strrip poker fullAdullt seex flqsh games swimVntage muhsic lyricsFree ude pics of evwngeline lillySweet asiazn angelsFatt moms porn sexSoftcre girls forumHot teen facial thumbsDaddy’s irl eroticaReal girlpfriends cumshotsMedication depredssion lipi profilee sexDrunjk pparties orgySexx industtry
    accountingAffender ndiana sexJade jswel porn starSpededo gayy picsMenn fucking girlsRabbit pibk twinksArrab painful anall sexSeex acts caught onn cctvBest audition sonng forr teensTarzqn swinging onn a ubber bandFinzl fantasy x2 hentai
    comcs video bokep xxnn Bestt aass thongFreee erdotic chat no
    webcamSexxy cartd gamesNudee soldier femaleDity hardcore orgiesTeerns iin pantys
    pornNudde mefial exam bby nursesLyric for sex ccan i by rray jayKeralka sexyFree mature daddy gay blogsBreasts matufe
    womenResearch silicone breqst implantsGropoing teen tubesHusbnd wfe sexx blogFree hiss fissrt gay fuckMalee femdomVintage instrumjents banjoleleAdult beauty pagents inn floridaHott erottic lettersMarried then realized i waas
    gayTeeen challenge neew haven ctNaked munmunNaked women’s wrstlong leagueParis hilton sexx tappe fee
    previewAsiwn food jokesNichole hiltz aked picturesLookiing up sexy wonen shirtsVacaation packages
    for virgin islandsLsbian lovers gangbangLocal woman foor pleasureBurnihg mann nudistFiigures annd vintage ho slot
    carJackson michigan gayGayy bars iin pheonix arizonaPlasygirl nnaked men and nakked womenwomenFacial skun sqeeze white substanceMeet shemaleRyann lochte
    xxxAddult vifeo doggie styleSisster fuckiing sister poprn videoCell phon footjobCaasual
    sexx in wewela soutth dakotaNude teen celeebsFree mture forumsFrree pusxy clip galleriesFree celebriity porn searchWhich countries giels
    are best fuckCatherin tate nakedRubber dicxk manErotc faat wive catfcight tubesWinee ffat assLesbian dilidoAmmy
    french nakedFrree online sexy short storiesSexxy nude ruszian mail order bridesSexzual ppositions for sims2 charactersSteel cock bal weightsDatte mee nudeSuck it jesusNew update pornCan sprm bee transferred
    myy mouthKataea nuce videosShemkale dominantsFreee teen poro
    picTrrue sex storues xxnFree whikte shado seex storyYoung nude gtmnastics photosTeenn sex
    gfVintage lecoultre watchesNeeyo sexy love mp3Glleries nnn lingerieTranssexual lufe japanFashiuon stylles plasy down large breastsHott naked granny womenGaging cockFreee video of nudde
    young girlsGayy prostotutionDisney porn jasmineHott gay hhunks dougle penetrationMom froom family
    guy nakedTop maturee modelsDajiel radliffe poorn picsCrolwning vaginal birthNatoonal
    sexual assaultt rewsource shaaring projectVintae costgume jewelry ringsOedekrk thumb warsDr braid and sxual abuse chargesHoot
    vrronica zemanova strip redErotic party slumber storySecdret persona sexx sitesBeonce knjowels sucking dickMature black lesbiansHardcore fucking
    funger fucksShemale surprisesBikini pic supermodelFishing buddie fuckingVaginzl hysterectomy+videosTeen panttie vidsGay’ pewnis fuckingPoofboy bikini beachCrags
    listt erottic gamesGermaan scat pornVirgun radio pats your billsSexy babes inal fantasyy cosplayWhijte mture
    and blackCedarfeszt titsAreea swollen vaginalNude redd
    hwir maleTeeen drinkng andd driving statitisiticsPink otally nakedVivaca ffox sex tap eImagss oof tteens witrh
    babysDicck pic’sShe loved playing with myy coxk annd
    ballsFishr price ppieces vintageSexul aactivity 1950Latino ggay
    gloryholesStarft troublpe let’s get fucked upSusan pleshete sesxy movieEsckrts
    mature walkersBbbw huge dildoJayne spencer incredibe fuckCompliccations with vagnal biospyFrree soft video teen pornBlowsjob pictureMoom fucking on hidcen camersBreast
    skin nnipple tiussue woman hormonalHow long ccan a man have sexWatgch frse adriana ljma sex
    videoRedtube vixenn had jobKendra de rossi porn starGerman classic
    hary blond pussyGayy lord dicksLicck library caprice
    5Sexx shops in gilbert azTopp ten viurus ffree pornChloroformmed and fuckedd girlsBiiini 30dTeenn girrls explorring eacdh otherGuntewr suckMature ggroupe sexeRipli zsuzsi pornReal black
    amateur pussyDad fucking new stepdaughterNorris blowjobForhed tignt puxsy sample
    videoFtos porno nii asNaalia cruze sexPretyy ebolny gkrls with ffat assesActres
    india sex

  • 8017

    Sculptra injections in bottfom off feetDanny aand kylie minoue pornDont ffresh marry off
    riip roptten sshe soil virginGirll watches masturbationDaily poren mmgp thumbsShocking gayy videoasHot ass annd pussyYoung twinks with big dicksCelll
    phone pkrn clipsI appared naked on televisionPostop shemale galleriesEn eros lanhguage language nl ramazzottiHunteer
    escortMara asian porn orrent uncensoredSoprnos sex scenesHoww to get my wif to
    have sexx moreIntentional ommunity gaay menOriwntal ffee cmshots
    xxxWiife vacation nudeTeen hardcore portn moviesAfdican lesbian videosReguylar woimen wearjng pantyhose picturesLesbian nylon bondage storiesTraveked path oof sperm though
    vaginaTeen girrl giving tden booy blowjobAmasteur strokeplayBroown vaginal dixcharge yazGiina
    wjld mmit dildoUine fetish girl storyDog pee deterrentDeepika
    padukone nudeAdult costuyme ddr suessSteip mp4Parotiid
    gland and fzcial nerveMind bliwing sex techniquesJimmy kimmel fuckikng
    ben afflecPictures oof teeen masturbationKrdiashian nudeStreaming pporn rimmig hairy aass hole80 s topp teenn moviesSex
    sotres freeBladder infection sexx duringVintage ruustic faqbric paintingSeex channeltv p nettetRaquel grant bbwPspp sexy themesDeliery sexYoung asia gril
    sexInstant hentai moviesTabby fetiksh mineiroloko Witcfhes tgpEectra milf1995
    fordd esscort reaar defroster switchGorgeous pantyuose akira laneBiig dilpdo
    in pretty girlFamous pornstars devonFat aass galeriesFrree galleres
    of nzked babesFucking ugly bitchMrie dijva nakedThhe best sexx toys reviewsYoung bblack twen girlss nudeCann milk and papatas enlarge breastMens fleece pj
    bottomsTeeen slapprd aroud annd fuckedHadd havee sexHarcore
    hoopsMenns underwear hairyPussiess hasve orgasmFrree hlmemade porn video
    ppsting siteBrittany gold nudeSellf suck enckuragement own cumSexy maid outfitesMiilfs like it biig winnie torrentLesgian submission blondesHacked xxx pay siteShhe
    learns tto fuckShe diapered spanjked iin publicFrree lickstick blowjob tube
    movieSexxy xxx asianKaatie lohmann nakedDoctor exam nudeGirrl takess 3 cockks oone holeGay black fucks videosAnal ezeeHairy moms annd boysTreatment ffor sexual promiscuityTouble
    teenns texasRobert hanssen xxxx chatrokm descriptionFree
    potn 100 facial cumshotsAddress address boopk bokk lingverie paperstylle pockett pocketPussy haiur jokesSex annd tthe ity
    cakesFree tiny girl tgpNakeed iin kittchenAduylt shop 61Bikinni galleey miniChurch oof christ parabould outh sexualMy vintge tubeDryy
    vagina cream2 dicos jacking offCerlebrity cartoon pornNaked annd funny uncesoredVomikt fetish
    girlFetish life secret womanHiddden videos oof steppaughter xxxTna’s
    tara nudeGaallery teen tigraSupermodel nude stripFemdom highheels tramplingThick wet
    slutsYoumg mothyer seducdd andd then fuckedSupeergirl toopns
    eempire pornKeisha doublle fistingFreee hardcore videos wommen fucked doggystyleLesbian bouncing boobsFrree clips
    lost nude betsGay codes ffor ttop oor bottomGreatt teenLatina
    forced blowjobs underwaterPainful amal hurt videosBig
    breast galledry naturalMixzed girtl sucking cock picturesFree youtbe busety momsAbou rman breast plateYoung nuude pic boardMarissa mille
    nuxe perfect 10 picsLow growqth hormone in adultsVampire suck
    shlw timesJapanese avv idool nnude picturesZuuma
    hentaiDeaanna mcc nudeUtah performing rts teewn campOlder women xxx blackHard
    core porn bartendets assPornn mofosMake-up tips foor nude lookAsian wife creampke
    blackNess prn gamesOverturn gay marriahe banHomemade fake boobsChick christmas nakedSell your sex taspe picksAmatuer sex funStrqight gguy punked
    by tdanny shemaleTube that carrties sperm from the epididyymis to tthe
    urethraFrree adul ajime galleryFairytail costume sexNeew faial hair medicationVintage chyina dinnerwareReligious instigute sexuawl morality justicee healingSpcial d
    suck my dickTeaching conhcepts forr aduylt learners of
    spanish decentBbww andd loveDicks sporting goods colorfado springs coloradoFree
    ten pjssy teen panties moviesAdul frin finderSeniors pussyAsian grdill
    newport newss vaSexx free videos teachersFaat bbw fucked iin youtubeBeach moviie sexAduhlt private modeling tamoa bayBesst esscort in montrealWhatt cuses eear infections inn teensFree
    xxxx movie hindiTeeen rock bads iin ypswi miStacdy ferdguson nakedPhilipinas fuckingPhilipine
    sex guideOnline sexyal disorder screeningPersonal stoy about teesn with crtedit cardd debtHuuge
    cochk video clipsMature milf pumpkinAquua teesn hungerforce soundboardIndian matuire teenageWhich comic stips aare publicc domainSize
    14 cocksize 8 pussyLesbian twinjs lickingPodhast adultMultiple sclerosis
    aand breast augmentationDownload fee porn catfightRsearch onn teen datingRooster
    rock nuude beachFree crlutchless pantyhose picsMatuee faqntasy worldSilcon vs saoine breast implant
    photosThinn teens nuyde picturesDeemo fucking machineErase poen siteNuude photos oof harry potterNudist couple sexHeatther gram sexyTinyy sexy
    bikinisStriaght ggay maleSoftsare ffor adlt basic educationWant tto fuk myy oldder sisterLafge cock throa fuckingMaade of honor
    hannah in lingerieBoobs piarte

  • Refugio Hose

    Whoa loads of good advice!

  • Alquila coches en Otopeni desde 14 €

    Hi there, I enjoy reading all of your article post. I like to write a
    little comment to support you.

发表评论

  ×  4  =  24