第一章 素數判定法現狀

現在，確定性素數判定法已經有很多種，常用的有試除法、威廉斯方法、艾德利曼和魯梅利法。它們的適用范圍各不相同，威廉斯方法比較適合10^20到10^50之間的數，艾德利曼和魯梅利法適合大于10^50的數，對于32位機器數，由于都小于10^10，所以一般都用試除法來判定。

也許有人會問：“你為什么沒有提馬寧德拉.阿格拉瓦法呢？不是有人說它是目前最快的素數判定法嗎？” 其實這是一個很大的誤解，阿格拉瓦法雖然是log(n)的多項式級算法，但目前只有理論上的意義，根本無法實用，因為它的時間復雜度是O(log(n)^12)，這個多項式的次數太高了。就拿最慢的試除法跟它來比吧，試除法的時間復雜度為O(n^(1/2)*log(n)^2)，當n = 16時，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多么大！如果要讓兩者速度相當，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^43.1214，此時需要進行的運算次數為log(n)^12 = 10^25.873（注意：本文中log（）函數缺省以2為底），這樣的運算次數在一臺主頻3GHz的計算機上運行也要10^8.89707年才能運行完，看來我們這輩子是別指望看到阿格拉瓦法比試除法快的這一天啦！

除了這些確定性素數判定法外，還有基于概率的非確定性素數判定法，最常用的就是米勒-拉賓法。

對于32位機器數（四則運算均為常數時間完成），試除法的時間復雜度是O(n^(1/2))，而米勒-拉賓法的時間復雜度只有O(log(n))。所以后者要比前者快得多，但是由于米勒-拉賓法的非確定性，往往我們在需要確定解時仍然要依靠速度較慢的試除法。那是否可以通過擴展米勒-拉賓法，來找到一種更快的確定性素數判定法呢？結論是肯定的，本文就帶你一起尋找這樣一種方法。

第二章 2-偽素數表的生成

既然要擴展米勒-拉賓法，那首先我們應該知道為什么米勒-拉賓法是個非確定性素數判定法？答案很簡單，由于偽素數的存在。由于米勒-拉賓法使用費爾馬小定理的逆命題進行判斷，而該逆命題對極少數合數并不成立，從而產生誤判，這些使費爾馬小定理的逆命題不成立的合數就是偽素數。為了研究偽素數，我們首先需要生成偽素數表，原理很簡單，就是先用篩法得出一定范圍內的所有素數，然后逐一判定該范圍內所有合數是否使以2為底數的費爾馬小定理的逆命題不成立，從而得出該范圍內的2-偽素數表。我的程序運行了100分鐘，得出了32位機器數范圍內的2-偽素數表，如下：

341

561

645

1105

1387

1729

1905

2047

2465

2701

...

...

...

4286813749

4288664869

4289470021

4289641621

4289884201

4289906089

4293088801

4293329041

4294868509

4294901761

（共10403個，由于篇幅所限，中間部分省略。）

第三章 尋找2-偽素數的最小可判定底數

對于2-偽素數表的每一個偽素數，尋找最小的可以判定它們是合數的底數，我把這個底數稱之為最小可判定底數。特別地，對于絕對偽素數，它的最小質因子即是它的最小可判定底數。由于已經證明了絕對偽素數至少有三個質因子，所以這個最小質因子一定不大于n^(1/3)。下面就是我找到的最小可判定底數列表：

341     3

561     3

645     3

1105    5

1387    3

1729    7

1905    3

2047    3

2465    5

2701    5

...

...

...

4286813749      3

4288664869      3

4289470021      5

4289641621      3

4289884201      3

4289906089      3

4293088801      3

4293329041      3

4294868509      7

4294901761      3

通過統計這個列表，我發現了一個規律，那就是所有的最小可判定底數都不大于n^(1/3)，由前述可知，對于絕對偽素數，這個結論顯然成立。而對于非絕對偽素數，雖然直觀上覺得它應該比絕對偽素數好判定出來，但是我無法證明出它的最小可判定底數都不大于n^(1/3)。不過沒關系，這個問題就作為一個猜想留給數學家來解決吧，更重要的是我已經通過實驗證明了在32位機器數范圍內這個結論成立。

我們還有沒有更好的方法來進一步減小最小可判定底數的范圍呢？有的！我們可以在計算平方數時進行二次檢測，下面是進行了二次檢測后重新計算的最小可判定底數列表：

341     2

561     2

645     2

1105    2

1387    2

1729    2

1905    2

2047    3

2465    2

2701    2

...

...

...

4286813749      2

4288664869      2

4289470021      2

4289641621      2

4289884201      2

4289906089      2

4293088801      2

4293329041      2

4294868509      2

4294901761      3

很顯然，二次檢測是有效果的，經過統計，我發現了新的規律，那就是經過二次檢測后所有的最小可判定底數都不大于n^(1/6)，真的是開了一個平方呀，哈哈！這個結論的數學證明仍然作為一個猜想留給數學家們吧。我把這兩個猜想叫做費爾馬小定理可判定上界猜想。而我已經完成了對32位機器數范圍內的證明。

通過上面總結的規律，我們已經可以設計出一個對32位機器數進行素數判定的 O(n^(1/6)*log(n)) 的確定性方法。但是這還不夠，我們還可以優化，因為此時的最小可判定底數列表去重后只剩下了5個數（都是素數）：{2,3,5,7,11}。天哪，就是前5個素數，這也太容易記憶了吧。

不過在實現算法時，需要注意這些結論都是在2-偽素數表基礎上得來的，也就是說不管如何對2的判定步驟必不可少，即使當2>n^(1/6)時。

還有一些優化可以使用，經過實驗，當n>=7^6時，可以不進行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正確的。這樣就可以把判定次數降為4次以下，而每次判定只需要進行4log(n)次乘除法（把取余運算也看作除法），所以總的計算次數不會超過16log(n)。經過實驗，最大的計算次數在n=4294967291時出現，為496次。

自己寫了個隨機化素數判定算法：
s越大，穩定性越好，但效率會低點。原作者有更好的判定算法，對作者表示感謝。。 對自定義類型到string的示例

 

Reference Type 和 Pointer Type

所謂左值（lValue）：是用來代表某個對象的一個東西。如果p是指向類型為T的某個對象，那么表達式*p不能只是返回類型為T的對象，而必須是返回一個lValue（左值）。

   平時總是拿起*p就直接賦值（對于簡單基本類型，例如int *p = &I ;  *p=3），沒想什么*p返回左值那么多。但是當在自定義類中重栽*運算符的時候，我們就要特別小心，要注意到這點，返回為T& 才對。

言規正傳

iterator_traits的某些機制所蘊涵的意義十分微妙而深遠，不過它的實現卻不是很復雜，不過這些東西看起來比較容易看懂，真正能夠靈活使用就需要花時間領悟了，為什么會采取這種方法解決問題，和其它的方法對比有什么好處和提高？這種明白這些問題才算掌握了trait的實質。

template< class Iterator>

struct iterator_traits

{

typedef   typename Iterator::iterator_category   iterator_category;

typedef   typename Iterator::value_type        value_type;

typedef   typename Iterator::difference_type    difference_type;

typedef   typename Iterator::pointer           pointer;

typedef   typename Iterator::reference         reference    ;

};

template< class T>

struct iterator_traits

{

typedef   random_access_iterator_tag   iterator_category;

typedef   T        value_type;

typedef   ptrdiff_t    difference_type;

typedef   T*           pointer;

typedef   T&         reference    ;

};

template< class T>

struct iterator_traits

{

typedef   random_access_iterator_tag   iterator_category;

typedef   T        value_type;

typedef   ptrdiff_t    difference_type;

typedef   T*           pointer;

typedef   T&         reference    ;

};

當你定義一個自己的算法，你需要關注這個機制，下面兩個理由就是你可能要用到iterator_traits：

①     你必須返回某值，或者是申明臨時變量，而其它型別與iterator的value type 或者different type或者reference type 或者pointer type一致。

②     你的算法類似與advance，必須根據iterator的分類來決定不同的實現方法（提高效率，在編譯時候進行判斷而不是在運行的時候進行判斷），沒有traits機制，你只好在‘一般化但是沒效率’或者‘有效率但是過度狹隘’中進行抉擇。

當定義一個Iterator 類，就得在改類中定義五個嵌套的類型，如上面的五個所示。要不然就得針對你的Iterator類，明白的令iterator_traits為Iterator特化，就像iterator_traits要明白的針對指針而特化一樣。第一種做法總是比較簡單，尤其是STL的一個輔助類，base class iterator，讓事情變得更簡單了。

template< class Category,

class Value,

class Distance =ptrdiff_t,

class Pointer = Value*,

class Reference = Value &

>

struct iterator

{

typedef Category iterator_category;

typedef Value      value_type;

typedef Distance difference_type;

typedef Pointer     pointer;

typedef Reference   reference;

};

     為了確保iterator_traits能夠對新的iterator class有適當的定義，最簡單的方法就是從iterator類派生自己的iterator。基類iterator不含任何成員函數和成員變量，所以繼承不存在額外的開銷。

說來慚愧，使用了很久Visual Stdio 2003了，只知道MFC升級到了7.0，ATL也升級到了7.0，對于這兩個經典的類庫做了一些研究，但一直沒有注意C++標準庫的變化。

     今天嘗試的使用了stdext::hash_map這個庫，果然不錯。下面寫下一些心得。

     hash_map類在頭文件hash_map中，和所有其它的C++標準庫一樣，頭文件沒有擴展名。如下聲明：

          #include <hash_map>
          using namespace std;
          using namespace stdext;

     hash_map是一個聚合類，它繼承自_Hash類，包括一個vector，一個list和一個pair，其中vector用于保存桶，list用于進行沖突處理，pair用于保存key->value結構，簡要地偽碼如下：

          class hash_map<class _Tkey, class _Tval>
          {
          private:
               typedef pair<_Tkey, _Tval> hash_pair;
               typedef list<hash_pair>    hash_list;
               typedef vector<hash_list>  hash_table;
          };

     當然，這只是一個簡單模型，C++標準庫的泛型模版一向以嵌套復雜而聞名，初學時看類庫，無疑天書啊。微軟的hash_map類還聚合了hash_compare仿函數類，hash_compare類里有聚合了less仿函數類，亂七八糟的。

     下面說說使用方法：

     一、簡單變量作為索引：整形、實性、指針型
     其實指針型也就是整形，算法一樣。但是hash_map會對char*, const char*, wchar_t*, const wchar_t*做特殊處理。
     這種情況最簡單，下面代碼是整形示例：
            hash_map<int, int> IntHash;
            IntHash[1] = 123;
            IntHash[2] = 456;

            int val = IntHash[1];
            int val = IntHash[2];
     實型和指針型用法和整形一樣，原理如下：
     1、使用簡單類型作索引聲明hash_map的時候，不需要聲明模版的后兩個參數（最后一個參數指名hash_map節點的存儲方式，默認為pair，我覺得這就挺好，沒必要修改），使用默認值就好。
     2、對于除過字符串的其它簡單類型，hash_map使用模版函數 size_t hash_value(const _Kty& _Keyval) 計算hash值，計算方法是經典的掩碼異或法，自動溢出得到索引hash值。微軟的工程師也許開了一個玩笑，這個掩碼被定義為0xdeadbeef(死牛肉，抑或是某個程序員的外號）。
     3、對于字符串指針作索引的時候，使用定類型函數inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)計算hash值，計算方法是取出每一個字符求和，自動溢出得到hash值。對于字符串型的hash索引，要注意需要自定義less仿函數。
     因為我們有理由認為，人們使用hash表進行快速查找的預期成本要比在hash表中插入的預期成本低得多，所以插入可以比查找昂貴些；基于這個假設，hash_map在有沖突時，插入鏈表是進行排序插入的，這樣在進行查詢沖突解決的時候就能夠更快捷的找到需要的索引。
     但是，基于泛型編程的原則，hash_map也有理由認為每一種類型都支持使用"<"來判別兩個類型值的大小，這種設計恰好讓字符串類型無所適從，眾所周知，兩個字符串指針的大小并不代表字符串值的大小。見如下代碼：
          hash_map<const char*, int> CharHash;
          CharHash["a"] = 123;
          CharHash["b"] = 456;

          char szInput[64] = "";
          scanf("%s", szInput);

          int val = CharHash[szInput];

     最終的結果就是無論輸入任何字符串，都無法找到對應的整數值。因為輸入的字符串指針是szInput指針，和"a"或"b"字符串常量指針的大小是絕對不會相同。解決方法如下：
     首先寫一個仿函數CharLess，繼承自仿函數基類binary_function（當然也可以不繼承，這樣寫只是符合標準，而且寫起來比較方便，不用被類似于指針的指針和指針的引用搞暈。

          struct CharLess : public binary_function<const char*, const char*, bool>
          {
          public:
               result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
               {
                    return(stricmp(_Left, _Right) < 0 ? true : false);
               }
          };

     很好，有了這個仿函數，就可以正確的使用字符串指針型hash_map了。如下：

          hash_map<const char*, int, hash_compare<const char*, CharLess> > CharHash;
          CharHash["a"] = 123;
          CharHash["b"] = 456;

          char szInput[64] = "";
          scanf("%s", szInput);

          int val = CharHash[szInput];
     
     現在就可以正常工作了。至此，簡單類型的使用方法介紹完畢。

     二、用戶自定義類型：比如對象類型，結構體。
     這種情況比價復雜，我們先說簡單的，對于C++標準庫的string類。
     
     慶幸的是，微軟為basic_string（string類的基類）提供了hash方法，這使得使用string對象做索引簡單了許多。值得注意（也值得郁悶）的是，雖然支持string的hash，string類卻沒有重載比較運算符，所以標準的hash_compare仿函數依舊無法工作。我們繼續重寫less仿函數。
         
          struct string_less : public binary_function<const string, const string, bool>
          {
          public:
               result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
               {
                    return(_Left.compare(_Right) < 0 ? true : fase);
               }
          };
           
     好了，我們可以書寫如下代碼：
           
          hash_map<string, int, hash_compare<string, string_less> > StringHash;
          StringHash["a"] = 123;
          StringHash["b"] = 456;

          string strKey = "a";

          int val = CharHash[strKey];
     
     這樣就可以了。
     
     對于另外的一個常用的字符串類CString（我認為微軟的CString比標準庫的string設計要灑脫一些）更加復雜一些。很顯然，標準庫里不包含對于CString的支持，但CString卻重載了比較運算符（郁悶）。我們必須重寫hash_compare仿函數。值得一提的是，在Virtual Stdio 2003中，CString不再是MFC的成員，而成為ATL的成員，使用#include <atlstr.h>就可以使用。我沒有采用重寫hash_compare仿函數的策略，而僅僅是繼承了它，在模版庫中的繼承是沒有性能損耗的，而且能讓我偷一點懶。
     首先重寫一個hash_value函數：
     
          inline size_t CString_hash_value(const CString& str)
          {
               size_t value = _HASH_SEED;
               size_t size  = str.GetLength();
               if (size > 0) {
                    size_t temp = (size / 16) + 1;
                    size -= temp;
                    for (size_t idx = 0; idx <= size; idx += temp) {
                         value += (size_t)str[(int)idx];
                    }
               }
               return(value);
          }
     
     其次重寫hash_compare仿函數：
     
          class CString_hash_compare : public hash_compare<CString>
          {
          public:
               size_t operator()(const CString& _Key) const
               {
                    return((size_t)CString_hash_value(_Key));
               }
  
               bool operator()(const CString& _Keyval1, const CString& _Keyval2) const
               {
                    return (comp(_Keyval1, _Keyval2));
               }
          };
           
     上面的重載忽略了基類對于less仿函數的引入，因為CString具備比較運算符，我們可以使用默認的less仿函數，在這里映射為comp。好了，我們可以聲明新的hash_map對象如下：

          hash_map<CString, int, CString_hash_compare> CStringHash;

     其余的操作一樣一樣的。

     下來就說說對于自定義對象的使用方法：首先定義
     
          struct IHashable
          {
               virtual unsigned long hash_value() const = 0;
               virtual bool operator < (const IHashable& val) const = 0;
               virtual IHashable& operator = (const IHashable& val) = 0;
          };
     
     讓我們自寫的類都派生自這里，有一個標準，接下來定義我們的類：
     
          class CTest : public IHashable
          {
          public:
               int m_value;
               CString m_message;
          public:
               CTest() : m_value(0)
               {
               }
           
               CTest(const CTest& obj)
               {
                    m_value = obj.m_value;
                    m_message = obj.m_message;
               }
          public:
               virtual IHashable& operator = (const IHashable& val)
               {
                    m_value   = ((CTest&)val).m_value;
                    m_message = ((CTest&)val).m_message;
                    return(*this);
               }
           
               virtual unsigned long hash_value() const
               {
                    // 這里使用類中的m_value域計算hash值，也可以使用更復雜的函數計算所有域總的hash值
                    return(m_value ^ 0xdeadbeef 
               }
           
               virtual bool operator < (const IHashable& val) const
               {
                    return(m_value < ((CTest&)val).m_value);
               }
          };
     
     用這個類的對象做為hash索引準備工作如下，因為接口中規定了比較運算符，所以這里可以使用標準的less仿函數，所以這里忽略：
     
          template<class _Tkey>
          class MyHashCompare : public hash_compare<_Tkey>
          {
          public:
               size_t operator()(const _Tkey& _Key) const
               {
                    return(_Key.hash_value());
               }
           
               bool operator()(const _Tkey& _Keyval1, const _Tkey& _Keyval2) const
               {
                    return (comp(_Keyval1, _Keyval2));
               }
          };
           
     下來就這樣寫：
     
          CTest test;
          test.m_value = 123;
          test.m_message = "This is a test";
     
          MyHash[test] = 2005;
           
          int val = MyHash[test];
     
     可以看到正確的數字被返回。
     
     三、關于hash_map的思考：
     
     1、性能分析：采用了內聯代碼和模版技術的hash_map在效率上應該是非常優秀的，但我們還需要注意如下幾點：
     
     * 經過查看代碼，字符串索引會比簡單類型索引速度慢，自定義類型索引的性能則和我們選擇hash的內容有很大關系，簡單為主，這是使用hash_map的基本原則。
     * 可以通過重寫hash_compair仿函數，更改里面關于桶數量的定義，如果取值合適，也可以得到更優的性能。如果桶數量大于10，則牢記它應該是一個質數。
     * 在自定義類型是，重載的等號（或者拷貝構造）有可能成為性能瓶頸，使用對象指針最為索引將是一個好的想法，但這就必須重寫less仿函數，理由同使用字符串指針作為索引。

        想自己開始學語言的時候，因為根本不知道什么書好，所以看到基本是一些國內的，水平一般的書，如果你剛開始學c or c++,推薦c++創始人寫的<<the c++ programming language>>,即使是學有所成的人，再看此書也有很大收獲我想，慢慢品味，會有收獲的。。。以后我會將自己學習此書的筆記寫在此，各位路過的大牛指點指點。。。^_^