python 实现
# 大整数操作
class BigInt:
def add(self, a, b):
i, j = len(a) - 1, len(b) - 1
carry = 0
res = []
while i >= 0 or j >= 0 or carry > 0:
if i >= 0:
carry += int(a[i])
i -= 1
if j >= 0:
carry += int(b[j])
j -= 1
res.append(str(carry % 10))
carry = carry // 10
res = "".join(res[::-1])
return res
def multiply(self, a, b):
if a == "0" or b == "0":
return "0"
a = list(a[::-1])
b = list(b[::-1])
r = ['0'] * (len(a) + len(b) + 1)
for i in range(len(a)):
up = 0
for j in range(len(b)):
t = (int(a[i]) - int('0')) * (int(b[j]) - int('0')) + up + int(r[i + j]) - int('0')
up = t // 10
r[i + j] = chr(ord('0') + t % 10)
if up != 0:
r[i + j + 1] = chr(up + ord('0'))
res = ''.join(r)
for i in range(len(res) - 1, -1, -1):
if res[i] != '0':
res = res[:i + 1]
break
return res[::-1]
def sub(self, a, b):
# print("sub ", a,b)
if a == b:
return "0"
isf = False # a，b互换
if len(a) < len(b) or (len(a) == len(b) and a < b):
a, b = b, a
isf = True
a = a[::-1]
b = b[::-1]
r1 = list(map(int, a))
r2 = list(map(int, b))
for i in range(len(r2)):
if r1[i] >= r2[i]:
r1[i] = r1[i] - r2[i]
else:
r1[i + 1] = r1[i + 1] - 1
r1[i] = r1[i] - r2[i] + 10
r1 = list(map(str, r1))
res = ''.join(r1[::-1])
for i in range(len(res)):
if res[i] != '0':
res = res[i:]
break
if isf:
res = "-" + res
return res
def divide(self, a, b):
res = ""
if (len(a) == len(b) and a < b) or len(a) < len(b):
return "0"
dis = len(a) - len(b)
len2 = len(b)
b += "0" * dis
while dis >= 0:
sum = 0
while len(b) < len(a) or (len(a) == len(b) and a >= b):
sum += 1
a = self.sub(a, b)
res += str(sum)
dis -= 1
b = b[:len2 + dis]
# a is the remainder
# print(" 余数: " + a)
for i in range(len(res)):
if res[i] != '0':
res = res[i:]
break
return res
内部用一个int 数组，每个元素保存DLEN位数字
普通大整数思路
加法
只能是正数，模仿手算加法，用额外一个int保存每个位置相加结果并加到进位上
class Solution {
public:
string addStrings(string num1, string num2) {
int i = num1.size() - 1;
int j = num2.size() - 1;
int carry = 0;
string res = "";
while(i>=0 || j>=0 || carry){
long sum = 0;
if(i >= 0){sum += (num1[i] - '0');i--;}
if(j >= 0){sum += (num2[j] - '0');j--;}
sum += carry;
carry = sum / 10;
sum = sum % 10;
res = res + to_string(sum);
}
reverse(res.begin(), res.end());
return res;
}
};
减法
同样是模拟手算，处理借位。用大的减去小的，最后再判断是否需要添加负号。
关键部分
for(int i=0;i<s2.length();i++)
{
if(s[i]>=s2[i])
s[i]=s[i]-'0'-(s2[i]-'0')+'0';
else{
s[i+1]=s[i+1]-'0'-1+'0';
s[i]=s[i]-'0'+10-(s2[i]-'0')+'0';
}
}
乘法
还是模拟手算，第一个字符串的第i位乘以第二个字符串的第j位一定是结果的第i+j位，如果i+j已经有值，直接加上去就OK，别忘了处理进位。
这样的算法的复杂度是O（n2）.利用FFT可以将算法优化到O（nlogn），关于FFT的实现在此不再赘述，可以参考算法导论或者 http://www.cnblogs.com/lsx54321/archive/2012/07/20/2601632.html。
关键部分
for(int i=0;i<s1.length();i++)
for(int j=0;j<s2.length();j++)
{
int temp=(s1[i]-'0')*(s2[j]-'0');
s[i+j+1]=s[i+j+1]-'0'+(s[i+j]-'0'+temp)/10+'0';
s[i+j]=(s[i+j]-'0'+temp)%10+'0';
}
除法
我们将除法看作是减法来处理，用被减数不断的减去减数，记录减的次数即是商的值。但是我们当然不能一个一个减，因为如果有10000000/1这种情况不是要减到猴年马月。
我们可以记录被减数和减数的位数之差len，将减数扩大10的len倍。然后依次去减，一旦被减数小于减数时，将减数减小10倍，直至到原值。依次循环，去掉前置0，得出结果。
Java实现
import javax.print.DocFlavor;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Main {
/**
* 大整数减法
* 注意大减小的肯定长度够所以不需要加
* @param a
* @param b
* @return
*/
static String sub(String a,String b){
if(a.compareTo(b)==0){
return "0";
}
boolean isf=false;
if(a.length()<b.length()||a.length()==b.length()&&a.compareTo(b)<0){
String t=b;
b=a;
a=t;
isf=true;
}
// System.out.println("a ,b: == "+a+" "+b);
a=new StringBuilder(a).reverse().toString();
b=new StringBuilder(b).reverse().toString();
char[] r1=a.toCharArray();
char[] r2=b.toCharArray();
for(int i=0;i<r2.length;i++){
char t1=r1[i];
char t2=r2[i];
if(t1>=t2){
r1[i]=(char)(t1-t2+'0');
}else{
r1[i+1]--;
r1[i]=(char)(t1-t2+'0'+10);
}
}
String res=new StringBuilder(new String(r1)).reverse().toString();
for(int i=0;i<res.length();i++){
if(res.charAt(i)!='0'){
res=res.substring(i,res.length());
break;
}
}
if (isf){
res="-"+res;
}
return res;
}
/**
* 大整数加法
* @param a
* @param b
* @return
*/
static String add(String a,String b){
String res="";
int i=a.length()-1;
int j=b.length()-1;
int carry=0;
while (i>=0||j>=0||carry>0){
if(i>=0){
carry+=a.charAt(i--)-'0';
}
if(j>=0){
carry+=b.charAt(j--)-'0';
}
res=String.valueOf(carry%10)+res;
carry=carry/10;
}
return res;
}
/**
* 大整数乘法
* @param a1
* @param b1
* @return
*/
static String multiply(String a1,String b1){
if(a1.equals("0")||b1.equals("0")){
return "0";
}
a1=new StringBuilder(a1).reverse().toString();
b1=new StringBuilder(b1).reverse().toString();
char[] a=a1.toCharArray();
char[] b=b1.toCharArray();
char[] r=new char[a.length+b.length+1];
Arrays.fill(r,'0');
int up=0;
for(int i=0;i<a.length;i++){
up=0;
int j;
for(j=0;j<b.length;j++){
int t=(a[i]-'0')*(b[j]-'0')+up+r[i+j]-'0';
up=t/10;
r[i+j]=(char)('0'+t%10);
}
if(up!=0){
r[i+j]+=up+'0';
}
}
String res=new String(r);
for(int i=res.length()-1;i>=0;i--){
if(res.charAt(i)!='0'){
res=res.substring(0,i+1);
break;
}
}
res=new StringBuilder(res).reverse().toString();
return res;
}
/**
* 大整数除法
* @param a
* @param b
* @return
*/
static String divide(String a,String b){
String res="";
if(cmp(a,b)<0){
return "0";
}
int dis=a.length()-b.length();
int len2=b.length();
for(int i=0;i<dis;i++){
b+="0";
}
while (dis>=0){
int sum=0;
String temp="";
while (cmp(a,b)>=0){
sum++;
a=sub(a,b);
}
res=res+String.valueOf(sum);
dis--;
b=b.substring(0,len2+dis);
}
// a为余数
System.out.println(" yu: "+a);
return res;
}
static int cmp(String a,String b){
if(a.length()==b.length()){
return a.compareTo(b);
}else{
return a.length()-b.length();
}
}
public static void main(String[] args) {
FileInputStream fin=null;
try {
fin=new FileInputStream("D:\\in.txt");
} catch (FileNotFoundException e) {
e.printStackTrace();
System.out.println("File not found");
}
System.setIn(fin);
Scanner in=new Scanner(new BufferedInputStream(System.in));
// int t=in.nextInt();
while (in.hasNext()){
String a=in.next();
String b=in.next();
// System.out.println(add(a,b));
System.out.println("Input: "+a+" - "+b);
System.out.println("Output: "+divide(a,b));
}
}
}