[大整数乘法] java代码实现

[大整数乘法] java代码实现

上一篇写的“[大整数乘法]分治算法的时间复杂度研究”,这一篇是基于上一篇思想的代码实现,以下是该文章的连接:

http://www.cnblogs.com/McQueen1987/p/3348426.html

代码主要实现大整数乘法,过程中也涉及到[大整数加法] 和 [大整数减法] 的计算,代码如下:

 

类1

————————————————————————————————————————————————————————————

package bigIntNum;

public class NumDividEqual { public char[] A; public char[] B; int n; /** * 将数组均分为两份,分别存入数组A和数组B中; * @param input */ public NumDividEqual(char[] input){ n = input.length/2; A = new char[n]; B = new char[n]; for(int i = 0; i<n;i++){ A[i] = input[i]; } for(int i = 0; i<n;i++){ B[i] = input[i + n]; } } public static void main(String[] args) { // TODO Auto-generated method stub } }

  

类2

————————————————————————————————————————————————————————————

package bigIntNum;

import java.util.Arrays;

public class bigIntMult {
    /**
     * 将字符数组倒序排列
     * @param input
     * @return
     */
    public char[] reverse(char[] input) {
        char[] output = new char[input.length];
        for (int i = 0; i < input.length; i++) {
            output[i] = input[input.length - 1 - i];
        }
        return output;
    }
    
    /**
     * 将大整数平均分成两部分
     * @param input
     * @return
     */
    public NumDividEqual partition(char[] input) {
        return new NumDividEqual(input);
    }

    /**
     * 求两数组中较大数组的长度,如果其长度为奇数则+1变偶
     * @param num1
     * @param num2
     * @return
     */
    public int calLength(char[] num1, char[] num2) {
        int len = num1.length > num2.length ? num1.length : num2.length;
        if (len == 1)
            return 1;
        len += len & 1;
        return len;
    }

    /**
     * 除去数字前面多余的0
     * @param input
     * @return
     */
    public static char[] trimPrefix(char[] input) {
        char[] ret = null;
        for (int i = 0; i < input.length; i++) {
            if (ret == null && input[i] == '0')
                continue;
            else {
                if (ret == null) {
                    ret = new char[input.length - i];//出去数字前面多余的0
                }
                ret[i - (input.length - ret.length)] = input[i];
            }
        }
        if (ret == null)
            return new char[] { '0' };
        return ret;
    }
    
    /**
     * 数组如果长度不足n,则在数组前面补0,使长度为n。
     * @param input 输入数组要求数字的最高位存放在数组下标最小位置
     * @param n 
     * @return
     */
    public static char[] format(char[] input, int n) {
   //
        if (input.length >= n) {
            return input;
        }
        char[] ret = new char[n];
        for (int i = 0; i < n - input.length; i++) {
            ret[i] = '0';
        }
        for (int i = 0; i < input.length; i++) {
            ret[n - input.length + i] = input[i];
        }
        return ret;
    }

    /**
     * 大整数尾部补0。相当于移位,扩大倍数
     * @param input
     * @param n
     * @return
     */
    public char[] addTail(char[] input, int n) {
   //
        char[] ret = new char[input.length + n];
        for (int i = 0; i < input.length; i++) {
            ret[i] = input[i];
        }
        for (int i = input.length; i < ret.length; i++) {
            ret[i] = '0';
        }
        return ret;
    }
    
    /**
     * 大整数加法
     * @param num1
     * @param num2
     * @return
     */
    public char[] add(char[] num1, char[] num2) {
        int len = num2.length > num1.length ? num2.length : num1.length;
        int carry = 0;//进位标识
        num1 = format(num1, len);
        num2 = format(num2, len);
        char[] ret = new char[len + 1];

        for (int i = len - 1; i >= 0; i--) {
            int tmp = num1[i] + num2[i] - 96;
            tmp += carry;
            if (tmp >= 10) {
                carry = 1;
                tmp = tmp - 10;
            } else {
                carry = 0;
            }
            ret[len - i - 1] = (char) (tmp + 48);
        }
        ret[len] = (char) (carry + 48);//最后一次,最高位的进位
        return trimPrefix(reverse(ret));
    }
    /**
     * 大整数减法:
     * @param num1 被减数,大整数乘法中只有一个减法(A+B)(C+D)-(AC+BD)=AC+BC>0,因此參數num1>num2且都为正
     * @param num2 减数
     * @return
     */
    public static char[] sub(char[] num1, char[] num2) {
        int lenMax = num1.length > num2.length ? num1.length : num2.length;
        char[] newNum1 = Arrays.copyOf(format(num1, lenMax), lenMax);//字符串前面补0,使两串长度相同
        char[] newNum2 = Arrays.copyOf(format(num2, lenMax), lenMax);
        
        for(int i=0;i<lenMax;i++){
   //when num1-num2<0 return
            if((newNum1[i]=='0' && newNum1[i]=='0') || newNum1[i] == newNum2[i]){
   //newNum1 is bigger;  
                continue;
            }
            else if(newNum1[i] < newNum2[i]){
   //不滿足參數num1>num2;
                    System.out.println("The Parameter in sub(A,B).A MUST Bigger Than B!");
                    System.exit(0);
                 }
            else break;
        }

        for(int i=lenMax-1;i>=0;i--){
            if(newNum1[i] < newNum2[i]){
   //result < 0
             newNum1[i] = (char) (newNum1[i] + '0' + 10 - newNum2[i]);
             newNum1[i-1] = (char) (newNum1[i-1] - 1);
            }
            else{
                newNum1[i] = (char) (newNum1[i] + '0' - newNum2[i]);
            }
        }
        return trimPrefix(newNum1);
    }      
    /**
     * 大整数乘法
     * @param num1
     * @param num2
     * @return
     */
    public char[] mult(char[] num1, char[] num2) {
        char[] A, B, C, D, AC, BD, AjB, CjD, ACjBD, AjBcCjD,  SUM;
        int N = calLength(num1, num2);//求两数组中较大数组的长度,如果长度为奇数则+1变偶,方便二分成两部分
        num1 = format(num1, N);//数组高位存整数的高位数;数字前面补0,使长度为n;
        num2 = format(num2, N);
        if (num1.length > 1) {
            NumDividEqual nu1 = partition(num1);//将大整数平均分成两部分
            NumDividEqual nu2 = partition(num2);
            A = nu1.A;
            B = nu1.B;
            C = nu2.A;
            D = nu2.B; 
            AC = mult(A, C);//分治求大整数乘法
            BD = mult(B, D);
            AjB = add(A,B);
            CjD = add(C,D);
            ACjBD = add(AC,BD);
            AjBcCjD = mult(AjB, CjD);
            
            char[] tmp1 = addTail(sub(AjBcCjD, ACjBD), N / 2);//尾部补0,相当于移位
            char[] tmp2 = add(addTail(AC, N), BD);
            SUM = add(tmp1, tmp2);
            char[] test = trimPrefix(SUM);//除去结果前面多余的0
            return test;
        } else {
            Integer ret = (num1[0] - 48) * (num2[0] - 48);
            return ret.toString().toCharArray();
        }
    }

    public static void main(String[] args) {
        String st1 = "168746315641347979798";
        String st2 = "164681654767446887797451316158";
        char[] a = st1.toCharArray();
        char[] b = st2.toCharArray();
        bigIntMult bg = new bigIntMult();
        char[] ret = bg.mult(a, b);
        System.out.println(ret);
    }
}

 

[大整数乘法] java代码实现

 

代码优化:

1.可以写个hash表,存储一些常见的乘法,从而避免每次都重复计算。比如9999×9999999,里面有重复的9×9计算,可以考虑hash表存储这些计算的结果,用到时直接查询结果,从而避免重复计算。

 

声明:代码是本人脑力劳动结果,请尊重他人劳动。转载注明出处!

 

 

转载于:https://www.cnblogs.com/McQueen1987/p/3401979.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/109981.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 开心网买房子外挂_开心躲猫猫穿墙版下载

    开心网买房子外挂_开心躲猫猫穿墙版下载     开心网的买房子组件出了很久了,竟然到现在还没有出一个买房外挂。上星期某一晚上基于turbozv.com提供的抢车位的源代码,改写了一个买房子的外挂,此外挂不具有抢人住自己家的功能,那个不赚钱。来钱最快的是每隔一小时换一个地方住,随机得0到6000之前的住房津贴。经过一个星期的尝试,平均每天入帐5万,嘿嘿。发给大家一起来挂吧,祝大家早日住上大别墅。…

    2022年9月12日
    0
  • 素数推断算法(高效率)

    素数推断算法(高效率)

    2021年12月16日
    43
  • latex教程详细笔记「建议收藏」

    latex教程详细笔记「建议收藏」本文是笔者初学WinEdt用以编辑Latex的笔记,只涉及一些简单问题,详细请参考百度文库(点点这几个字看看~~)本文的主要参考文献是ta1.字体大小options—optionsinterface—Fontschemes—Font双击从右边找到FONT_SIZE将10改为自己想要的,如14—-保存—右键单击左边之前的Font—-LoadScript—结束2.分段机制在原…

    2022年5月31日
    42
  • 联想g510键盘如何拆装视频_联想g5080键盘怎么拆

    联想g510键盘如何拆装视频_联想g5080键盘怎么拆导致笔记本键盘失灵的原因有很多种,有时候是因为电脑系统的原因,但是大部分还是因为键盘本身的问题,如果是键盘本身的问题导致的笔记本键盘失灵,那么最多的解决方法就是拆卸该笔记本的键盘,然后分析问题的所在。下面小编就为大家介绍一下的方法吧,欢迎大家参考和学习。首先观察一下键盘正面,键盘靠一个弧形的卡口卡在掌托上的。如图:键盘左手面在桌上找一块大空地,周围不要放水或者…当键盘坏了,这时就需要更换了,笔…

    2022年9月16日
    0
  • origin怎么做多组柱状图_origin怎么对比两组数据

    origin怎么做多组柱状图_origin怎么对比两组数据1.数据点的横坐标不是等间距时的曲线绘制用实验数据作图时,会遇到数据点的横坐标不是等间距的情况,比如:X:1,3,4,8,9,12,…Y:10.2,10.5,11.4,11.8,10.9,10.2,…如果只有一组实验数据,则按照普通的方法在Worksheet中分别输入X,Y的值,然后用“线+符号”的方式绘图即可。但是,当有多组此种情况的数据需要绘制在一个图中时,例如:X1:1,3,4,8…

    2022年9月30日
    0
  • 利用WSUS搭建补丁升级服务器「建议收藏」

     前言随着Windows操作系统的复杂化和尺寸不断扩大,软件的漏洞也越来越多,这些漏洞使得病毒攻击和恶意入侵造成的安全事故也越来越频繁,为了解决软件漏洞尤其是安全漏洞造成的危害,软件开发商在发现漏洞后会及时公布相应的补丁程序。安装软件补丁是安全和解决小范围软件错误的有效途径。软件补丁是指一种插入程序能对运行的软件错误进行修改的软件编码。由于补丁管理具有及时性和持续性,对局域网范围内的所有计

    2022年4月12日
    639

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号