我的编程空间,编程开发者的网络收藏夹
学习永远不晚

如何实现大整数乘法运算与分治算法

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

如何实现大整数乘法运算与分治算法

本篇内容主要讲解“如何实现大整数乘法运算与分治算法”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何实现大整数乘法运算与分治算法”吧!

普通乘数运算

对于乘数运算有一种比较简单较为容易理解的方法,我们可以利用小学时期学的列竖式的计算方法进行乘法运算。

如何实现大整数乘法运算与分治算法

列竖式乘法运算

参考上图中的列竖式计算方法,我们进行代码实现。

#include <iostream> #include <string> #include <stdlib.h> #include <vector> #include <cstring> #include <algorithm>  std::string multiply(std::string a, std::string b) {     std::string result = "";     int row = b.size();     int col = a.size() + 1;     int tmp[row][col];     memset(tmp,0, sizeof(int)*row*col);          reverse(a.begin(),a.end());     reverse(b.begin(),b.end());          for(int i = 0; i < b.size(); i++)     {         for(int j = 0; j < a.size(); j++)         {             std::string bit_a = std::string(1, a.at(j));             std::string bit_b = std::string(1, b.at(i));                          tmp[i][j] += std::stoi(bit_a) * std::stoi(bit_b);                      tmp[i][j+1] = tmp[i][j] / 10;             tmp[i][j] %= 10;          }      }      int N =  a.size() + b.size();     int sum[N];     memset(sum, 0, sizeof(int)*N);          for(int n = 0; n < N; n++)     {         int i = 0;         int j = n;                  while (i <= n && j >= 0 )         {             if(i < row && j < col)             {                 sum[n] += tmp[i][j];             }                          i++;             j--;         }          if( n+1 < N )         {             sum[n+1] = sum[n] / 10;             sum[n] %= 10;         }      }      bool zeroStartFlag = true;     for (int i = N-1; i >= 0; i--)     {         if(sum[i]==0 && zeroStartFlag)         {             continue;         }                  zeroStartFlag = false;         result.append(std::to_string(sum[i]));     }          return result; }   int main() {     std::string a = "3456";     std::string b = "1234";      std::string result = multiply(a, b);         std::cout << a << " * " << b << " = " << result <<std::endl;          return 0; }

为了方便我们先将各个乘数做了翻转处理,最后需要再将结果翻转回来。在运算过程中用来存放乘法运算结果的数组,我们没有进行移位处理同列相加,而是对角线相加,这样可以减少空间和运算步骤。上面的代码运行结果如下所示。

如何实现大整数乘法运算与分治算法

运行结果

因为字符串的长度没有特别的限制,所以上面的算法可以适用大整数运算。

分治算法

虽然上面的列竖式的方法可以很好的解决大整数乘法的问题,但是我们还用一种更加高效的方法可以选择,这就是分治(Divide and  Conquer)算法。它是一种非常重要的算法,可以应用到很多领域,比如快速排序,二分搜索等。从算法的名字我们可以看出它是将大的问题拆分进行细化,由大变小,先将小的问题解决,最终将这个问题解决,所以叫Divide  and Conquer。在这里我们可以通过这种方法将大整数进行拆分,拆分成一个个可以通过程序语言直接进行运算的小整进行计算,最后求得到大整数的值。

假设有两个大整数,我们设为a(大小为n位)和b(大小为m位),这里我们将使用二分法对数据进行拆分,这两个整数我们可以分解为:

如何实现大整数乘法运算与分治算法

则,

如何实现大整数乘法运算与分治算法

令,

如何实现大整数乘法运算与分治算法

根据上面公式里,我们可以将a*b分解为四个小的整数的乘法,即z3,z2,z1,z0四个表达式。如果分解出来的乘法数值还是很大,还可以按照同样的方法进行拆解直到拆解成较小的数值乘法,直到计算机程序语言可以直接运算。

比如,上面的3456和1234相乘,参考下图通过二分法逐级对整数进行拆分,我们将两个整数拆分到一位整数进行运算。

如何实现大整数乘法运算与分治算法

3456和1234拆分步骤图

下面我们看一下分治算法的代码实现,这里我们使用递归的方法。

#include <iostream> #include <string> #include <stdlib.h> #include <vector> #include <cstring> #include <algorithm> #include <cmath>  std::string add(std::string a, std::string b) {     int N = std::max(a.size(), b.size());     int sum[N];     memset(sum, 0, sizeof(int)*N);          reverse(a.begin(),a.end());     reverse(b.begin(),b.end());      for(int i = 0; i< N; i++)     {         int bit_a = 0;         int bit_b = 0;         if(i < a.size()) bit_a = std::stoi(std::string(1, a.at(i)));         if(i < b.size()) bit_b = std::stoi(std::string(1, b.at(i)));          sum[i] += (bit_a + bit_b);          if(i < N-1 && sum[i]>9)         {             sum[i+1] = sum[i] / 10;             sum[i] %=10;         }     }      std::string result="";     bool zeroStartFlag = true;     for (int i = N-1; i >= 0; i--)     {         if(sum[i]==0 && zeroStartFlag)         {             continue;         }                  zeroStartFlag = false;         result.append(std::to_string(sum[i]));     }       return result; }  std::string divideAndConquer(std::string a, std::string b) {     if( a.size() < 2 && b.size() < 2)      {         return std::to_string(std::stoi(a) * std::stoi(b));     }          int n = a.size();     int m = b.size();          int halfN = n/2;     int halfM = m/2;      std::string a0 = "0";     std::string a1 = "0";     if(a.size() > halfN && halfN > 0)     {         a1 = a.substr(0, halfN);         a0 = a.substr(halfN, a.size() - halfN);     }     else     {         a1 = "0";         a0 = a;     }          std::string b0 = "0";     std::string b1 = "0";     if(b.size() > halfM && halfM > 0)     {         b1 = b.substr(0, halfM);         b0 = b.substr(halfM, b.size() - halfM);      }     else     {         b1 = "0";         b0 = b;     }      std::string a1b1 = divideAndConquer(a1, b1);     std::string a0b0 = divideAndConquer(a0, b0);     std::string a1b0 = divideAndConquer(a1, b0);     std::string a0b1 = divideAndConquer(a0, b1);          a1b1.append((n - halfN) + (m - halfM), '0');     a1b0.append(n - halfN, '0');     a0b1.append(m - halfM, '0');      std::string result = "";     result = add(a1b1, a1b0);     result = add(result, a0b1);     result = add(result, a0b0);      return result; }  int main() {     std::string a = "3456";     std::string b = "1234";      std::cout << a << " * " << b << " = " << divideAndConquer(a, b) << std::endl;       return 0; }

程序的运行结果如下:

如何实现大整数乘法运算与分治算法

分治算法运行结果

到此,相信大家对“如何实现大整数乘法运算与分治算法”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

如何实现大整数乘法运算与分治算法

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

看了就会的大整数乘法运算与分治算法

在数据加密处理中有很多复杂的加密算法,这些加密算法往往会用到很多超大的整数运算。

php如何实现乘法运算

本篇内容主要讲解“php如何实现乘法运算”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“php如何实现乘法运算”吧!在PHP中,可以利用“*”算术运算符实现乘法运算,该运算符用于计算前后两个数的乘
2023-06-29

Pytorch如何实现常用乘法算子TensorRT

这篇文章主要介绍了Pytorch如何实现常用乘法算子TensorRT的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇Pytorch如何实现常用乘法算子TensorRT文章都会有所收获,下面我们一起来看看吧。1.乘
2023-06-30

Shell(())如何实现对整数进行数学运算

这篇文章主要介绍“Shell(())如何实现对整数进行数学运算”,在日常操作中,相信很多人在Shell(())如何实现对整数进行数学运算问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Shell(())如何实现
2023-06-09

Java中的排序数索引怎么利用分治算法实现

Java中的排序数索引怎么利用分治算法实现?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。具体如下:/** * Find the first q and return the
2023-05-31

python如何实现比较运算符的方法

这篇文章将为大家详细讲解有关python如何实现比较运算符的方法,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。实现比较运算符的简单方法为一个类实现所有的比较相似(如 lt , le , gt , ge)是
2023-06-27

PHP如何在不使用加减乘除运算符号的情况下实现加法

这篇文章主要讲解了“PHP如何在不使用加减乘除运算符号的情况下实现加法”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“PHP如何在不使用加减乘除运算符号的情况下实现加法”吧!写一个函数,求两个
2023-06-20

python如何实现决策树分类算法

今天小编给大家分享一下python如何实现决策树分类算法的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。前置信息1、决策树决策
2023-07-02

如何实现数值校验的算法

给定一个字符串如何判断它是否为数值类型?本文将带着大家实现这个判断算法。

Python实现的基数排序算法原理与用法实例分析

本文实例讲述了Python实现的基数排序算法。分享给大家供大家参考,具体如下: 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,
2022-06-04

C#算法如何实现两数之和

小编给大家分享一下C#算法如何实现两数之和,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!题目给定一个整数数组 nums和一个目标值 target,请你在该数组中找
2023-06-26

编程热搜

目录