高精度乘法(Trachtenberg速算法)

一.介绍:

Trachtenberg速算法:(转载)

二.代码实现:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;struct node
{int pos;char num;
};const int M = 1010;
struct node a[M], b[M];
int len = 0;
int len1 = 0;
int len2 = 0;
int ans[M * M];void Print()
{int i = len;while(!ans[i])i--;for(; i >= 0; --i)printf("%d", ans[i]);printf("\n");
}void Trachtenberg()
{while(b[0].pos != len1 + 1){for(int i = 0; i < len2; ++i){if(b[i].pos == 0)ans[len] += ((b[i].num - '0') * (a[len1 - 1].num - '0')) % 10;else if(b[i].pos == len1)ans[len] += ((b[i].num - '0') * (a[0].num - '0')) / 10;else if(b[i].pos > 0 && b[i].pos < len1)ans[len] += ((b[i].num - '0') * (a[len1 - b[i].pos - 1].num - '0')) % 10 + ((b[i].num - '0') * (a[len1 - b[i].pos].num - '0')) / 10;b[i].pos++;}ans[len + 1] += ans[len] / 10;ans[len] %= 10;len++;}Print();
}void Scan(string s1, string s2)
{len1 = s1.size();len2 = s2.size();for(int i = 0; i < len1; ++i)a[i].num = s1[i];for(int i = 0; i < len2; ++i)b[i].num = s2[i];for(int i = len2 - 1; i >= 0; --i){if(i == len2 - 1)b[i].pos = 0;elseb[i].pos = b[i + 1].pos - 1;}
}int main()
{string s1, s2;cin >> s1 >> s2;Scan(s1, s2);if(a[0].num == '0' && len1 == 1 || b[0].num == '0' && len2 == 1)printf("0\n");elseTrachtenberg();return 0;
}

 


本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击【内容举报】进行投诉反馈!

相关文章

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部