c++符号计算大量多项式的方法(符号表过大时的编译出错问题)
在用C++符号计算库GiNaC进行符号计算时,由于需要处理的多项式太多,他们又被定义在.cpp/.h文件里,因此g++编译总是在运行很久之后报错失败;我们构思了一种从外部读取文本再解析为对应符号的方法,来解决这个问题;
问题描述
在用C++符号计算库GiNaC进行符号计算时,由于需要处理的多项式太多,他们又被定义在.cpp/.h文件里:
std::vector<GiNaC::ex> ITEMS_ZTT {t1*z664, t2*z664,...};
std::vector<GiNaC::ex> EQUATIONS_420 {t39*z979 + t40*z979 + z749...,...};
这时候编译,会因内存不足(符号表太大了)而报错:
[hanss@Tenda cpp]$ g++ app_gauss.cpp -o app -lginac -lcln
g++: internal compiler error: Segmentation fault (program cc1plus)
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-7/README.Bugs> for instructions.
解决方法
一个直接的想法就是,既然"把公式写进去"这种操作定义的符号过多,那么在编译时不定义,运行时再定义可以吗?
C++怎么动态地用一个字符串声明一个变量?
事实上,不能;因为符号表是在程序创建之初就生成的;
那么折衷的想法就是:我只创建基础的符号,比如变元:
GiNaC::symbol x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5"), x6("x6"), x7("x7"), x8("x8"), x9("x9");
然后把要计算的公式存放在静态的.dat文件里面,然后只需要读取它然后解析即可:
z1*c1 + z2*c2 + z3*c3 + z4*c4 + z5*c5 + z6*c6 + z7 + z8
z1*c2 + z3*c4 + z1 + z3
...
因此,需要的功能包括文件读取/符号解析/公式生成,整个程序如下:
#include <vector>
#include <string>
#include <iostream>
#include <cstring>
#include <fstream>
#include <ginac/ginac.h>
#include <map>
#define MAX_LEN_LINE 200
using namespace std;
std::vector<string> read_formulas(const string& FILE_NAME)
{
char THIS_LINE[MAX_LEN_LINE];
string FORMULA_STRING;
string TMP_VAR;
std::ifstream FILEIN(FILE_NAME);
std::vector<string> FORMULA_STRING_SET;
for (;;)
{
FILEIN.getline( THIS_LINE, sizeof(THIS_LINE));
if ( FILEIN.eof()){break;}
std::vector<int> COEFF;
for (int j = 0; j < MAX_LEN_LINE; ++j)
{
if ( THIS_LINE[j]=='\0'){break;}
TMP_VAR = THIS_LINE[j];
FORMULA_STRING += TMP_VAR;
}
FORMULA_STRING_SET.push_back(FORMULA_STRING);
FORMULA_STRING.clear();
}
FILEIN.close();
return FORMULA_STRING_SET;
}
vector<string> split(const string& PROCESS_STRING, const string& DELIM) {
vector<string> res;
if("" == PROCESS_STRING) return res;
char * strs = new char[PROCESS_STRING.length() + 1] ;
strcpy(strs, PROCESS_STRING.c_str());
char * d = new char[DELIM.length() + 1];
strcpy(d, DELIM.c_str());
char *p = strtok(strs, d);
while(p) {
string s = p;
res.push_back(s);
p = strtok(NULL, d);
}
return res;
}
GiNaC::ex make_poly_from_string(const string& PROCESS_STRING,std::map<string,GiNaC::symbol> MAP_STR_SYMBOL)
{
std::vector<string> STR_MONOMIALS = split(PROCESS_STRING, " + ");
GiNaC::ex POLYNOMIAL = 0;
for (int INDEX_i = 0; INDEX_i < STR_MONOMIALS.size(); ++INDEX_i)
{
std::vector<string> STR_SYMBOLS = split(STR_MONOMIALS[INDEX_i], "*");
if (STR_SYMBOLS.size()==1)
{
POLYNOMIAL+=MAP_STR_SYMBOL[STR_SYMBOLS[0] ];
continue;
}
GiNaC::ex MONOMIAL = 1;
for (int INDEX_j = 0; INDEX_j < STR_SYMBOLS.size(); ++INDEX_j)
{
MONOMIAL *= MAP_STR_SYMBOL[STR_SYMBOLS[INDEX_j] ];
}
POLYNOMIAL += MONOMIAL;
}
return POLYNOMIAL;
}
std::map<string,GiNaC::symbol> construct_map(const std::vector<GiNaC::symbol>& ITEMS_X)
{
std::map<string,GiNaC::symbol> MAP_STR_SYMBOL;
for (int INDEX_i = 0; INDEX_i < ITEMS_X.size(); ++INDEX_i)
{
MAP_STR_SYMBOL[ITEMS_X[INDEX_i].get_name()] = ITEMS_X[INDEX_i];
}
return MAP_STR_SYMBOL;
}
std::vector<GiNaC::ex> ppsh_read_formulas_from_file(const string& FILE_NAME, std::map<string,GiNaC::symbol> MAP_STR_SYMBOL)
{
std::vector<GiNaC::ex> EQUATIONS_192;
std::vector<string> FORMULA_STRING_SET = read_formulas("poly.dat");
for (int INDEX_i = 0; INDEX_i < FORMULA_STRING_SET.size(); ++INDEX_i)
{
EQUATIONS_192.push_back(make_poly_from_string(FORMULA_STRING_SET[INDEX_i],MAP_STR_SYMBOL));
}
return EQUATIONS_192;
}
int main()
{
GiNaC::symbol x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5"), x6("x6"), x7("x7"), x8("x8"), x9("x9");
std::vector<GiNaC::symbol> ITEMS_X {x1, x2, x3, x4, x5, x6, x7, x8, x9};
std::map<string,GiNaC::symbol> MAP_STR_SYMBOL = construct_map(ITEMS_X);
std::vector<GiNaC::ex> EQUATIONS_192 = ppsh_read_formulas_from_file("poly.dat",MAP_STR_SYMBOL);
for (int i = 0; i < EQUATIONS_192.size(); ++i)
{
cout << EQUATIONS_192[i] <<endl;
}
}
整个项目可以参考我们组写的有限域上多项式的符号计算程序:
https://github.com/Luomin1993/PPSH-41
另一个小问题:怎么在没有root权限的服务器上编译源码并引用
在没有root权限的服务器上,你需要编译一个库(CLN),还需要编译一个依赖CLN的库GiNac,最后还要用g++编译你的依赖GiNac的c++程序,这一切可以按如下操作:
[hanss@Tenda cpp]$ ./configure --prefix=$HOME/usr // 编译CLN之前
[hanss@Tenda cpp]$ make // 编译CLN
[hanss@Tenda cpp]$ make install // 安装CLN
[hanss@Tenda cpp]$ export PKG_CONFIG_PATH=$HOME/usr/lib/pkgconfig // 指明CLN库
[hanss@Tenda cpp]$ ./configure --prefix=$HOME/usr // 编译GiNaC之前
[hanss@Tenda cpp]$ make // 编译GiNaC
[hanss@Tenda cpp]$ make install // 安装GiNaC
[hanss@Tenda cpp]$ g++ hello.cc -o hello -I$HOME/usr/include -L$HOME/usr/lib -lginac -lcln // 编译你的程序
[hanss@Tenda cpp]$ export LD_LIBRARY_PATH=$HOME/usr/lib // 运行程序之前
[hanss@Tenda cpp]$ ./hello // 运行程序
|