大数运算介绍

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 星期六: