问题描述

由于计算机的精度是有限的, 因此在某些需要高精度乘法运算的场合, 直接说是用原子数据类型来完成两个大整数乘法是不切实际的.

问题分析

可以使用两个数组分别表示需要相乘的两个大整数, 对数组中的元素分别进行乘法运算并将结果根据乘法法则有序存放在结果数据中, 然后处理进位问题.

举个简单的例子, 例如表达式123*456的两个因数, 数学运算如下:

 123
*456
-----
  738	
 615 
492
------
56088

可以分别使用数组: a[] = {1,2,3} 和 b[] = {4,5,6}进行表示. 对应的数组运算如下:

 {1,2,3}
*{4,5,6}
---------
{18,12,6}				//Expression1
   {15,10,5}			//Expression2
      {12,8,4}			//Expression3
----------------
{18,27,28,13,4}
----------------	
逆序得到:{4,13,28,27,18}

进位处理:56088

为了简化代码, 可以将a[]和b[]都进行逆序, 并且在最后计算结果时,先进位,再逆序. 具体运算步骤如下:

创建一个新数组ret[]存储乘积, 由于n位整数与m位整数的乘积的位数可能为m+n或m+n-1, 取其大者,因此可以数组ret大小可以定义为两个数的各自的位数之和;
将a[]和b[]都进行逆序
将a0分别与b[]中的元素相乘, 结果分别存储在ret[0]…ret[N]中;(Expression1)
将a1与b[]中的元素相乘, 结果分别存储在ret[1]…ret[N]中;(Expression2)
类推将a[m]与b[]中的元素相乘, 结果分别存储在ret[m]…ret[N]中;
按照十进制进位法则, 对ret[]中大于10的位进行进位处理;
将ret[]进行逆序
输出结果

由此可以类推到多位大整数的乘法实现.

问题解决

//
//  main.cpp
//  大整数乘法
//
//  Created by Miu on 16/11/30.
//  Copyright © 2016年 XB. All rights reserved.
//

#include <iostream>
using namespace std;
void swapNum(int& num1, int& num2)
{
    num1 = num1 + num2;
    num2 = num1 - num2;
    num1 = num1 -num2;
}

void reverseArray(int nums[], int length)
{
    int begin = 0;
    int end = length - 1;
    while (begin < end) {
        swapNum(nums[begin++], nums[end--]);
    }
}

void outNums(int nums[], int count)
{
    for (int i = 0; i < count; i++) {
        cout << nums[i];
    }
    cout << endl;
}

void multi(int num1[], int length1, int num2[], int length2)
{
    reverseArray(num1, length1);
    reverseArray(num2, length2);

    
    int retLength = length1+length2;
    int *ret = new int(retLength);
    memset(ret, 0, sizeof(int)*retLength);
    for (int i=0; i < length1; i++) {
        int k = i;
        for (int j = 0; j < length2; j++) {
            ret[k++] += num1[i] * num2[j];
        }
    }
    for (int i = 0; i < retLength; i++) {
        if (ret[i] > 10) {
            ret[i+1] += ret[i]/10;
            ret[i] = ret[i]%10;
        }
    }
    
    //逆序
    reverseArray(ret, retLength);
    
    //结果位数不足时, 数组第一元素可能为0, 需要清除
    if (ret[0] == 0) {
        for (int i = 0; i < retLength-1; i++) {
            ret[i] = ret[i+1];
        }
        retLength -= 1;
    }
    
    outNums(ret,retLength);
}

int main(int argc, const char * argv[]) {
    int a[] = {1,2,3};
    int b[] = {4,5,6};
    
    multi(a, 3, b, 3);
    
    return 0;
}

输出: 56088

做点有意思的事情

C++之大整数乘法问题

问题描述

问题分析

问题解决