大数运算介绍
1.大数指的是超过计算机CPU寄存器表达的数，即超过计算机字长的数。大数基本运算主要指的是对大数进行数论运算，如加、减、乘、除。出于效率原因，一般的大数运算主要指对无符号类型的数进行数论计算。
2.目前主流RSA算法都建立在512位到1024位的大数运算之上。然而大多数的编译器只能支持到64位的整数运算，即运算中整数必须小于等于64位，即：0xFFFFFFFFFFFFFFFF，这远远达不到RSA的需要，于是需要建立专门的大数运算库来解决这一问题。
3.最简单的办法是将大数当作字符串处理，也就是将大数用10进制字符数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低，因为1024位的大数其10进制数字个数就有数百个，对于任何一种运算，都需要在两个有数百个元素的数组空间上做多重循环，还需要许多额外的空间存放计算的进位退位标志及中间结果。其优点是算法符合人们的日常习惯，易于理解。
4.另一种方法是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试。
5.许多高级语言都支持大数运算(例如Java提供的bigDecimal，python等等)
实验代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author zhangjin
* @ClassName task_one.java
* @Description
* @createTime 2021年11月13日 09:02:00
*/
public class task_one {
/**
*
* @param x
* @param y
* @return x>y返回正 x<y返回负 x==y返回0
*/
public static int compare(String x,String y)
{
if(x.length()>y.length()) return 1;
if(x.length()<y.length()) return -1;
for(int i=0;i<x.length();i++)
{
if(x.getBytes()[i]!=y.getBytes()[i])
{
return x.getBytes()[i]-y.getBytes()[i];
}
}
return 0;
}
public static String add(String x,String y,String jishu)
{
if(compare(x,y)<0) return add(y,x,jishu); // 保证x>y
Integer key = Integer.valueOf(jishu);//key为进制
int j=y.length();int i=x.length();
int jinwei=0;
StringBuilder benwei=new StringBuilder();
while(j>0)
{
int y1=Integer.valueOf(y.substring(j-1,j));//取y的一位
int x1=Integer.valueOf(x.substring(i-1,i));//取x的一位
benwei.append((jinwei+x1+y1)%key);//获取本位并拼接到字符串
jinwei=(x1+y1+jinwei)/key;//获取进位位
j--;i--;
}
while(i>0)//因为x>y 所以当遍历完y的所有位数后x尚未遍历完
{
int x1=Integer.valueOf(x.substring(i-1,i));//继续遍历x
benwei.append((x1+jinwei)%key);
jinwei=(x1+jinwei)/key;
i--;
}
if(jinwei!=0) benwei.append(jinwei);//最后一次进位
return benwei.reverse().toString();//将求和得到的字符串翻转
}
public static String sub(String x,String y,String jishu)
{
if(compare(x,y)<0) return sub(y,x,jishu);//确保x>y
Integer key=Integer.valueOf(jishu);
int jiewei=0;//借位
int i=x.length();
int j=y.length();
StringBuilder benwei=new StringBuilder();
while(j>0)
{
int y1=Integer.valueOf(y.substring(j-1,j));
int x1=Integer.valueOf(x.substring(i-1,i));
benwei.append((x1+key-y1-jiewei)%key);//获取本位
jiewei=(x1-jiewei-y1)>=0?0:1;//获取借位位
i--;j--;
}
while(i>0)//x的位数大于y的位数的情况
{
int x1=Integer.valueOf(x.substring(i-1,i));
benwei.append((x1+key-jiewei)%key);
jiewei=(x1-jiewei)>=0?0:1;
i--;
}
String res = benwei.reverse().toString().replaceFirst("^0*", "");//去除首位的0
if(res.equals("")) return "0";//若结果为"00000" 上面去除首位的0后为空字符串
else return res;
}
//y为个位数 将y的每一位与x相乘
public static String mul_one(String x,String y,String jishu){
int i=x.length();
int jinwei=0;
Integer key=Integer.valueOf(jishu);
StringBuilder benwei=new StringBuilder();
while(i>0)
{
Integer Y=Integer.valueOf(y);
int x1=Integer.valueOf(x.substring(i-1,i));
benwei.append((Y*x1+jinwei)%key);
jinwei=(Y*x1+jinwei)/key;
i--;
}
if(jinwei!=0) benwei.append(jinwei);
return benwei.reverse().toString();
}
public static String mul(String x,String y,String jishu)
{
if(compare(x,y)<0) return mul(y,x,jishu);//确保x>y
int length_y=y.length();
List<String> res=new ArrayList<String>();
int i=length_y;
while(i>0) {
String s = mul_one(x, y.substring(i - 1, i),jishu);//用y的每一位与x相乘 结果放入数组
res.add(s);
i--;
}
for(int j=0;j<length_y;j++)
{
String s=res.get(j);//当j=0时表示y的个位数与x相乘 当j=1时表示y的十位数与x相乘 在后续补0相当于移位扩大倍数
for(int m=0;m<j;m++)
{
s=s+"0";
}
res.set(j,s);
}//将数组中所有值相加
String ans="0";
while(length_y>0)
{
ans=add(ans,res.get(length_y-1),jishu);
length_y--;
}
return ans;
}
public static String div(String x,String y,String jishu)
{ if(compare(x,y)<0) return div(y,x,jishu);
String ans="0";
String Y=y;//保存除数
while(compare(x,y)>0)//x为每次剩余部分的值 当剩余部分大于y表示任需要除
{
int len=x.length()-y.length();//x比y多多少位
while(x.length()>y.length())
{
y=y+"0";//例如x=789 y=35 x比y多一位 在y后面补0直到y与x位数相同
}
if(compare(x,y)<0) {
y=y.substring(0,y.length()-1);//如果补0后位数相同但y大于x 则减去一个0
len=len-1;
}
StringBuilder temp=new StringBuilder();
for(int i=9;i>0;i--)//获取结果的最高位
{
String mul = mul(String.valueOf(i), y, jishu);
if(compare(mul,x)<=0){
temp.append(i);
for(int j=1;j<=len;j++)//前面补了多少零就表示需要添加多少0 x=789 y=35 补了一个0 最高位为2 再添上一个0 即一部分结果为20
{
temp.append("0");
}
ans=add(temp.toString(),ans,jishu);//20为一部分结果
x= sub(x, mul, jishu);//x=x减去已经取走的部分
y=Y;//y设为初始的y
break;
}
}
}
return ans+" "+x;
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
System.out.println("please input first number: ");
String x = scanner.next();
System.out.println("please input second number: ");
String y=scanner.next();
System.out.println("please input jishu");
String jishu = scanner.next();
System.out.println("the add result: "+add(x,y,jishu));
System.out.println("the sub result: "+sub(x,y,jishu));
System.out.println("the mul result: "+mul(x,y,jishu));
System.out.println("the div result: "+div(x,y,jishu));
}
}
2021-11-13 21:51:53 星期六: