高精乘速度问题
  • 板块学术版
  • 楼主_8008008
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/25 10:53
  • 上次更新2023/11/3 07:46:59
查看原帖
高精乘速度问题
803885
_8008008楼主2023/7/25 10:53

我很好奇我这种歪门邪道的方法比人家正常的还快,还是我计时器弄错了
code:

#include<iostream>
#include<string>
#include<cstdlib>
#include<windows.h>
#include<ctime>
using namespace std;
//高精度比大小
//a>b return 1;b>a return -1;a=b return 0;
int  bidaxiao(string a, string b){
	int lena=a.length(),lenb=b.length(),flag;
	if (a[0]=='-'&&b[0]=='-')flag=-1;
	else if(a[0]=='-'&&b[0]!='-')return -1;
	else if(a[0]!= '-'&&b[0]=='-')return 1;
	else flag=1;
	if (lena<lenb)return -flag;
	if (lena>lenb)return flag;
	for(int i=0;i<max(lena,lenb);i++) {
		if (a[i]!= '.'){
			if (a[i]-'0'>b[i]-'0')return flag;
			if (a[i]-'0'<b[i]-'0')return -flag;
		}
	}
	return 0;
}
//高精度加法
//结果为string类型且去除整数部分前置0、小数部分后置0,小数点为英文句号"."
//a>=0,b>=0
string jiafa(string a, string b) {
	string a1 = "", a2 = "", b1 = "", b2 = "";
	{
		int i;
		for (i=a.length()-1;i>-1;i--){
			if(a[i]=='.')break;
			a2=a[i]+a2;
		}
		for(i--;i>-1;i--){
			a1=a1+a[i];
		}
		for(i=b.length()-1;i>-1;i--) {
			if(b[i] == '.')break;
			b2=b[i]+b2;
		}
		for (i--;i>-1;i--)b1= b1 + b[i];
		if (a1=="")a1=a2,a2 = "";
		if (b1=="")b1=b2,b2="";
	}
	int lena1 = a1.length(), lenb1 = b1.length(), lena2 = a2.length(), lenb2 = b2.length();
	{
		if(lena1<lenb1)for(int i=0;i<lenb1-lena1;i++)a1="0"+a1;
		else for(int i=0;i<lena1-lenb1;i++)b1="0"+b1;
		if (lena2<lenb2)for(int i=0;i<lenb2-lena2;i++)a2+="0";
		else for(int i=0;i<lena2-lenb2;i++)b2+="0";
	}
	string ans1= "",ans2 = "";int jinwei=0,yujia;
	{
		for(int i=max(lena2, lenb2)-1;i>-1;i--) {
			yujia=(a2[i]-'0'+b2[i]-'0'+jinwei);
			ans2=to_string(yujia % 10)+ans2;
			if (yujia>9)jinwei = 1;
			else jinwei = 0;
		}
		for(int i=max(lena1,lenb1)-1;i>-1;i--) {
			yujia=(a1[i]-'0'+b1[i]-'0'+jinwei);
			ans1=to_string(yujia%10)+ans1;
			if(yujia>9)jinwei = 1;
			else jinwei = 0;
		}
		if(jinwei!=0)ans1=to_string(jinwei)+ans1;
	}
	{
		string str = "";int i = 0;
		for(i;i<ans1.length()-1;i++)if(ans1[i]!='0')break;
		for(i;i<ans1.length();i++)str=str+ans1[i];ans1=str;i=ans2.length()-1;
		str="";
		for(i;i>-1;i--)if(ans2[i]!='0')break;
		for (i;i>-1;i--)str=ans2[i]+str;
		ans2=str;
	}
	string finish_ans;
	if (ans2=="")finish_ans = ans1;
	else finish_ans=ans1+"."+ans2;
	return finish_ans;
}
//0<=b<=a
//高精度减法
//结果为string类型且去除整数部分前置0、小数部分后置0,小数点为英文句号"." 负号为"-"
string jianfa(string a, string b){
	string a1="",a2="",b1="",b2="";
	{
		int i;
		for(i=a.length()-1;i>-1;i--) {
			if(a[i] == '.'||a[i] == '-')break;
			a2=a[i]+a2;
		}
		for(i--;i>-1;i--) {
			if(a[i]=='.'||a[i]=='-')break;
			a1+=a[i];
		}
		for(i=b.length()-1;i>-1;i--) {
			if(b[i]=='.'||b[i]=='-')break;
			b2=b[i]+b2;
		}
		for(i--;i>-1;i--) {
			if(b[i]=='.'||b[i]=='-')break;
			b1+=b[i];
		}
		if(a1=="")a1=a2,a2 = "";
		if(b1=="")b1=b2,b2 = "";
	}
	int lena1=a1.length(),lenb1=b1.length(),lena2=a2.length(),lenb2 = b2.length();
	{
		if (lena1<lenb1)for(int i=0;i<lenb1-lena1;i++)a1="0"+a1;
		else for(int i=0;i<lena1-lenb1;i++)b1="0"+b1;
		if(lena2<lenb2)for(int i=0;i<lenb2-lena2;i++)a2=a2+"0";
		else for(int i=0;i<lena2-lenb2;i++)b2+="0";
	}
	string ans1,ans2;
	int tuiwei=0,yujian=0;
	{
		for (int i=max(lena2,lenb2)-1;i>-1;i--) {
			yujian=(a2[i]-'0')-(b2[i]-'0')-tuiwei;
			if(yujian<0)yujian=yujian+10,tuiwei=1;
			else tuiwei=0;
			ans2=to_string(yujian)+ans2;
		}
		for (int i=max(lena1,lenb1)-1;i>-1;i--) {
			yujian=(a1[i]-'0')-(b1[i]-'0')-tuiwei;
			if(yujian<0)yujian=yujian+10,tuiwei=1;
			else tuiwei=0;
			ans1=to_string(yujian)+ans1;
		}
	}
	{
		string str = "";int i=0;
		for (i;i<ans1.length()-1;i++)if(ans1[i]!='0')break;
		for (i;i<ans1.length();i++)str=str+ans1[i];
		ans1=str,str = "";i=ans2.length()-1;
		for (i;i>-1;i--)if(ans2[i]!='0')break;
		for(i;i>-1;i--)str=ans2[i]+str;
		ans2=str;
	}
	string finish_ans;
	if(ans2 == "")finish_ans = ans1;
	else finish_ans=ans1+"."+ans2;
	return finish_ans;
}
//a>=0,b>=0
//需要高精度加法 
string chengfa(string a,string b){
	string a1="",b1="",ans="0",sum[10]{"0","","","","","","","","",""};int xsw=0,flag=0;
	for(int i=0;i<a.length();i++){
		if(flag)xsw++;
		if(a[i]!='.')a1+=a[i];
		else flag=1;
	}
	flag=0;
	for(int i=0;i<b.length();i++){
		if(flag)xsw++;
		if(b[i]!='.')b1+=b[i];
		else flag=1;
	}
	sum[1]=a1;
	for(int i=2;i<10;i++)sum[i]=jiafa(sum[i-1],a1);
	for(int i=0;i<b1.length();i++){
		string c=sum[b1[i]-'0'];
		for(int j=0;j<b1.length()-i-1;j++)c+="0";
		ans=jiafa(ans,c);
	}
	if(xsw!=0){
		int lenans=ans.length();
		ans+=" ";
		for(int i=lenans-1;i>=lenans-xsw;i--)ans[i+1]=ans[i];
		ans[lenans-xsw]='.';
	}
	return ans;
}
int compare(string str1,string str2)
{
    if(str1.length()>str2.length()) return 1;
    else if(str1.length()<str2.length())  return -1;
    else return str1.compare(str2);
}
//高精度加法
//只能是两个正数相加
string add(string str1,string str2)//高精度加法
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    //前面补0,弄成长度相同
    if(len1<len2)
    {
        for(int i=1;i<=len2-len1;i++)
           str1="0"+str1;
    }
    else
    {
        for(int i=1;i<=len1-len2;i++)
           str2="0"+str2;
    }
    len1=str1.length();
    int cf=0;
    int temp;
    for(int i=len1-1;i>=0;i--)
    {
        temp=str1[i]-'0'+str2[i]-'0'+cf;
        cf=temp/10;
        temp%=10;
        str=char(temp+'0')+str;
    }
    if(cf!=0)  str=char(cf+'0')+str;
    return str;
}
//高精度减法
//只能是两个正数相减,而且要大减小
string sub(string str1,string str2)//高精度减法
{
    string str;
    int tmp=str1.length()-str2.length();
    int cf=0;
    for(int i=str2.length()-1;i>=0;i--)
    {
        if(str1[tmp+i]<str2[i]+cf)
        {
            str=char(str1[tmp+i]-str2[i]-cf+'0'+10)+str;
            cf=1;
        }
        else
        {
            str=char(str1[tmp+i]-str2[i]-cf+'0')+str;
            cf=0;
        }
    }
    for(int i=tmp-1;i>=0;i--)
    {
        if(str1[i]-cf>='0')
        {
            str=char(str1[i]-cf)+str;
            cf=0;
        }
        else
        {
            str=char(str1[i]-cf+10)+str;
            cf=1;
        }
    }
    str.erase(0,str.find_first_not_of('0'));//去除结果中多余的前导0
    return str;
}
//高精度乘法
//只能是两个正数相乘
string mul(string str1,string str2)
{
    string str;
    int len1=str1.length();
    int len2=str2.length();
    string tempstr;
    for(int i=len2-1;i>=0;i--)
    {
        tempstr="";
        int temp=str2[i]-'0';
        int t=0;
        int cf=0;
        if(temp!=0)
        {
            for(int j=1;j<=len2-1-i;j++)
              tempstr+="0";
            for(int j=len1-1;j>=0;j--)
            {
                t=(temp*(str1[j]-'0')+cf)%10;
                cf=(temp*(str1[j]-'0')+cf)/10;
                tempstr=char(t+'0')+tempstr;
            }
            if(cf!=0) tempstr=char(cf+'0')+tempstr;
        }
        str=add(str,tempstr);
    }
    str.erase(0,str.find_first_not_of('0'));
    return str;
}
int main() {
	string a="",b="",ans1,ans2,c;
	for(int i=1;i<=100;i++){
		for(int i=0;i<100;i++)a+=to_string(rand());
		for(int i=0;i<100;i++)b+=to_string(rand());
     //弄了随机数作比较
		double time1,time2;
		time1=clock();ans1=chengfa(a,b);time1=clock()-time1;
		time2=clock();ans2=mul(a,b);time2=clock()-time2;
		if(bidaxiao(ans1,ans2)==0)c="AC";else c="WA";
		cout<<"#"<<i<<":"<<c<<" true:"<<time1<<" my:"<<time2<<endl<<"true:"<<ans1<<endl<<"yours;"<<ans2<<endl<<endl;
		a="",b="";
	}
	return 0;
}

我找了份高精度代码和我自己的作比较 找的样本函数是这儿
他的函数名是英文开头几个 我的是拼音
在自己电脑上测试time1和time有10倍之差 不知道评测机上情况怎样 正常写法应该是模拟竖式计算 但我是把0-10乘以因数1的情况都算出来存在sum[0-10]再ans+=sum[b[i]](高精度加法&&b[i]需要-'0')

2023/7/25 10:53
加载中...