当前位置:网站首页>High precision operation
High precision operation
2022-07-06 17:59:00 【Stellaris_ L】
List of articles
High precision addition
analysis
The main ways to realize high-precision addition are 2 spot :① How to save the number ② How to calculate logarithm
One 、 How to save a large integer ?
answer : Exists in the array , And from a bit ( Low position ) Start saving . For example, a number 123456789.
Location | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
Number of deposits | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
(1) Why reverse order ?
answer : Every time you calculate , May encounter carry problems . If a carry occurs during the calculation of the largest bit , And we use positive order storage , You need to move the array to make a space at the beginning , This will be very cumbersome . Therefore, it is very convenient to add the last carry by directly using reverse order storage .
And this is also in line with the direction of our manual calculation .( Manual calculation will be explained later )
(2) Why use dynamic arrays (vector)
answer : In dynamic arrays , have access to STL The self-contained function is very convenient to obtain the array length , No external summation storage , And random access to .
Two 、 How to calculate an array ?
answer : Simulate artificial addition , Add from the low order of two numbers , When the sum is less than 10 Time is directly expressed as the operation result of this bit , The sum is greater than or equal to 10 Will be greater than 10 As the result of the operation of this bit and move forward one bit .
Templates
vector<int> add(string a,string b){
vector<int>A,B;// Store the string in reverse order into the dynamic array .
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');// Transformation types
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int>C;
int t=0;// Carry sign , Initial carry 0
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size())t+=A[i];// The current bit exists , Join in t
if(i<B.size())t+=B[i];
C.push_back(t%10);// Add non carry numbers to the array .
t/=10;// When t Greater than 10 Time quotient 1, That is, carry .
}
if(t)C.push_back(1);// Determine whether the last carry
return C;
}
Example
791. High precision addition - AcWing Question bank
AC Answer key :
#include <iostream>
#include <vector>
using namespace std;
vector<int> add(string a,string b){
vector<int>A,B;// Store the string in reverse order into the dynamic array .
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');// Transformation types
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int>C;
int t=0;// Carry sign , Initial carry 0
for(int i=0;i<A.size()||i<B.size();i++){
if(i<A.size())t+=A[i];// The current bit exists , Join in t
if(i<B.size())t+=B[i];
C.push_back(t%10);// Add non carry numbers to the array .
t/=10;// When t Greater than 10 Time quotient 1, That is, carry .
}
if(t)C.push_back(1);// Determine whether the last carry
return C;
}
int main(){
string a,b;
cin>>a>>b;
auto sum=add(a,b);//auto You can automatically determine the type of return value , Can be lazy .
for(int i=sum.size()-1;i>=0;i--)cout<<sum[i];
return 0;
}
High precision subtraction
analysis
The storage methods of the four high-precision algorithms are the same .
A 3 A_3 A3 | A 2 A_2 A2 | A 1 A_1 A1 | A 0 A_0 A0 | |
---|---|---|---|---|
— | B 2 B_2 B2 | B 1 B_1 B1 | B 0 B_0 B0 |
A i − B i − t A_i-B_i-t Ai−Bi−t There are two situations ,
① A i − B i − t ≥ 0 A_i-B_i-t\ge0 Ai−Bi−t≥0 There is direct A i − B i − t A_i-B_i-t Ai−Bi−t.
② A i − B i − t < 0 A_i-B_i-t<0 Ai−Bi−t<0 Yes A i − B i + 10 − t A_i-B_i+10-t Ai−Bi+10−t, At the same time, record a debit .
At this time, you can find a problem , Only when guaranteed A ≥ B A\ge B A≥B When can we calculate in a correct order . So we also need to consider being A < B A<B A<B The situation of , This situation is also easy to deal with, just change it to − ( B − A ) -(B-A) −(B−A) That's all right. . Of course, there is another point here , Namely A A A and B B B Must be positive numbers , If there is a negative number, it still needs a judgment to transform .
- summary : Judge A A A and B B B The size of the relationship , A ≥ B A\ge B A≥B When A − B A-B A−B; A < B A<B A<B When − ( B − A ) -(B-A) −(B−A).
Finally, we need to remove the leading 0.
Templates
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])return A[i]>B[i];
return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
vector<int> C;
for(int i=0,t=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1&&C.back()==0)C.pop_back();// Remove the lead 0
return C;
}
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';
Example
792. High precision subtraction - AcWing Question bank
#include <iostream>
#include <vector>
using namespace std;
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])
return A[i]>B[i];
return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){
vector<int> C;
for(int i=0,t=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1&&C.back()==0)C.pop_back();// Remove the lead 0
return C;
}
int main(){
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int> C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
cout<<endl;
return 0;
}
High precision multiplication
analysis
The high-precision multiplication here is different from the previous high-speed addition and division , Not two high-precision phase operations . But a high precision and a low precision operation . The low accuracy here is less than m a x ( l o n g l o n g ) / 10 max(long\ long)/10 max(long long)/10 Of .
A 2 = 1 A_2=1 A2=1 | A 1 = 2 A_1=2 A1=2 | A 0 = 3 A_0=3 A0=3 | ||
---|---|---|---|---|
× × × | B = 12 B=12 B=12 | |||
carry | t 3 t_3 t3 | t 2 t_2 t2 | t 1 t_1 t1 | t 0 t_0 t0 |
value | C 3 C_3 C3 | C 2 C_2 C2 | C 1 C_1 C1 | C 0 C_0 C0 |
First step :
C 0 = ( A 0 ∗ B + t 0 ) % 10 = 6 C_0=(A_0*B+t_0)\%10=6 C0=(A0∗B+t0)%10=6
t 1 = ( A 0 ∗ B + t 0 ) / 10 = 0 t_1=(A_0*B+t_0)/10=0 t1=(A0∗B+t0)/10=0
The second step :
C 1 = ( A 1 ∗ B + t 1 ) % 10 = 7 C_1=(A_1*B+t_1)\%10=7 C1=(A1∗B+t1)%10=7
t 2 = ( A 1 ∗ B + t 1 ) / 10 = 2 t_2=(A_1*B+t_1)/10=2 t2=(A1∗B+t1)/10=2
The third step :
C 2 = ( A 2 ∗ B + t 2 ) % 10 = 4 C_2=(A_2*B+t_2)\%10=4 C2=(A2∗B+t2)%10=4
t 3 = ( A 2 ∗ B + t 2 ) / 10 = 1 t_3=(A_2*B+t_2)/10=1 t3=(A2∗B+t2)/10=1
Step four :
C 3 = ( 0 ∗ B + t 3 ) % 10 = 1 C_3=(0*B+t_3)\%10=1 C3=(0∗B+t3)%10=1
- The final answer 123 ∗ 12 = 1476 123*12=1476 123∗12=1476
Templates
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for (int i=0;i<A.size()||t;i++){
if(i<A.size())t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();// Remove the lead 0
return C;
}
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
Example
793. High precision multiplication - AcWing Question bank
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for (int i=0;i<A.size()||t;i++){
if(i<A.size())t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)C.pop_back();// Remove the lead 0
return C;
}
int main(){
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
auto C=mul(A,b);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
High precision division
analysis
Just like high-precision multiplication , High precision division is also a high precision and low precision operation . And the setting will not produce decimals , It exists in the form of remainder .
Templates
vector<int> div(vector<int> &A,int b,int &r){
//r Is reference passing
vector<int> C;// merchant
r=0;
for (int i=A.size()-1;i>=0;i--){
// Start at the top
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
Example
794. High precision division - AcWing Question bank
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A,int b,int &r){
//r Is reference passing
vector<int> C;// merchant
r=0;
for (int i=A.size()-1;i>=0;i--){
// Start at the top
r=r*10+A[i];
C.push_back(r/b);
r%=b;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
int main(){
string a;
vector<int> A;
int B;
cin>>a>>B;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
int r;
auto C=div(A,B,r);
for(int i=C.size()-1;i>=0;i--)cout<<C[i];
cout<<endl<<r<<endl;
return 0;
}
边栏推荐
- Jerry's setting currently uses the dial. Switch the dial through this function [chapter]
- J'aimerais dire quelques mots de plus sur ce problème de communication...
- Debug and run the first xv6 program
- Jerry's watch reads the file through the file name [chapter]
- Pytorch extract middle layer features?
- 编译原理——预测表C语言实现
- 带你穿越古罗马,元宇宙巴士来啦 #Invisible Cities
- 1700C - Helping the Nature
- OpenEuler 会长久吗
- MSF横向之MSF端口转发+路由表+SOCKS5+proxychains
猜你喜欢
10 advanced concepts that must be understood in learning SQL
C语言通过指针交换两个数
Basic configuration and use of spark
Why should Li Shufu personally take charge of building mobile phones?
Pyspark operator processing spatial data full parsing (5): how to use spatial operation interface in pyspark
It doesn't make sense without a distributed gateway
Unity particle special effects series - treasure chest of shining stars
FlutterWeb浏览器刷新后无法回退的解决方案
SAP UI5 框架的 manifest.json
Spark accumulator and broadcast variables and beginners of sparksql
随机推荐
8位MCU跑RTOS有没有意义?
EasyCVR电子地图中设备播放器loading样式的居中对齐优化
李書福為何要親自掛帥造手機?
C语言通过指针交换两个数
Easy introduction to SQL (1): addition, deletion, modification and simple query
EasyCVR授权到期页面无法登录,该如何解决?
The art of Engineering (1): try to package things that do not need to be exposed
Summary of study notes for 2022 soft exam information security engineer preparation
Kernel link script parsing
C # nanoframework lighting and key esp32
李书福为何要亲自挂帅造手机?
QT中Model-View-Delegate委托代理机制用法介绍
TCP packet sticking problem
EasyCVR接入设备开启音频后,视频无法正常播放是什么原因?
[getting started with MySQL] fourth, explore operators in MySQL with Kiko
The shell generates JSON arrays and inserts them into the database
Smart street lamp based on stm32+ Huawei cloud IOT design
在一台服务器上部署多个EasyCVR出现报错“Press any to exit”,如何解决?
J'aimerais dire quelques mots de plus sur ce problème de communication...
How to output special symbols in shell