大数加减运算

NANCHANG UNIVERSITY

课 程 设 计 报 告

课程名称： 计算机技术综合课程设计 题 目： 大数的加减运算

学 院： 信息工程学院 系： 计算机科学与技术系 专 业：网 络 工 程 班 级： 1 3 1 班 学 号： 610321301？ 学生姓名：张

时 间：2016.8.29~2016.9.8

目录

摘 要 ............................................................ 1 引 言 ............................................................ 2 问 题 描 述 ....................................................... 2 第一章 分析与设计 ................................................. 2 第二章 各个模块的实现方法描述 ..................................... 3 1、显示与输入模块............................................ 3

2、大数加减运算模块.......................................... 3

2.1 无符号加法运算的实现——PLUS方法..................... 3 2.2 无符号减法运算的实现——MINUS方法.................... 4 2.3 有符号加减运算的实现——add方法和sub方法............ 6

第三章 运行结果效果图 ............................................. 8 第四章 实验总结 .................................................. 10 第五章 附录：程序源代码 .......................................... 11 1.输入与显示模块：UI类 ..................................... 11

2. 大数运算模块：GetResult类 ............................... 15 第六章 参考文献 .................................................. 21

摘要

在数学中，数值的大小是没有上限的，但是在计算机中，由于字长的限制，计算机所能表示的范围是有限的，当我们对比较小的数进行运算时，如：1234+5678，这样的数值并没有超出计算机的表示范围，所以可以运算。但是当我们在实际的应用中进行大量的数据处理时，会发现参与运算的数往往超过计算机的基本数据类型的表示范围，这就涉到大数运算。大数运算，顾名思义，就是很大的数值的数进行一系列的运算。本文采用一个在JAVA语言下实现大数运算的一个程序为例，讲解包括了大数的加法，减法的算法及代码。

关键字：大数、运算精度、大数加减

1

引言

大数运算，意味着参加的值和计算结果通常是以上百位数，上千位数以及更大长度之间的整数运算。大数运算在当代社会得到了广泛运用。大数运算不仅仅运用在密码学中，保护网络信息安全，还在物理学、天文学、化学等学科的科研活动中发挥重要作用。例如大家所熟知圆周率π的值，在一般的数值计算中用到圆周率的不须要多大的精度，但在天文学计算一些星球或是星系上的体积面积时便显的误差很大了，这时π值计算的精度应该达到几百万位甚至更高，才能缩小误差,这就涉及到大数运算。

问 题 描 述

本次课程设计的题目就是实现大数加减运算，要实现以下要求：

1、参与运算的2个大数从键盘输入； 2、输入的数据为十进制整数； 3、数的十进制位数不低于20位。

编码实现语言没有限制，所以我决定使用我比较熟悉的Java来实现。

第一章 分析与设计

要实现上述大数加减运算程序，需要两个模块：

1. 显示与输入模块，用来获取从键盘输入的两个大数，并显示计算结果。

2. 大数加减运算模块，根据用户输入的两个大数和选中的运算类型，进行 加减运算。

2

大数加减运算程序模显示与输入模块 图1：大数运算模块示意图

大 数 运 算 模 块 第二章 各个模块的实现方法描述

1、显示与输入模块

本模块由名为UI的类实现，UI类有以下几个方法（详细代码请查看附录）： （1）setWinStyle()方法，其作用是设置窗口显示风格为微软风格，美化图形界面的显示效果，移除Java默认的窗口风格。

（2）setMyFont()方法，设置输入输出的字体为指定字体。 （3）initGUI()方法，初始化图形界面。 （4）Listener()方法，添加事件监听器。

（5）UI()构造方法，调用以上方法完成UI类的初始化。 （6）getInput()方法，获取输入的大数。 （7）静态main方法，应用程序的入口。

其中，图形界面的布局主要采用GridLayout和BorderLayout。 2、大数加减运算模块

该模块是本程序的核心模块，被显示与输入模块调用，进而实现加减运算功能。本模块由名为GetResult的类实现，当UI类需要显示计算结果时，只需创建GetResult的实例，调用GetResult类的相关方法，并传递参与运算的两个大数对应的字符串即可（加法调用GetResult的add方法，减法调用sub方法）。

GetResult的核心是PLUS和MINUS方法，PLUS方法实现无符号大整数的加法，MINU方法实现无符号大整数的减法，add方法、sub方法基于PLUS与MINUS方法实现了有符号的大整数的加减。

2.1 无符号加法运算的实现——PLUS方法

加法计算还是比较容易的，我们也是先从低位算起，因为只须要对应的位相

3

加，再加上前一位的进位，再去判断是否本位是否有进位， 有则把本位数字改为减去它的权，也就是10，再置进位为1。如果没有进位，则给进位赋值0。

事实上，输入的两个大数均为字符串，对将第一个大数反转所得到的字符串命名为number1，第二个大数命名反转所得到的字符串为number2，对于第i位

int c=int (number1.[i] + number2.[i] - 96);

若c<10则表明该位相加没有进位，c>10则表明有进位。

若int carry=c/10，则对于加法运算结果反转所得字符串result的第i+1位满足(carry表示来自低位的进位)：

int temp=number1.[i+1] + number2.[i+1]+carry - 96; result[i+1]=temp;

图2： 加法运算示意图

在实际编码中，为了提高效率，先将number1.[i] + number2.[i] - 48的值以字符的形式存在字符串容器result的第i个位置中，这样两个数相差较大时可以减少循环次数，最后再统一进行处理。

2.2 无符号减法运算的实现——MINUS方法

减法稍微有一点复杂， 因为会处理负数，而我们所用的是字符串的形式来保存数字也是为这一点。否则用整型或其它类型时，则表示处理、保存时会相当复杂。算法也是从低位开始减。先要判断减数和被减数那一个大，减数位大于被减数是正常减；被减数大，则被减数减减数，最后还要加上负号；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断

4

是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。

下面是我实现比较数字字符串大小的方法： //返回1前者较大，返回0两者相等，返回-1后者较大

privateint COMPARE(String number1, String number2) { intj;

intlength1 = number1.length(); intlength2 = number2.length(); if (number1.length() == 0) number1 = \; if (number2.length() == 0)

number2 = \;

j = 0;

for (inti = 0; i

break; }

number1 = number1.substring(j); j = 0;

for (inti = 0; i

break; }

number2 = number2.substring(j); length1 = number1.length(); length2 = number2.length(); if (length1>length2) { return 1;

} elseif (length1 == length2) {

if (number1.compareTo(number2) > 0) { return 1; } elseif (number1.compareTo(number2) == 0) { return 0; } else {

return -1;

}

5

}

} else { }

return -1;

思路是如果两个数长度不一样那么长度长的整数大；如果长度一致，由于0-9这10个数字的ASCII是逐渐递增的逐一只要取出每一位的字符来比较即可。

这样就可以判断减数和被减数哪个大，对于减数位大于被减数是正常减；被减数大，则被减数减减数，最后还要追加结果前面负号。

判断借位与加法判断进位原理差不多，就不一一说明了。

图3：减法实现示意图

2.3 有符号加减运算的实现——add方法和sub方法

UI类调用传参前会去除输入的数字中带有的’+’、’,’、空格等符号。add方法对两个数进行判断，如果两个数字均负（以‘-’开头）,则转换为无符号大整数相加并在结果前面追加’-’；如果一正一负则转化为无符号大整数相减；如果均为正数，则进行无符号大整数相加。

sub方法思路同add方法。 代码如下：

// 带符号大整数加法

public String add(String num1, String num2) {

if (isNumeric(num1) && isNumeric(num2)) {

String result=null; charc1 = num1.charAt(0); charc2 = num2.charAt(0); if (c1 == '-') {

if (c2 == '-') {

result=\+this.PLUS(num1.substring(1),

num2.substring(1));

} else {

6

}

}

}

result=this.MINUS(num2, num1.substring(1));

} else {

if (c2 == '-') { }

result=this.MINUS(num1, num2.substring(1)); result=this.PLUS(num1, num2); } else {

returnresult;

return\您的输入格式不正确\; }

// 带符号大整数减法

public String sub(String num1, String num2) { }

if (isNumeric(num1) && isNumeric(num2)) { }

return\您的输入格式不正确\;

String result=null;

num1.replaceAll(\, \); num2.replaceAll(\, \); charc1 = num1.charAt(0); charc2 = num2.charAt(0); if (c1 == '-') { }

returnresult;

if (c2 == '-') { }

if (c2 == '-') { }

result=this.PLUS(num1, num2.substring(1)); result=this.MINUS(num1, num2); } else {

result=this.MINUS(num2.substring(1), num1); result=\+this.PLUS(num1.substring(1), } else {

num2.substring(1));

} else {

7

第三章运行结果效果图

1、程序初始界面

2、加法

图：加法示例1

8

图：加法示例2

3.减法

图：减法示例

9

第四章 实验总结

刚拿到课设的题目时，我对大数运算了解有限。为了保证代码的高效性，特地参考了《算法导论》。

回顾这次课设的过程，我感概颇多，在这段时间，需要经常从电脑上查询资料，查看书本了解一些函数的使用方法，当然，写代码的过程也充满了各种挫折，每每满心欢喜的运行已经写好的代码时，总会出现各种意料之外的bug，然后又去苦思解决方案，这样反反复复的修改，最终才形成了现在的代码，虽然这个代码还不是最完美的，但是却锻炼了我独立思考的能力，更重要的是我也学到了很多之前没有学过的东西，让我受益匪浅。这次做课设也让我明白了查阅资料的重要性，在信息化多元的今天，我们不可能掌握所有的知识，面对未知的事物，学会查阅书籍和上网搜集是必不可少的。

对于这些代码还是有很大的改进空间的：1.界面上的输入框并不友好，当用户输入3个数后不能自动追加空格，数字都没有空格隔开。2.对于结果不支持让用户选择精度的科学计数法。

10

第五章附录：程序源代码

1.输入与显示模块：UI类

package ncu;

import java.awt.BorderLayout; import java.awt.Font;

import java.awt.GridLayout;

import java.awt.event.ActionEvent; import java.awt.event.ActionListener; importjava.util.regex.Matcher; importjava.util.regex.Pattern; import javax.swing.JButton; import javax.swing.JFrame; import javax.swing.JLabel; import javax.swing.JPanel; import javax.swing.JScrollPane; import javax.swing.JTextArea; import javax.swing.SwingUtilities; import javax.swing.UIManager;

publicclassUIextends JFrame { private JTextArea firstNum; private JTextArea nextNum; private JTextArea result; private String resultStr; private JButton add; private JButton sub; private String num1; private String num2; public UI() { this.setWinStyle(); this.initGUI(); this.setMyFont(); this.Listener(); this.setSize(700, 400); this.setLocationRelativeTo(null); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

}

this.setTitle(\大数运算\); this.setVisible(true);

11

//设置字体

privatevoid setMyFont(){ Font font= new Font(\,Font.BOLD,22); this.firstNum.setFont(font); this.nextNum.setFont(font); this.result.setFont(font); }

//初始化页面

privatevoid initGUI() {

JPanel pn = new JPanel();

pn.setLayout(new GridLayout(2, 1, 0, 4)); JPanel first = new JPanel();

first.setLayout(new BorderLayout(4, 4));

first.add(new JLabel(\第一个数:\), BorderLayout.WEST); this.firstNum = new JTextArea(15, 4); firstNum.setLineWrap(true);

JScrollPane scrollNum1 = new JScrollPane(); scrollNum1.setViewportView(firstNum);

first.add(scrollNum1, BorderLayout.CENTER); JButton btn1 = new JButton(\清除\); first.add(btn1, BorderLayout.EAST); // this.add(first); pn.add(first);

JPanel next = new JPanel();

next.setLayout(new BorderLayout(4, 4));

next.add(new JLabel(\第二个数:\), BorderLayout.WEST); this.nextNum = new JTextArea(15, 4); nextNum.setLineWrap(true);

JScrollPane scrollNum2 = new JScrollPane(); scrollNum2.setViewportView(nextNum);

next.add(scrollNum2, BorderLayout.CENTER); JButton btn2 = new JButton(\清除\); next.add(btn2, BorderLayout.EAST); // this.add(next); pn.add(next);

JPanel panel = new JPanel();

panel.setLayout(new BorderLayout());

this.add = new JButton(\加法\);

12

this.sub = new JButton(\减法\); JPanel type = new JPanel();

type.setLayout(new BorderLayout(4, 4));

type.add(new JLabel(\运算类型:\), BorderLayout.WEST); JPanel kind = new JPanel();

type.add(kind, BorderLayout.CENTER); kind.setLayout(new GridLayout(1, 2)); kind.add(this.add); kind.add(this.sub);

panel.add(type, BorderLayout.NORTH); // this.add(type);

this.result = new JTextArea();

JScrollPane scroll = new JScrollPane(); this.result.setEditable(false); this.result.setLineWrap(true);

this.result.setWrapStyleWord(true); scroll.setViewportView(result);

scroll.setColumnHeaderView(new JLabel(\运算结果:\)); panel.add(scroll, BorderLayout.CENTER); // this.add(scroll);

this.setLayout(new GridLayout(2, 1, 0, 4)); this.add(pn); this.add(panel);

//清除输入1

btn1.addActionListener(new ActionListener() {

@Override publicvoid actionPerformed(ActionEvent e) { firstNum.setText(null); } }); //清除输入2 btn2.addActionListener(new ActionListener() { @Override publicvoid actionPerformed(ActionEvent e) { nextNum.setText(null); } }); } //初始化监听器 privatevoid Listener() { this.add.addActionListener(new ActionListener() {

13

@Override

publicvoid actionPerformed(ActionEvent e) { result.setText(null); GetResult gr=new GetResult(); }

getInput();//获取输入

longstartTime=System.nanoTime(); //获取大数计算开始时间 resultStr=gr.add(num1, num2);

longendTime=System.nanoTime(); //获取结束时间

System.out.println(\程序运行时间： \+(startTime-endTime)+\); if (!resultStr.isEmpty()) { inta=0; if(resultStr.charAt(0)=='-') a=1; if(!resultStr.equals(\您的输入格式不正确\)){ intn=resultStr.length()-a; result.setText(\和是\+n+\位整数:\\n \); } result.append(resultStr); } else { result.setText(\未知的错误！\); }

});

this.sub.addActionListener(new ActionListener() { @Override publicvoid actionPerformed(ActionEvent e) { result.setText(null); GetResult gr=new GetResult(); getInput();//获取输入 longstartTime=System.nanoTime(); //获取大数计算开始时间 resultStr=gr.sub(num1, num2);

longendTime=System.nanoTime(); //获取结束时间

System.out.println(\程序运行时间： \+(startTime-endTime)+\); if (!resultStr.isEmpty()) { inta=0; if(resultStr.charAt(0)=='-') a=1; if(!resultStr.equals(\您的输入格式不正确\)){ intn=resultStr.length()-a; result.setText(\差是\+n+\位整数:\\n \); } result.append(resultStr); } else {

14

}

}

}

result.setText(\未知的错误！\);

}); }

//获取输入

privatevoid getInput() { this.num1 = firstNum.getText().replaceAll(\, \); this.num2 = nextNum.getText().replaceAll(\, \); }

// 设置界面显示风格为微软窗口风格 privatevoid setWinStyle() { }

try { String lookAndFeel = UIManager.getSystemLookAndFeelClassName(); UIManager.setLookAndFeel(lookAndFeel); SwingUtilities.updateComponentTreeUI(this); } catch (Exception e) { e.printStackTrace(); }

publicstaticvoid main(String[] args) { UI h = new UI(); h.setTitle(\大数运算 -ncu.edu\); }

2.大数运算模块：GetResult类

package ncu;

import java.util.regex.Matcher; import java.util.regex.Pattern; public class GetResult { // 比较数的大小，减法需要用到

//返回1前者较大，返回0两者相等，-1后者较大 private int COMPARE(String number1, String number2) { int j;

15

}

int length1 = number1.length(); int length2 = number2.length(); if (number1.length() == 0) number1 = \

if (number2.length() == 0) number2 = \j = 0;

for (int i = 0; i < length1; ++i) { if (number1.charAt(i) == '0') ++j; else break; }

number1 = number1.substring(j); j = 0;

for (int i = 0; i < length2; ++i) { if (number2.charAt(i) == '0') ++j; else break; }

number2 = number2.substring(j); length1 = number1.length(); length2 = number2.length();

if (length1 > length2) { return 1;

} else if (length1 == length2) { if (number1.compareTo(number2) > 0) { return 1; } else if (number1.compareTo(number2) == 0) { return 0; } else { return -1; } } else { return -1; }

// 无符号大整数加法

16

public String PLUS(String number1, String number2) { int i; int length1 = number1.length(); int length2 = number2.length(); }

StringBuilder result = new StringBuilder();

number1 = new StringBuilder(number1).reverse().toString(); number2 = new StringBuilder(number2).reverse().toString(); for (i = 0; i < length1 && i < length2; i++) { char c = (char) (number1.charAt(i) + number2.charAt(i) - 48); result.append(c); }

while (i < length1) { result.append(number1.charAt(i)); ++i; }

while (i < length2) { result.append(number2.charAt(i)); ++i; }

int carry = 0;

int n = result.length(); for (i = 0; i < n; ++i) { int value = result.charAt(i) - 48 + carry; result.setCharAt(i, (char) (value % 10 + 48)); carry = value / 10; }

if (carry != 0) { result.append((char) (carry + 48)); }

String resultStr = result.reverse().toString(); if (resultStr.length() == 0) return \return resultStr;

17

// 无符号大整数减法

public String MINUS(String number1, String number2) { int i; int length1 = number1.length(); int length2 = number2.length(); StringBuilder result = new StringBuilder();

if (this.COMPARE(number2, number1) > 0) { return \}

number1 = new StringBuilder(number1).reverse().toString(); number2 = new StringBuilder(number2).reverse().toString(); for (i = 0; i < length1 && i < length2; i++) { char c = (char) (number1.charAt(i) - number2.charAt(i) + 48); result.append(c); }

if (i < length1) { for (; i < length1; i++) { result.append(number1.charAt(i)); } }

int carry = 0;

int n = result.length(); for (i = 0; i < n; i++) { int value = result.charAt(i) - 48 + carry; if (value < 0) { value = value + 10; carry = -1; } else { carry = 0; } result.setCharAt(i, (char) (value + 48)); }

for (i = n - 1; i >= 0; i--) { if (result.charAt(i) != '0') break; }

String resultStr = result.reverse().substring(n - i - 1, n); if (resultStr.length() == 0)

18

}

return \return resultStr;

// 带符号大整数加法

public String add(String num1, String num2) { if (isNumeric(num1) && isNumeric(num2)) { String result=null; char c1 = num1.charAt(0); char c2 = num2.charAt(0); if (c1 == '-') { if (c2 == '-') { result=\ } else { result=this.MINUS(num2, num1.substring(1)); } } else { if (c2 == '-') { result=this.MINUS(num1, num2.substring(1)); } else { result=this.PLUS(num1, num2); } }

} return result; }

return \您的输入格式不正确\

// 带符号大整数减法

public String sub(String num1, String num2) { if (isNumeric(num1) && isNumeric(num2)) { String result=null; num1.replaceAll(\ num2.replaceAll(\ char c1 = num1.charAt(0); char c2 = num2.charAt(0); if (c1 == '-') { if (c2 == '-') { result=this.MINUS(num2.substring(1), num1); } else { result=\ } } else {

19

}

}

}

if (c2 == '-') { result=this.PLUS(num1, num2.substring(1)); } else { result=this.MINUS(num1, num2); } }

return result;

return \您的输入格式不正确\

// 判断是否是数字字符串

public boolean isNumeric(String str) { if (str.isEmpty()) return false; Pattern pattern = Pattern.compile(\ Matcher isNum = pattern.matcher(str); if (isNum.matches()) { return true; } return false; }

20

第六章 参考文献

[1]、《算法导论（原书第3版）》（美）Thomas H.Cormen, Charles E.Lesserson,Ronald L.Rivest ,Clifford Stein编著；殷建平、徐云、王刚、刘晓光、苏明、邹恒明、王宏志 译； 电子工业出版社；2013.1

[2]、《Java语言程序设计（基础篇）》 （美） Y.Daniel Liang 编著；李娜 译 电子工业出版社；2015.1

21

本文来源：https://www.bwwdw.com/article/74p3.html