高精度小数
寒冰大大
2020-03-09 18:51:32
### 当前我在咕啥
1.目前咕压位高精。
~~2.想都还没想的k次方根~~
3.除法还没优化
~~4.快速乘~~
5为啥n^2的乘法比nlogn的快，~~算了之后用分治乘来折腾下吧~~算了之后用FFT优化一下吧
### 1.1.2 版本内容
1.优化了加法乘法减法
2.增加了k次方根
3.优化掉了1.1.1版本
### 1.1版本的功能
1.新增开方功能（目前只能开平方根，精度不理想，后面用牛顿迭代法试试吧）
2.新增快速幂（目前没遇到bug，过了模板）
3.有两种输出方式（fprint为小数形式，mprint输出方式见P1517）
4.快读
### 1.0版本的功能
1.加减乘除
2.double与该类型加减乘除（加减还没弄）
3.比较大小（小于等于大于）
4.自定义数组长度($width$)，小数点位数($bas$)，除法精度($eps$)，double转该类型精度($deps$)
5.都测了一下，应该没有问题
### 目前已知的缺陷、
1.~~不能与其他类型多次同时读入（应该能和string同时读入）,
比如你前一半读入该类型后一半其他类型是可以的，但是你再读一次该类型就要炸~~ 接了个快读上去，解决了
~~2.代码丑~~
~~4.没有第三点~~
5.double转小数精度不高，貌似在1e-6左右
6.string转小数好像没测
7.后面应该可以优化前面的代码，但是还在加功能，所以没优化。
~~8.使用dev c++~~ 现在用上了vscode
~~有神仙说有bug，目前乘法法肯定不会有bug（能过一整道题），所以问题可能出现在减法和加法上，除法大概率不会bug，~~ 修复了
~~之前0.02会玄学变成0.2~~ 修复了
~~change_num锅了~~ 好了
*暂且命名为mdob*
*转载标明出处*
*有Bug请指出*
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
// code mmm uid:38636
//rules
// 1 a double which is <1 consider as 0.xxx
// 2 a double base place is a const(now here is 69),and the point
// 3 ab integer consider as x.0
//#define int long long
const int width=1020;
const int bas=500;
const int eps=25;
const int deps=1; //double eps
struct mdob{
int a[width];
int l,r;
int fg,wfg;
mdob()
{
memset(a,0,sizeof(a));
l=r=bas;
fg=0;
wfg=0;
}
inline void mov(int p)
{
if(p==0) return ;
if(p>0) for(int i=l;i<=r;i++)
{
if(i-p<=bas&&i>bas) a[i-p-1]=a[i],a[i]=0; else if(i!=bas) a[i-p]=a[i],a[i]=0;
}
if(p<0) for(int i=r;i>=l;i--)
{
if(i-p>=bas&&i<bas) a[i-p+1]=a[i],a[i]=0;
else if(i!=bas) a[i-p]=a[i],a[i]=0;
}
if(p>0)
{
l=l-p; if(a[l]==0) l++;
r=max(r-p,bas+1);
}
if(p<0)
{
l=min(l-p,bas-1);
r=max(r-p,bas+1); if(a[r]==0) r--;
}
return ;
}
void war()
{
if(fg==0) return;
wfg=1;
for(int i=l;i<=r;i++)
{
if(i==bas) continue;
a[i]=-a[i];
}
}
void peace()
{
if(fg==0) return;
wfg=0;
for(int i=l;i<=r;i++)
{
if(i==bas) continue;
a[i]=-a[i];
}
}
//judge a num which <0 look at the firstplace
inline void check()
{
int i,leave=0;
if(l==bas) l--;
if(r==bas) r--;
if(wfg) peace();
for(i=r;i>=l;i--)
{
if(i==bas) continue;
a[i]+=leave;
leave=0;
if(a[i]>=10)
{
leave+=a[i]/10,a[i]%=10;
if(i==l) l--;
}
}
while(a[l]==0&&l<bas-1) l++; //consider as 0,xxx
while(a[r]==0&&r>bas+1) r--; //consider as xxx.0
}
inline void clr()
{
//memset(a,0,sizeof(a));
for(int i=l;i<=r;i++) a[i]=0;
l=r=bas;
fg=0;
}
inline void mread()
{
clr();
l=r=bas;
fg=0;
stack <int> s;
queue <int> q;
char p;
p=getchar();
while(p<'0'||p>'9') if(p=='-') fg=1,p=getchar();
while(p>='0'&&p<='9') s.push(p-'0'),p=getchar();
while(!s.empty()) a[--l]=s.top(),s.pop();
if(p!='.')
{
a[++r]=0;
return ;
}
p=getchar();
while(p>='0'&&p<='9') q.push(p-'0'),p=getchar();
while(!q.empty()) a[++r]=q.front(),q.pop();
return ;
check();
}
int _10n(int x)
{
if(x==0) return 1;
if(x==1) return 10;
if(x==2) return 100;
if(x==3) return 1000;
if(x==4) return 10000;
if(x==5) return 100000;
if(x==6) return 1000000;
if(x==7) return 10000000;
return 0; // vscode 的要求
}
void doudob(double x)
{
clr();
double mutis;
if(0-x>0.0000001) fg=1,x=-x;
mutis=x-floor(x);
int rp,lp; //point right,point left
lp=floor(x);
mutis=1.0*mutis*_10n(deps);
l=r=bas;
queue <int> s;
stack <int> q;
while(lp)
s.push(lp%10),lp/=10;
int ts=1;
rp=floor(mutis);
while(ts<=deps)
{
if(rp)
q.push(rp%10),rp/=10;
else q.push(0);
ts++;
}
while(!s.empty()) a[--l]=s.front(),s.pop();
while(!q.empty()) a[++r]=q.top(),q.pop();
l=min(l,bas-1);
r=max(r,bas+1);
}
inline void strdob(string st)
{
int muti=st.size();
clr();
l=r=bas;
fg=0;
stack <int> s;
queue <int> q;
int p=0;
while((st[p]<'0'||st[p]>'9')&&p<muti) if(st[p]=='-') fg=1,p++;
while(st[p]>='0'&&st[p]<='9'&&p<muti) s.push(st[p]-'0'),p++;
while(!s.empty()) a[--l]=s.top(),s.pop();
if(st[p]!='.')
{
a[++r]=0;
return ;
}
p++;
while(st[p]>='0'&&st[p]<='9'&&p<muti) q.push(st[p]-'0'),p++;
while(!q.empty()) a[++r]=q.front(),q.pop();
return ;
check();
}
inline int getnowplace(int p)
{
if(p>bas) return p-l;
else return p-l+1;
}
inline void mprint() //printf like P1517 luogu
{
check();
int i;
if(fg) cout<<'-';
if(a[l]!=0)for(i=l;i<bas;i++) cout<<a[i];
if(r==bas)
{
cout<<endl;
return ;
}
cout<<".";
for(i=bas+1;i<=r;i++) cout<<a[i];
cout<<endl;
cout<<endl;
return ;
}
inline void fmprint() //printf like P1517 luogu
{
check();
int i;
if(fg) cout<<'-';
if(a[l]!=0)for(i=l;i<bas;i++) cout<<a[i];
cout<<".";
for(i=bas+1;i<=r;i++) cout<<a[i];
cout<<endl;
return ;
}
inline void change_num(int x)
{
clr();
if(x<0) fg=1,x=-x;
while(x)
{
a[--l]=x%10;
x/=10;
}
a[++r]=0;
check();
}
inline int findl()
{
int i=l;
while(a[i]<=0) if(i==bas-1) i+=2; else i++;
return i;
}
};
//n^2的乘法
mdob getmul(mdob x,mdob y)
{
int target[width];
//memset(target,0,sizeof(target));
mdob ans;
ans.l=ans.r=bas;
ans.clr();
ans.fg=x.fg^y.fg;
int i,j;
int zeropla=x.getnowplace(bas-1)+y.getnowplace(bas-1);
int trg; //结束位置
trg=x.getnowplace(x.r)+y.getnowplace(y.r)-1;
for(i=1;i<=trg;i++) target[i]=0;
for(i=x.l;i<=x.r;i++)
{
if(i==bas) continue;
for(j=y.l;j<=y.r;j++)
{
if(j==bas) continue;
target[x.getnowplace(i)+y.getnowplace(j)-1]+=x.a[i]*y.a[j];
}
}
int muti=x.getnowplace(x.r)+y.getnowplace(y.r)-1;
for(i=zeropla-1;i>=1;i--) ans.a[--ans.l]=target[i];
for(i=zeropla;i<=muti;i++) ans.a[++ans.r]=target[i];
ans.check();
return ans;
}
mdob getmul(mdob x,int y)
{
mdob k;
k.change_num(y);
return getmul(x,k);
}
mdob operator -(mdob x,mdob y)
{
mdob ans;
int looker=0;
y.fg=1-y.fg;
y.war();
x.war();
int i,st=min(x.l,y.l),ed=max(x.r,y.r);
for(i=st;i<=ed;i++)
{
if(i==bas) continue;
ans.a[i]=x.a[i]+y.a[i];
if(ans.a[i]!=0&&!looker) looker=1,ans.fg=ans.a[i]<0;
}
ans.l=st;
ans.r=ed;
int muti=x.getnowplace(x.r)+y.getnowplace(y.r)-1;
if(ans.fg==1)
{
for(i=ed;i>=st+1;i--) if(ans.a[i]>0)
{
ans.a[i]-=10;
if(i-1==bas) ans.a[i-2]++; else ans.a[i-1]++;
}
}
if(ans.fg==0)
{
for(i=ed;i>=st+1;i--) if(ans.a[i]<0)
{
ans.a[i]+=10;
if(i-1==bas) ans.a[i-2]--; else ans.a[i-1]--;
}
}
ans.peace();
ans.check();
return ans;
}
mdob operator +(mdob x,mdob y)
{
mdob ans;
int looker=0;
y.war();
x.war();
int i,st=min(x.l,y.l),ed=max(x.r,y.r);
for(i=st;i<=ed;i++)
{
if(i==bas) continue;
ans.a[i]=x.a[i]+y.a[i];
if(ans.a[i]!=0&&!looker) looker=1,ans.fg=ans.a[i]<0;
}
ans.l=st;
ans.r=ed;
int muti=x.getnowplace(x.r)+y.getnowplace(y.r)-1;
if(ans.fg==1)
{
for(i=ed;i>=st+1;i--) if(ans.a[i]>0)
{
ans.a[i]-=10;
if(i-1==bas) ans.a[i-2]++; else ans.a[i-1]++;
}
}
if(ans.fg==0)
{
for(i=ed;i>=st+1;i--) if(ans.a[i]<0)
{
ans.a[i]+=10;
if(i-1==bas) ans.a[i-2]--; else ans.a[i-1]--;
}
}
ans.peace();
ans.check();
return ans;
}
//10*log(n)的除法
mdob operator /(mdob x,mdob y)
{
mdob ans;
ans.l=ans.r=bas;
ans.clr();
ans.fg=x.fg^y.fg;
int i,j;
int deltapla;
int xl,yl;
i=x.l; while(x.a[i]<0) if(i==bas-1) i+=2; else i++; xl=i;
i=y.l; while(y.a[i]<0) if(i==bas-1) i+=2; else i++; yl=i;
deltapla=yl-xl;
if((xl<bas&&yl>bas)||(xl>bas&&yl<bas))
{
if(deltapla>0) deltapla--; else deltapla++;
}
y.mov(deltapla);
mdob looker;
int p=y.l;
x.fg=0;
y.fg=0;
ans.l=p;
ans.r=bas+eps;
while(p<=bas+eps)
{
if(p==bas) p++;
int con=0;
while(!x.fg)
{
x=x-y;
con++;
}
con--;
if(con==-1) con++;
else
{
x=x+y;
ans.a[p]+=con;
}
y.mov(-1);
p++;
}
ans.check();
return ans;
}
//o(n log n )乘法
mdob operator *(mdob a,mdob b)
{
mdob ans;
mdob looker;
ans.clr();
int fg=a.fg^b.fg;
a.fg=b.fg=0;
int i,j;
for(i=b.l;i<=bas;i++)
{
looker.clr();
if(b.a[i]==0) continue;
looker=getmul(a,b.a[i]);
looker.mov(bas-i-1);
ans=ans+looker;
}
for(i=bas+1;i<=b.r;i++)
{
looker.clr();
if(b.a[i]==0) continue;
looker=getmul(a,b.a[i]);
looker.mov(bas-i);
ans=ans+looker;
}
ans.fg=fg;
return ans;
}
bool operator ==(mdob a,mdob b)
{
int al=a.findl();
int bl=a.findl();
int looker=0;
if(a.fg==1) looker=1;
if(al<bl&&looker) return 0;
if(al>bl&&!looker) return 0;
if(al>bl&&looker) return 0;
if(al<bl&&!looker) return 0;
int i;
int st=a.l;
int ed=max(a.r,b.r);
for(i=st;i<=ed;i++)
{
if(i==bas) continue;
if(a.a[i]!=b.a[i]) return 0;
}
return 1;
}
bool operator <(mdob a,mdob b)
{
if(a==b) return 0;
if(a.fg>b.fg) return 1;
if(a.fg<b.fg) return 0;
int al=a.findl();
int bl=b.findl();
int looker=0;
if(a.fg==1) looker=1;
if(al<bl&&looker) return 1;
if(al>bl&&!looker) return 1;
if(al>bl&&looker) return 0;
if(al<bl&&!looker) return 0;
int i;
int st=a.l;
int ed=max(a.r,b.r);
for(i=st;i<=ed;i++)
{
if(i==bas) continue;
if(a.a[i]>b.a[i]&&looker) return 1;
if(a.a[i]>b.a[i]&&!looker) return 0;
if(a.a[i]<b.a[i]&&looker) return 0;
if(a.a[i]<b.a[i]&&!looker) return 1;
}
return 0; //vscode的要求
}
bool operator >(mdob a,mdob b)
{
int x=0,y=0;
x=a==b;
y=a<b;
if(x==1) return 0;
return y^1;
}
bool operator <=(mdob a,mdob b)
{
return (a<b||a==b);
}
bool operator >=(mdob a,mdob b)
{
return (a>b||a==b);
}
mdob operator *(mdob x,double y)
{
mdob ans,yy;
yy.doudob(y);
ans=x*y;
return ans;
}
mdob operator +(mdob x,int y)
{
mdob yy;
yy.change_num(y);
return x+yy;
}
mdob operator -(mdob x,int y)
{
mdob yy;
yy.change_num(y);
return x-yy;
}
mdob operator /(mdob x,double y)
{
mdob ans,yy;
yy.doudob(y);
ans=x/yy;
return ans;
}
mdob operator /(mdob x,int y)
{
double c=1.0*y;
mdob ans;
ans=x/c;
return ans;
}
mdob _sqrt(mdob x)
{
mdob l,r,mid;
l.strdob("0.0");
mdob target,ans;
target.strdob("1.0");
target.mov(-deps);
//just for which is >0
if(x.fg==1) return l;
if(x==l) return l;
r=x;
x.mprint();
while(r-l>target)
{
mid=(l+r)/2;
mid.r=min(mid.r,deps+bas+1);
if(mid*mid<=x) l=mid,ans=mid;
else r=mid;
}
if(mid.a[mid.r]>=5) mid.a[--mid.r]++;
return ans;
}
mdob _pow(int x,mdob &y)
{
mdob ans;
if(x==0) {ans.strdob("1.0"); return ans;}
if(x==1) return y;
ans.strdob("1.0");
if(x&1) ans=ans*y;
ans=ans*_pow(x/2,y)*_pow(x/2,y);
return ans;
}
mdob take_root(int x,mdob y)
{
mdob target;
target.strdob("1.0");
target.mov(-deps);
mdob ans;
ans.change_num(0);
if(x<=0) return ans;
if(y.fg==1&&(x&1)==0) return ans;
if(y==ans) return ans;
int looker=0;
if(y.fg) looker=1,y.fg=0;
mdob l,r,mid;
l=ans; r=y;
while(r-l>target)
{
mid=(l+r)/2;
mid.r=min(mid.r,deps+bas+1);
if(_pow(x,mid)<=y) l=mid,ans=mid;
else r=mid;
}
if(ans.a[bas+1]>=5&&!looker) ans=ans+1;
else if(ans.a[bas+1]<=5&&looker) ans=ans-1;
if(looker) ans.fg=1;
return ans;
}
int qread()
{
int ans=0,f=1;
char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1; c=getchar(); };
while(isdigit(c)) { ans=ans*10+c-'0'; c=getchar(); }
return f*ans;
}
signed main()
{
ios::sync_with_stdio(false);
int i,j;
mdob a,b,c;
double t,t2;
int x;
string s;
while(1)
{
a.mread();
b.mread();
c=a*b;
c.mprint();
}
return 0;
}
```