C/C++ – 负一的平方根

绘制整系数多项式复数根的分布

我在百度贴吧Mathematica吧的这个帖子看到有人在研究如下问题：

求解所有系数为1或-1的n次多项式的根，然后把所有这样的根绘制到复平面上。

我想起以前在Matrix67的博客上也看到过这个问题，里面介绍了Sam Derbyshire用Mathematica跑了四天四夜（也有说法是三天三夜）生成了n=24的所有根，然后用Java程序绘图，得到了下图：

贴吧中的“三分钟复现”是算到n=17的情况。由于n增加1导致需要求解方程的数量翻倍，每个方程中根的个数也增加1，所以我估计了一下，n=24时大约需要求出24*2^24=402M个解。（24次多项式包括常数项有25个系数，但是由于对称性可以省去一半计算。）这些计算显然不需要以天为数量级的时间。

我决定用C语言解决这个问题，同时改善一下显示的效果，并尝试绘制分辨率更高的图。

解决这个问题有两个比较麻烦的事：

如何求解多项式的根
图上的颜色按照什么绘制

继续阅读“绘制整系数多项式复数根的分布”

C++的直接初始化与复制初始化

C++中的直接初始化指的是直接调用类的构造函数进行初始化，例如

string a; //调用默认构造函数
string a("hello"); //调用参数为const char *类型的构造函数
string b(a); //调用拷贝构造函数

复制初始化指的是用“=”号来初始化对象，例如

string a="hello";
string b=a;

在上面的例子中，这两种写法是完全等效的，但是直接初始化和复制初始化在一些情况下还是有区别的。

继续阅读“C++的直接初始化与复制初始化”

为什么C++直接输出2¹⁰⁰⁰可以精确到个位

这个想法源于一道程序设计课的上机题：任意给定一个正整数N(N<=100)，计算2的n次方的值。这道题的本意是练习高精度计算，但是可以发现，使用long double类型调用pow函数就足够了。当然我还是用高精度计算写的。然而，我发现即使仅使用double，甚至用float，在C++中都可以输出正确的答案。运行下面的C++代码：

#include<iostream>
#include<cmath>

using namespace std;

int main(){
    int x;
    cin>>x;
    cout.precision(0);
    cout<<fixed<<pow(2,x);
    return 0;
}

输入1000，程序输出一个超过300位的结果，虽然这早已超出double和long double的精度，但是运算结果是完全正确的。

至于结果的正确性，比较方便的方法就是与Python给出的结果进行对比。在Python的控制台中输入2**1000可以直接得到高精度计算的结果，很方便。

为什么结果是精确的呢？

继续阅读“为什么C++直接输出2¹⁰⁰⁰可以精确到个位”

C/C++中的const可信吗？

C和C++中有很多函数的参数类型使用了const这个关键字。例如C语言string.h头文件中的strcpy字符串复制函数，它的原型是

char * strcpy (char * Dest, const char * Source)

其中的const表示strcpy函数保证不修改Source指向的内存中的数据，而未加const的Dest指向的内容却可以被修改。

再如stdlib.h中的qsort快速排序函数原型如下：

void qsort (void * Base, size_t NumOfElements, size_t SizeOfElements, int (*PtFuncCompare)(const void *, const void *))

其中最后一个参数是一个函数指针，qsort需要你提供一个比较函数，这个比较函数以两个指针为参数，const要求你不能通过指针修改其指向的数据。

然而指针类型的参数加了const的函数就真的能保证它不会修改数据吗？

继续阅读“C/C++中的const可信吗？”

【π Day】一段很短的计算圆周率的代码

今天是3月14日，圆周率日。

我在网上看到了一段很短的计算圆周率的代码，可以算到8000位。我把程序输出的结果和Mathematica的结果比较了一下，验证了程序是正确的。

通过更改c的值和f数组的大小，可以算到更多的位。

我没弄明白这段代码的原理，如果有谁知道，欢迎在回复中告诉我。

简短版：

#include<stdio.h>
int a=10000,b=0,c=28000,d,e=0,f[28010],g;
main(){
for(;b-c;)f[b++]=a/5;
for(;d=0,g=c*2;c-=14,printf("%04d",e+d/a),e=d%a)
for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);
}

正常版：
继续阅读“【π Day】一段很短的计算圆周率的代码”