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

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

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

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

roots1

贴吧中的“三分钟复现”是算到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++直接输出21000可以精确到个位

这个想法源于一道程序设计课的上机题:任意给定一个正整数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++直接输出21000可以精确到个位”

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】一段很短的计算圆周率的代码”

C语言中的gets()与fgets()

C语言中gets(char*);可以从标准输入中读入一行字符,存入字符串;而用fgets(char*,int,FILE*)可以从文件读入一行字符,其中的整型参数指的是缓冲区大小。

我之前以为get(s)和fgets(s,length,stdin)在不考虑溢出的问题时,行为是完全相同的,但是今天发现它们有个细微的差别。

继续阅读“C语言中的gets()与fgets()”

只用位运算来写整数四则运算程序

整数在计算机中是以二进制形式存储的,整数的运算归根到底是二进制位的逻辑运算。

那么如何用最基本的位运算来实现整数的四则运算?

我今天写了“加”、“减”、“乘”、“除”、“取余”和“取相反数”这几种基本运算,代码中只用到了位运算。

我选择的是short型数值,并用代码循环了所有可能的情况(两个操作数分别从-32768到32767),可以验证我的运算函数的结果和直接做运算的结果是完全相同的(包括溢出的情况)。这些函数经过简单修改很容易支持更多位的整数。

有符号整数右移操作会复制符号位,我把一些函数的参数设置成了unsigned类型的,但是调用函数的时候可以直接传进有符号数。“加”、“减”、“乘”函数传进无符号数也可以得到正确结果。

由于有符号数中负数比正数多一个-32768,所以为了让程序支持边界条件,除法运算中所有操作都是针对负数进行的。

下面附代码:

继续阅读“只用位运算来写整数四则运算程序”

scanf函数中的扫描集

ANSI C语言标准向scanf函数增加了一种新特性,叫做扫描集。利用此特性可以解决一些处理文本时的棘手问题。

最开始源于我对CSV(逗号分隔值)文件的处理。(本文不考虑CSV文件中引号和转义字符等其他特性)

例如下面这段代码

char a[100],b[100];
scanf("%s,%s",a,b);

如果用它读入下面的数据:

Alice,Bob

会直接把“Alice,Bob”赋值给a而继续等待输入b。

我在网上查了这种问题的解决方法,较为简便的一种就是利用扫描集。

继续阅读“scanf函数中的扫描集”

对C语言中不同类型数据计算速度的测试

我对C语言中各种数据类型的四则运算速度进行了测试。

操作系统:Windows 8.1 专业版 (64位)
编译器:GCC 4.8.1 64-bit Release (未开任何优化)
处理器:Intel Core i7-4702MQ

测试数据选择的都是12345和123

测试源程序:

继续阅读“对C语言中不同类型数据计算速度的测试”

从图片看出伪随机数的周期性

今天尝试用代码生成了一张大小为1024*1024,每个像素的RGB值都是随机数的图片(以下图片经过了一定程度的压缩):

random1

本应该是完全随机的图案,但是在图片中却可以明显地看出许多竖线,这显然是伪随机数的周期性导致的。

继续阅读“从图片看出伪随机数的周期性”