`

大数/高精度加减乘除取模[收藏]

阅读更多
#include <iostream>
#include <string>
using namespace std;

inline int compare(string str1, string str2)
{
      if(str1.size() > str2.size()) //长度长的整数大于长度小的整数
            return 1;
      else if(str1.size() < str2.size())
            return -1;
      else
            return str1.compare(str2); //若长度相等,从头到尾按位比较,compare函数:相等返回0,大于返回1,小于返回-1
}
//高精度加法
string ADD_INT(string str1, string str2)
{
      string MINUS_INT(string str1, string str2);
      int sign = 1; //sign 为符号位
      string str;
      if(str1[0] == '-') {
           if(str2[0] == '-') {
                 sign = -1;
                 str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));
           }else {
                 str = MINUS_INT(str2, str1.erase(0, 1));
           }
      }else {
           if(str2[0] == '-')
                 str = MINUS_INT(str1, str2.erase(0, 1));
           else {
                 //把两个整数对齐,短整数前面加0补齐
                 string::size_type l1, l2;
                 int i;
                 l1 = str1.size(); l2 = str2.size();
                 if(l1 < l2) {
                       for(i = 1; i <= l2 - l1; i++)
                       str1 = "0" + str1;
                 }else {
                       for(i = 1; i <= l1 - l2; i++)
                       str2 = "0" + str2;
                 }
                 int int1 = 0, int2 = 0; //int2 记录进位
                 for(i = str1.size() - 1; i >= 0; i--) {
                       int1 = (int(str1[i]) - 48 + int(str2[i]) - 48 + int2) % 10;  //48 为 '0' 的ASCII 码
                       int2 = (int(str1[i]) - 48 + int(str2[i]) - 48 +int2) / 10;
                       str = char(int1 + 48) + str;
                 }
                 if(int2 != 0) str = char(int2 + 48) + str;
          }
     }
     //运算后处理符号位
     if((sign == -1) && (str[0] != '0'))
          str = "-" + str;
     return str;
}


//高精度减法
string MINUS_INT(string str1, string str2)
{
     string MULTIPLY_INT(string str1, string str2);
     int sign = 1; //sign 为符号位
     string str;
     if(str2[0] == '-')
            str = ADD_INT(str1, str2.erase(0, 1));
     else {
            int res = compare(str1, str2);
            if(res == 0) return "0";
            if(res < 0) {
                  sign = -1;
                  string temp = str1;
                  str1 = str2;
                  str2 = temp;
            }
            string::size_type tempint;
            tempint = str1.size() - str2.size();
            for(int i = str2.size() - 1; i >= 0; i--) {
                 if(str1[i + tempint] < str2[i]) {
                       str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1);
                       str = char(str1[i + tempint] - str2[i] + 58) + str;
                 }
                 else
                       str = char(str1[i + tempint] - str2[i] + 48) + str;
            }
           for(i = tempint - 1; i >= 0; i--)
                str = str1[i] + str;
     }
     //去除结果中多余的前导0
     str.erase(0, str.find_first_not_of('0'));
     if(str.empty()) str = "0";
     if((sign == -1) && (str[0] != '0'))
          str = "-" + str;
     return str;
}

//高精度乘法
string MULTIPLY_INT(string str1, string str2)
{
     int sign = 1; //sign 为符号位
     string str;
     if(str1[0] == '-') {
           sign *= -1;
           str1 = str1.erase(0, 1);
     }
     if(str2[0] == '-') {
           sign *= -1;
           str2 = str2.erase(0, 1);
     }
     int i, j;
     string::size_type l1, l2;
     l1 = str1.size(); l2 = str2.size();
     for(i = l2 - 1; i >= 0; i --) {  //实现手工乘法
           string tempstr;
           int int1 = 0, int2 = 0, int3 = int(str2[i]) - 48;
           if(int3 != 0) {
                  for(j = 1; j <= (int)(l2 - 1 - i); j++)
                        tempstr = "0" + tempstr;
                  for(j = l1 - 1; j >= 0; j--) {
                        int1 = (int3 * (int(str1[j]) - 48) + int2) % 10;
                        int2 = (int3 * (int(str1[j]) - 48) + int2) / 10;
                        tempstr = char(int1 + 48) + tempstr;
                  }
                  if(int2 != 0) tempstr = char(int2 + 48) + tempstr;
           }
           str = ADD_INT(str, tempstr);
     }
     //去除结果中的前导0
     str.erase(0, str.find_first_not_of('0'));
     if(str.empty()) str = "0";
     if((sign == -1) && (str[0] != '0'))
           str = "-" + str;
     return str;
}
//高精度除法
string DIVIDE_INT(string str1, string str2, int flag)
{
     //flag = 1时,返回商; flag = 0时,返回余数
     string quotient, residue; //定义商和余数
     int sign1 = 1, sign2 = 1;
     if(str2 == "0") {  //判断除数是否为0
           quotient = "ERROR!";
           residue = "ERROR!";
           if(flag == 1) return quotient;
           else return residue;
     }
     if(str1 == "0") { //判断被除数是否为0
           quotient = "0";
           residue = "0";
     }
     if(str1[0] == '-') {
           str1 = str1.erase(0, 1);
           sign1 *= -1;
           sign2 = -1;
     }
     if(str2[0] == '-') {
           str2 = str2.erase(0, 1);
           sign1 *= -1;
     }
     int res = compare(str1, str2);
     if(res < 0) {
           quotient = "0";
           residue = str1;
     }else if(res == 0) {
           quotient = "1";
           residue = "0";
     }else {
           string::size_type l1, l2;
           l1 = str1.size(); l2 = str2.size();
           string tempstr;
           tempstr.append(str1, 0, l2 - 1);
           //模拟手工除法
           for(int i = l2 - 1; i < l1; i++) {
                 tempstr = tempstr + str1[i];
                 for(char ch = '9'; ch >= '0'; ch --) { //试商
                       string str;
                       str = str + ch;
                       if(compare(MULTIPLY_INT(str2, str), tempstr) <= 0) {
                              quotient = quotient + ch;
                              tempstr = MINUS_INT(tempstr, MULTIPLY_INT(str2, str));
                              break;
                       }
                 }
           }
           residue = tempstr;
     }
     //去除结果中的前导0
     quotient.erase(0, quotient.find_first_not_of('0'));
     if(quotient.empty()) quotient = "0";
     if((sign1 == -1) && (quotient[0] != '0'))
     quotient = "-" + quotient;
     if((sign2 == -1) && (residue[0] != '0'))
     residue = "-" + residue;
     if(flag == 1) return quotient;
     else return residue;
}

//高精度除法,返回商
string DIV_INT(string str1, string str2)
{
      return DIVIDE_INT(str1, str2, 1);
}
//高精度除法,返回余数
string MOD_INT(string str1, string str2)
{
      return DIVIDE_INT(str1, str2, 0);
}
                  
int main()
{
      char ch;
      string s1, s2, res;
      while(cin >> ch) {
           cin >> s1 >> s2;
           switch(ch) {
                case '+':  res = ADD_INT(s1, s2); break;   //高精度加法
                case '-':  res = MINUS_INT(s1, s2); break; //高精度减法
                case '*':  res = MULTIPLY_INT(s1, s2); break; //高精度乘法
                case '/':  res = DIV_INT(s1, s2); break; //高精度除法, 返回商
                case 'm':  res = MOD_INT(s1, s2); break; //高精度除法, 返回余数
                default :  break;
           }
           cout << res << endl;
      }
      return(0);
}
分享到:
评论
1 楼 yaojingguo 2010-09-15  
Good code. I have written a refined implementation based on your post. http://yaojingguo.iteye.com/blog/764311

相关推荐

    高精度加减乘除算法.doc

    高精度加法算法是计算机科学中处理大整数或大数运算的一种技术,它涉及到的主要是如何处理超出标准数据类型(如整型、浮点型)表示范围的数字。在处理这种运算时,通常需要自定义数据结构和算法来存储和操作这些大数...

    大数高精度运算库

    MapM库由Arthur O'Dwyer开发,提供包括加减乘除、取模、指数、对数、平方根等在内的多种大数运算功能。它的设计目标是能够在各种操作系统环境下运行,包括老旧的DOS系统以及Windows系列(如XP、2000、NT和9x)。 在...

    C++高精度大数模板

    大数的加减乘除操作都是基于这种位数组进行的。简略版通常会提供基本的运算符重载,如`+`、`-`、`*`、`/`,并使用简单而直观的算法实现这些操作。例如,加法可能通过逐位相加并考虑进位来完成,乘法则可能使用...

    gnu mp 大数高精度运算库

    GNU MP 是一个强大的开源大数高精度运算库,它提供了在各种编程语言中进行大整数和浮点数计算的能力。这个库被广泛用于需要处理超过标准整型或浮点型所能表示数值范围的场景,比如加密算法、科学计算、金融分析以及...

    高精度计算接口库

    在使用高精度计算库时,开发者可以利用库提供的API(Application Programming Interface)来执行加减乘除、取模、幂运算、开方、求根等操作。这些API通常会设计得易于理解和使用,使得开发人员无需关心底层复杂的...

    大数运算库 c/c++

    这些库通常提供包括加减乘除、取模、比较、位操作等在内的各种大数运算功能,并且支持动态增长的大数表示。 1. **原理与数据结构**:大数运算库通常采用链表或者数组来存储大数的每一位,每一位可以是一个较小的...

    高精度计算器_高精度计算器_

    这样的设计使得计算器能够处理从简单加减乘除到更复杂的根号、指数、对数等运算,且不损失精度。 在VB中实现高精度计算,首先要理解VB的数据类型系统。VB的Integer和Long类型虽然可以表示较大的整数,但仍有其局限...

    GMP.zip_GMP_gmp大数库介绍_gmp大数文档_大数库

    它实现了无限制长度的整数类型`mpz_t`,允许进行加减乘除、取模、指数运算、位操作等基本数学运算。此外,GMP还提供了浮点数类型`mpf_t`,支持高精度的浮点数计算。这些类型能够处理比系统原生类型大得多的数值,且...

    高精度算法

    在执行加减乘除等基本运算时,高精度算法需要考虑到进位和借位的问题。例如,加法通常采用“学校教的”竖式加法方法,逐位相加并处理进位;乘法可以使用Karatsuba算法或更高效的FFT(快速傅里叶变换)方法;除法则...

    大数运算-RSA-c语言大数运算库

    TOMMATH提供了完整的API,支持大数的加减乘除、比较、取模、平方根等操作,以及一些高级函数,如素数测试和模逆运算。使用这样的库可以简化开发者在C语言环境中实现大数运算的复杂性。 “ltm-0.39.zip”是...

    mod(div).rar_DIV_MOD_大数计算 java

    这个类提供了一系列方法,用于执行包括加减乘除、取模在内的各种大数运算。例如,我们可以使用`BigInteger`的`divide`方法来进行除法运算,`mod`方法来进行取模运算。这两个方法允许我们处理任意大小的整数,不受...

    高精度运算模块2.1版.zip易语言程序源码资源下载

    1. 大整数运算:支持大整数的加减乘除、乘方、取模等基本运算,以及位操作,如左移、右移、按位与、按位或、按位异或等。 2. 高精度浮点数运算:提供高精度的浮点数计算,可以处理标准浮点数无法精确表示的数值,...

    C++高精度代码及代码解释

    例如,`BigInt`类可能会重载`+`、`-`、`*`、`/`等操作符,以便进行加减乘除。此外,可能还会重载比较操作符如`、`&gt;`、`==`等,用于大整数之间的比较。 1. **重载加法运算符**:这通常涉及到两个`BigInt`对象的逐位...

    大数处理问题(就是用字符串)

    本题目的核心就是通过字符串操作来解决大数的加减乘除和取模运算。 1. **大数表示**: 在给定的代码中,大数被定义为一个结构体`Num`,包含一个字符数组`num`用于存储大数的每一位,以及一个整型变量`len`表示大数...

    大数计算器

    除了基本的运算功能,大数计算器通常还包含其他高级特性,如大数的加减乘除、因数分解、模逆元查找等。这些功能在处理复杂的数学问题,如数论问题、图论问题,甚至是物理模拟中都有广泛应用。 在实际使用中,大数...

    JAVA_大数操作

    Java提供了一个名为`java.math.BigInteger`的类,用于执行任意精度的算术运算,包括加减乘除、取模以及复杂的数学运算。这个类允许我们在程序中处理任意大小的整数,无论是正数、负数还是零。 首先,让我们了解一下...

    java大数类[参考].pdf

    它支持所有的整数算术运算,包括加减乘除、取模、位操作等。在示例1中,展示了如何使用`BigInteger`计算组合数C(n, k)。这里,`BigInteger.valueOf()`方法用于将整数转换为`BigInteger`对象,然后通过`multiply()`和...

    BigNumVB.zip_BIGNUMVB.DLL_BigNumVB_bignum_vb 大数计算

    在BigNumVB库中,大数被表示为一个内部结构,可以通过API调用来创建、初始化、比较、加减乘除以及执行其他数学运算。例如,你可以使用`NewBigInt`函数创建一个新的大数对象,使用`Add`函数进行加法运算,`Subtract`...

    gmp大数库的中文文档与静态链接库

    3. **编写代码**:使用GMP提供的API进行大数运算,例如初始化大数、分配内存、进行加减乘除等操作。 4. **测试和优化**:编写测试用例验证算法的正确性,并根据性能需求考虑优化策略,比如选择更适合当前任务的算法...

    gmpy2-2.1.1.tar.gz

    1. **大整数操作**:支持大整数的加减乘除、幂运算、取模、位操作等,适用于处理超过Python内置`int`类型范围的数字。 2. **浮点数运算**:提供高精度浮点数计算,可以设置任意精度,确保计算结果的准确性。 3. **...

Global site tag (gtag.js) - Google Analytics