高精度运算c语言.ppt

高精度运算 内蒙古师范大学计算机与信息工程学院孟繁军 运算的前提条件 类型范围 确定各类型的取值范围int 2 147 483 648 2 147 483 647unsignedint 0to4 294 967 295longint 2 147 483 648to2 147 483 647longlong 9 223 372 036 854 775 808to9 223 372 036 854 775 807float 3 4E 38 7digits double 1 7E 308 15digits longdouble 1 2E 4932 19digits 高精度运算的基本方法 1 加数 减数 运算结果的输入和存储运算因子超出了整型 实型能表示的范围 肯定不能直接用一个数的形式来表示 在运算过程中 能表示多个数的数据类型有两种 数组和字符串 1 数组 每个数组元素存储1位 在优化时 这里是一个重点 有多少位就需要多少个数组元素 用数组表示数的优点 每一位都是数的形式 可以直接加减 运算时非常方便用数组表示数的缺点 数组不能直接输入 输入时每两位数之间必须有分隔符 不符合数值的输入习惯 2 字符串 字符串的最大长度是多少 可以表示多少位数字 用字符串表示数的优点 能直接输入输出 输入时 每两位数之间不必分隔符 符合数值的输入习惯 用字符串表示数的缺点 字符串中的每一位是一个字符 不能直接进行运算 必须先将它转化为数值再进行运算 运算时非常不方便 3 因此 综合以上所述 对上面两种数据结构取长补短 用字符串读入数据 用数组存储数据 高精度运算的运算过程 在往下看之前 大家先列竖式计算35 86 注意的问题 1 运算顺序 两个数靠右对齐 从低位向高位运算 先计算低位再计算高位 2 运算规则 同一位的两个数相加再加上从低位来的进位 成为该位的和 这个和去掉向高位的进位就成为该位的值 如上例 3 8 1 12 向前一位进1 本位的值是2 可借助取余 整除运算完成这一步 3 最后一位的进位 如果完成两个数的相加后 进位位值不为0 则应添加一位 4 如果两个加数位数不一样多 则按位数多的一个进行计算 高精度的十进制算 一般形式 输入时为数串转化为整数数组 该数组的每一个元素对应一位十进制数 并使用一变量记录数组的实际长度 即数组元素有效个数 转化方法 memset a 0 number sizeof int k length s for i 1 i k i a k i 1 s i 0 加法运算 确定a和b中的最大位数x x max la lb 依照由低位至高位 第1位至第x位 的顺序进行加法运算 在每一次的运算中 a当前位加b当前位的和除以10 其商即为进位 其余数即为和的当前进位 在进行了x位的加法后 若最高位有进位 a x 1 0 则a的长度为x 1 加法运算算法 实现a a b voidadd inta intb inti x if la lb x la elsex lb for i 1 i0 x x 1 la x 1 减法运算 依照由低位至高位 第1位至第la位 的顺序进行减法运算 在每一次的减法运算中 若出现不够减的情况 a i b i 则向高位借位 a i 1 a i 1 1 a i a i 10 在进行了la位的减法后 若最高位为零 a la 0 则a的长度减1 减法运算算法 a a b voidsub inta intb inti for i 1 i la i if a i b i a i 1 a i 1 1 a i a i 10 a i a i b i while a la 0 la 乘法运算 按照乘法规则 从a的第1位开始逐位与C相乘 在第i位乘法运算中 1 i la a的i位与C的乘积必加上i 1位的进位 i 1位的乘积除以10的整商 然后规整积的i 1位 取i 1位的乘积对10的余数 乘法运算算法 voidmultiply inta intc inti a 1 a 1 c for i 2 i 10 la la 1 a la a la 1 10 a la 1 a la 1 10 改善的高精度运算的效率 以上的方法的有明显的缺点 1 浪费空间 一个整型变量只存放一位 0 9 2 浪费时间 一次加减只处理一位 改进办法 1 扩大进制数 考虑用一个数组元素记录2位数字 3位数字或更多位的数字 但是要考虑到计算机中的一个数的取值范围 必须保证在运算过程中不会越界 如 一个数组元素存放四位数 这样数组就相当于10000进制的数 2 建立因子表 扩大进制数 1数据类型inta 10000 stringst intla ln 2整数数组的建立和输出当输入数串st后 我们从左而右扫描数串st 以四个数码为一组 将之对应的10000进制数据存入数组n中 具体方法如下 扩大进制数 cont 建立 scanf s st K len st For i 0 i k i j k i 3 4 1 n j n j 10 st i 1 48 ln k 3 4 扩大进制数 cont 输出 printf n ln 1 for i ln 2 i 0 i printf d d d d n i 1000 n i 100 10 n i 10 10 n i 10 基本运算 1 整数数组减1 n n 1 n为整数数组 从n 0 出发往左扫描 寻找第一个非零的元素 n j 0 n j 1 n j 2 n j 3 n 0 0 由于该位接受了低位的借位 因此减1 其后缀全为9999 如果最高位为0 则n的长度减1j 0 While n j 0 j n j n j 1 for k 0 k j k n k 9999 if j ln 1 基本运算 cont 2 整数数组除以整数 a a I a为整数数组 i为整数 按照由高位至低位的顺序 逐位相除 在除到第j位时 该位在接受了来自第j 1位的余数 a j a j j 1位相除的余数 10000 后与i相除 如果最高位为0 a la 0 则a的长度减1 基本算法 除法 l 0 For j la 1 j 0lj a j a j l 1000 l a j i a j a i i While a la 1 0 la la 1 基本算法 两个整数数组相乘 a a n 按照由高位到低位的顺序 将a数组的每一个元素与n相乘 当计算到a j n时 根据乘法规则 a j 1 a 0 不变 a j 为原a j 与n 0 的乘积 a j k 加上a j n k 的乘积 k ln 1 ln 2 1 然后按照由低位到高位的顺序处理进位 最后 如果a la 1 n有进位 则乘积a