為什麼演算法中會出現magic number?

01-08

比如知乎上經典的Quake 3的開平方根演算法中的magic number，抑或是BKDRHash中的131，或者DJBHash中的5381，像這樣的數字是如何產生的，有沒有給出數學上的解釋？如果沒有又是為什麼不能給出相應解釋？

我們之所以管magic number叫magic number 就是因為我們不知道它是啥意思啊..

PS. 你說的那個數字不算magic number 因為有一句注釋..

有一些有數學原理，比如說以前寫過一個浮點數近似演算法的分析，主要就是運用浮點數與強制轉換成的定點數之間的近似關係：log_2(浮點數)≈定點數 + 小偏置。那個小偏置的取值一般就是個Magic Number。最終的最佳取值可能還是要經過一些實驗的。

這個求指數函數exp()的快速近似方法的原理是什麼? - 數學 - 知乎

另一些比如hash當中那個131，有一定的原理，但是還是以玄學為主

hash演算法的數學原理是什麼，如何保證儘可能少的碰撞？ - 計算機 - 知乎

純隨機或者玄學的也有，比如說DHCP中間的magic number，就沒有任何特殊的意義，僅僅是一個不太可能隨機出現的、用來表示這個協議的確是DHCP（BOOTP）的值。

這種參數一般都是試出來的，讓某種指標（如：整體誤差、碰撞概率等）最小

程序里的magic number 只是一個最優/較優數值解而已，由於它與工程本身架構演算法的重要性比起來微不足道（或者說在代碼里寫大段注釋解釋怎麼算這個數值解很可笑），所以作者通常對這些常數的解釋語焉不詳。

程序員習慣從代碼及其注釋理解程序的演算法，而magic number 就相當於一大段隱藏代碼（數學尋優）的執行結果，沒跳出固有習慣的程序員就會不知所以，傳訛magic number 是個謎…

以quake iii里那個快速開方演算法里的magic number為例，演算法本身很簡單，是作一次牛頓迭代，幻數只是一個較優迭代初值，相對於整個演算法而言只是個細節而已，所以作者沒必要為它多作解釋。

本身求這個較優數值解也不是什麼難題，只要查一下ieee里float的存儲格式，學過基礎的泰勒級數知識，就能把這個問題轉化為純粹的數學上的數值尋優問題，藉助現代的數學工具（matlab之類），很容易算出最優數值解，而且比原文的magic number精度略高。這也說明了原幻數只是作者隨手逼近的一個近似較優解而已，由於大方向上演算法（牛頓迭代法）的限制，這個幻數再精確下去對精度提升基本沒有幫助，所以作者也懶得算下去。

想了解具體求解過程的可以看下面的鏈接，

http://mt.renren.com/blog/301235945/492650132

這是我第一次從人人網看到quake iii快速開方演算法後用mathematica簡單求解的過程。簡單地說就是求兩個曲線簇交點最大值的最小值，十行以內mathematica計算代碼的事。

所以我認為編程上的幻數相對於工程本身的架構演算法而言只是個微不足道的細節。

有很多快速開方演算法在速度上優於quake iii，這樣看來它的magic number 再神秘也並沒有什麼卵用…

然而物理上的magic number就屬於另一種層次的了，或許是造物主"編程"時用的magic number，這些數不是這個值就不會有我們現在的宇宙存在，有點人擇原理的味道。

quake3的magic number是用牛頓迭代算出來的一個近似值，用來快速開方。

http://wk.baidu.com/view/20ce6451f01dc281e53af01d#page/1/1428485924648

你說的其他的演算法不了解，但這些數的選擇很可能和數學原則有關。特別是密碼學相關的東西。

當然也可能拍了下腦門。

哈希函數和素數

沒有人可以證明素數和偽隨機數生成器之間的關係，但是目前來說最好的結果使用了素數。偽隨機數生成器現在是一個統計學上的東西，不是一個確定的實體，所以對其的分析只能對整個的結果有一些認識，而不能知道這些結果是怎麼產生的。如果能進行更具體的研究，也許我們能更好的理解哪些數值比較有效，為什麼素數比其他數更有效，為什麼有些素數就不行，如果能用可再現的證明來回答這些問題，那麼我們就能設計出更好的偽隨機數生成器，也可能得到更好的哈希函數。

http://m.blog.csdn.net/blog/eaglex_11109/6310727

有一天我問Neil，你圈複雜度咋是E-N+2，2怎麼來的，他說，that"s a magic number.然後我說就為了結果是正數？他頓了一下，說you get the point。我還悶悶不樂驗算為什不是1，為什不是1024，後來結果是只有在2的時候順利充要滿足最短數量路徑覆蓋全路徑 [軟體測試的理論知識 ]

————————境界提升

我的回答是，magic number是人接受數字的結果或稱謂，它出現的本質跟為什麼素數只能被一與本身整除一樣，只是過程相反，我們把這樣的數叫素數，我能把這裡的magic number叫magic number.因為沒有這些數字的參與，規律就不成立了。

————————境界提升

可為什麼是常量呢？這些magic number可以被規律函數某些特殊值代替么，有些被代替了，比如平面幾何上三角形內角和180被後來(n-2)*180代替了，有些沒被代替，比如n邊形外角在平面上一直是180到了微分幾何也是如此，180就變成magic number了，你可以說2派變成magic number，咦，有兩個特殊數字呢，不不不，它們都是一個規律。越來越多的數字們被人解開奧秘，掌握規律，還有一些還在等我們，我是說規律才是重要的。

————————有一次提升

我也是最近才看到了數學理論評估世界推理世界的局限性，數學規律在自演繹時確實會出現令人不愉快的bugs，無論公理體系多完備，這些意外的結果就是magic number的參與，每一個讓人費解的magic number就好像為這個體系加了條規則，這種情況一定得是這樣，似乎成了公理，成了法則，其實，在我看來，是數學仍舊不完備所造成的畸形美『各位大牛請原諒我』

————————深化

數學有無數美麗之處，優雅簡潔深刻，但誰能解釋黃金比在哲學上的意義么，不是0.618這個magic number很美，而是數字背後的『尺寸』平衡吸引人。作為magic number背後隱藏的規律，才是我真正關心，數字只是數學定義規律下的數學符號。

————————期許

數學的目標是從數與量上刻畫邏輯規律，是一種描述規律絕不是終極規律，誠心希望能把這些magic number合理化，沒有合理化掉的數學世界參與者可能來自其他世界規律的強制干預。

————————

1+1=3 故事協會推送

一旦找到一個新數字能讓你的解更優，則原來的數字就失去了意義。magic number是它符合在當前context內的最優，而目前的經驗暫時無法將它通過一個通用公式或者函數推導出，或不值得這樣做，它已經很好的應用在工程中了。如在其他行業中，我們一般叫「經驗」。一般都是不斷的嘗試比較，很像是機器學習裡面調整特徵權重接近最優的過程。

此所謂玄學也。

Magic Number可以有很多種：

1、經驗所得。經過多次測驗，發現這個數字可以在某種情況下最接近你最想要的結果。例子：我平常隨機種子都用時間戳，但我有個朋友從來都用一個特定的數字做隨機種子，往往隨機出來的結果都比我的好。

2、計算所得。這個不用說啥，例如一個展開式中的某個係數，用於某迭代過程；或者是在預處理過程中得出的結果直接使用到最終程序中等等。例子：quake3中的sqrt。

3、規定所得。直接說例子：md5中預先存的那四個magic number。

據說理論物理有大量參數都是Magic number .. 參見場論

Hacker"s Delight這本書有大量Magic Number以及Magic Number推導過程。

LLVM優化器里也有一些代碼參照這書。

我覺得magic number很多情況下就是simulation出來的最優解, 比如ML里的 Gradient Descent, 或
Newton-like Methods 之類的沒法證明或者懶得證就叫magic