C++实现大整数乘法-6ren

C++实现大整数乘法

转载作者：qq735679552 更新时间：2022-09-29 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章C++实现大整数乘法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

算法竞赛入门经典这本书并没有对大数乘法实现，所以自己补充了一下，乘法的实现很简单，就是再其数据结构基础上把每宽为8位的十进制数看成多项式的系数，vector的下标看成多项式的指数，然后再对应相乘相加就可以了，注意系数超过8位将超八位的补分进位.

我这里是笛卡尔相乘。一般来说是够用的.

但其实多项式乘法算法还有很多更高效的.

 
    ? 
   
         #include <iostream> 
        
         #include <vector> 
        
         #include <cstring> 
        
         #include <cstdio> 
        
         using 
         namespace 
         std; 
        
         typedef 
         long 
         long 
         LL; 
        
         struct 
         BigInteger{ 
        
         static 
         const 
         int 
         BASE = 100000000; 
        
         static 
         const 
         int 
         WIDTH = 8; 
        
         vector< 
         int 
         > s; 
        
         BigInteger operator = ( 
         const 
         string& str){ 
        
         s.clear(); 
        
         int 
         x, len=(str.length()-1)/WIDTH+1; 
        
         for 
         ( 
         int 
         i=0;i<len;i++){ 
        
         int 
         r=str.length()-i*WIDTH; 
        
         int 
         l=max(0,r-WIDTH); 
        
         sscanf 
         (str.substr(l,r-l).c_str(), 
         "%d" 
         ,&x); 
        
         s.push_back(x); 
        
         } 
        
         return 
         * 
         this 
         ; 
        
         } 
        
         BigInteger operator * ( 
         const 
         BigInteger& b){ 
        
         BigInteger c; 
        
         int 
         lena= 
         this 
         ->s.size(),lenb=b.s.size(),lenc=lena+lenb-1; 
        
         LL *buf = 
         new 
         LL[lenc+1]; 
        
         for 
         ( 
         int 
         i=0;i<lenc+1;i++)buf[i]=0; 
        
         for 
         ( 
         int 
         i=0;i<lena;i++) 
        
         for 
         ( 
         int 
         j=0;j<lenb;j++){ 
        
         buf[i+j]+=( 
         this 
         ->s[i])*((LL)b.s[j]); 
        
         buf[i+j+1]+=buf[i+j]/BASE; 
        
         buf[i+j]=buf[i+j]%BASE; 
        
         } 
        
         for 
         ( 
         int 
         i=0;i<lenc;i++)c.s.push_back(buf[i]); 
        
         if 
         (buf[lenc])c.s.push_back(buf[lenc]); 
        
         return 
         c; 
        
         } 
        
         BigInteger operator * ( 
         const 
         int 
         & x){ 
        
         char 
         c[128]; 
        
         sprintf 
         (c, 
         "%d" 
         ,x); 
        
         string str(c); 
        
         BigInteger res; 
        
         res=str; 
        
         return 
         * 
         this 
         *res; 
        
         } 
        
         }; 
        
         ostream& operator<<(ostream& out, 
         const 
         BigInteger& b){ 
        
         int 
         len=b.s.size(); 
        
         out<<b.s[len-1]; 
        
         for 
         ( 
         int 
         i=len-2;i>=0;i--){ 
        
         int 
         buf=b.s[i],h=8; 
        
         while 
         (buf>0){buf/=10;h--;} 
        
         for 
         ( 
         int 
         j=0;j<h;j++)out<<0; 
        
         if 
         (b.s[i])out<<b.s[i]; 
        
         } 
        
         return 
         out; 
        
         } 
        
         int 
         main() 
        
         { 
        
         int 
         n;BigInteger b; 
        
         b= 
         "1000000000000" 
         ; 
        
         cout<< b<<endl; 
        
         cout<< (b*b)*4*b*b <<endl; 
        
         }

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我.

原文链接：https://blog.csdn.net/yinxiaobao97/article/details/83477734 。

最后此篇关于C++实现大整数乘法的文章就讲到这里了,如果你想了解更多关于C++实现大整数乘法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： C++实现大数相乘算法

文章推荐：一文明白calico的IPIP网络模式

文章推荐： EasyC++，C++指针初探

文章推荐：网络地址转换（NAT）之报文跟踪

Fortran:整数*4 vs 整数(4) vs 整数(kind=4)
我正在尝试学习 Fortran，并且看到了很多不同的定义，我想知道他们是否正在尝试完成同样的事情。以下有什么区别？整数*4 整数(4) 整数(kind=4) 最佳答案在 Fortran >=90
list - 转换 [整数] -> 整数
我以前从未编程过，最近(1 周前)才开始学习!第一门类(class)是函数式编程，使用 Haskell。我有一项学校作业，我想通过删除一两个步骤来改进它，但我遇到了一个讨厌的错误。基本上，我创建了
graphql - 变量和参数的类型不匹配(整数/整数)
给定以下GraphQL请求和变量: 请求: query accounts($filter:AccountFilter, $first_:String, $skip_:Int) { accounts
javascript - 整数、整数+点和小数的正则表达式
我已经搜索了 StackOverflow，但找不到关于如何检查计算器应用程序的数字输入正则表达式的答案，该计算器应用程序将检查每个 keyup 的以下格式(jquery key up): 任何整数，例
Java 图形 : setClip vs clipRect vs repaint(int, 整数、整数、整数)
类似于我上一篇致歉的文章，但没有那么长篇大论。基本上我想知道当每次重绘调用只重绘屏幕的一小部分时，优化重绘到 JFrame/JPanel 的最佳选择是什么。此外，除了重绘重载之外，我并不是 100%
math - F#:整数 (%) 整数 - 是如何计算的？
所以在我的教科书中有一个使用 f# 的递归函数的例子 let rec gcd = function | (0,n) -> n | (m,n) -> gcd(n % m,m);; 使用此功能，我的教科书
haskell - 给测量数据结构的函数赋予什么类型？整数，整数，积分？
我有一个数据结构，例如表达式树或图形。我想添加一些“测量”功能，例如depth和 size . 如何最好地键入这些函数？我认为以下三个变体的用处大致相同: depth :: Expr -> Int
java - compareTo 与原语 -> 整数/整数
这样写比较好 int primitive1 = 3, primitive2 = 4; Integer a = new Integer(primitive1); Integer b = new Inte
Java 8 HashMap<整数, ArrayList<整数>>
我是 Java 8 新手，想根据键对 Map 进行排序，然后在值内对每个列表进行排序。我试图寻找一种 Java 8 方法来对键和值进行排序。HashMap>映射 map.entrySet().str
C++: vector <对< vector <整数>，整数>>
这就是我的目标... vector ,int> > var_name (x, pair (y),int>); 其中 x 是 vector var_name 的大小，y 是对内 vector 的大小。
java - 队列<整数> q = new LinkedList<整数>()
这里是 an answer to "How do I instantiate a Queue object in java?" , Queue is an interface. You can't i
java - 整数 i=3 vs 整数 i= 新整数 (3)
这个问题在这里已经有了答案: Weird Integer boxing in Java (12 个答案) Why are autoboxed Integers and .getClass() val
C++: 对< vector <整数>, vector <整数>> p;
我们可以使用 C++ STL 做这样的事情吗？如果是，我将如何初始化元素？我试图这样做，但没有成功。 pair,vector>p; p.first[0]=2; 最佳答案 Can we do som
javascript - 基于值(整数，字符串)或(整数， float )的混合返回数组的索引
您好，我正在尝试为百分比和整数数组中的数字找到索引。假设 arraynum = ['10%','250','20%','500'] 并且用户发送一个值 15%，这个数字在哪个范围内居住？我可以使用这段
mysql - 将 AVG(整数) 与类别的 AVG(整数) 进行比较
我与三列有关系:ProductName、CategoryID 和 Price。我需要选择仅那些价格高于给定类别中平均产品价格的产品。(例如，当apple(ProductName)是fruit(Cate
c++ - 如何打印对的第二部分？ EX : pair>
我已经坚持了一段时间，我正在尝试将一些数据配对在一起。这是我的代码。 #include #include using namespace std; int main() { pair data(
swift - '(整数，整数 )' is not identical to ' CGPoint'
我收到错误:'(Int, Int)' 与 'CGPoint' 不相同如何将 (Int, Int) 转换为 CGPoint let zigzag = [(100,100), (100,150)
c++ - 这是什么 C++ 语言构造 : # (i. e。哈希)整数 "path_to_header_or_cpp_file"<整数>？
我在 .cpp 文件中发现了以下代码。我不理解涉及头文件的构造或语法。我确实认识到这些特定的头文件与 Android NDK 相关。但是，我认为这个问题是关于 C++ 语法的一般问题。这些在某种程度上
scala - 整数 vs 整数 : type mismatch, 找到 : Int, 需要:字符串
我将这些输入到 Scala 解释器中: val a : Integer = 1; val b : Integer = a + 1; 我收到消息: :5: error: type mismatch;
c++ - vector <对<整数，整数>>v(大小)；打印时显示 0 作为值
C++:vector>v(size);当我试图打印出值时显示 0 作为值，但是当未声明 vector 大小时它显示正确的输出？为什么这样？例如: int x; cin>>x; vector>v(x);

qq735679552

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

C++实现大整数乘法