第一章 素数判定法现状
现在,确定性素数判定法已经有很多种,常用的有试除法、威廉斯方法、艾德利曼和鲁梅利法。它们的适用范围各不相同,威廉斯方法比较适合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次。
自己写了个随机化素数判定算法:
1 #include <iostream>
2 #include <cmath>
3 #include <algorithm>
4
5 using namespace std;
6 typedef unsigned __int64 longlong_t;
7
8 bool _IsLikePrime(longlong_t n, longlong_t base)
9 {
10 longlong_t power = n-1;
11 longlong_t result = 1;
12 longlong_t x = result;
13 longlong_t bits = 0;
14 longlong_t power1 = power;
15 //统计二进制位数
16 while (power1 > 0)
17 {
18 power1 >>= 1;
19 bits++;
20 }
21 //从高位到低位依次处理power的二进制位
22 while(bits > 0)
23 {
24 bits--;
25 result = (x*x)%n;
26 //二次检测
27 if(result==1&&x!=1&&x!=n-1)
28 return false;
29
30 if ((power&((longlong_t)1<<bits)) != 0)
31 result = (result*base)%n;
32
33 x = result;
34 }
35 //费尔马小定理逆命题判定
36 return result == 1;
37 }
38 inline bool JudgePrime(int n,int s)
39 {
40 srand(20);
41 for(int i=0;i<s;i++){
42 int a=rand()%(n-1)+1;
43 if(!_IsLikePrime(n,a))
44 return false;
45 }
46 return true;
47 }
48 int main()
49 {
50 int n;
51 while(scanf("%d",&n)!=EOF){
52 int num=0;
53 int cnt=0;
54 for(int i=0;i<n;i++){
55 scanf("%d",&num);
56 if(JudgePrime(num,20))
57 cnt++;
58 }
59 printf("%d\n",cnt);
60 }
61 return 0;
62 }
s越大,稳定性越好,但效率会低点。原作者有更好的判定算法,对作者表示感谢。。
posted @
2008-01-26 09:37 小果子 阅读(1191) |
评论 (0) |
编辑 收藏
1
#include <iostream>
2
#include <string>
3
#include <algorithm>
4
#include <hash_map>
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
using namespace std;
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct hashable
{
9
string i;
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
hashable(string iv):i(iv)
{}
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
operator size_t()const
{
12
int ret=i.size();
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int k=0;k!=i.size();++k)
{
14
ret*=10;
15
ret+=i[k]-'A';
16
}
17
return ret;
18
}
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool operator< (hashable r)const
{
20
return i<r.i;
21
}
22
};
23
int main()
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
25
hash_map<hashable,string> hm;
26
hashable a("1");
27
hm[a]="T";
28
cout<<hm[a]<<endl;
29
}
对自定义类型到string的示例
posted @
2008-01-26 09:20 小果子 阅读(273) |
评论 (0) |
编辑 收藏
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不含任何成员函数和成员变量,所以继承不存在额外的开销。
posted @
2008-01-13 11:34 小果子 阅读(1922) |
评论 (1) |
编辑 收藏
说来惭愧,使用了很久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仿函数,理由同使用字符串指针作为索引。
posted @
2008-01-12 18:31 小果子 阅读(9674) |
评论 (0) |
编辑 收藏
想自己开始学语言的时候,因为根本不知道什么书好,所以看到基本是一些国内的,水平一般的书,如果你刚开始学c or c++,推荐c++创始人写的<<the c++ programming language>>,即使是学有所成的人,再看此书也有很大收获我想,慢慢品味,会有收获的。。。以后我会将自己学习此书的笔记写在此,各位路过的大牛指点指点。。。^_^
posted @
2007-12-15 23:22 小果子 阅读(218) |
评论 (0) |
编辑 收藏