大整数乘法

简介:

                                                                                     大整数乘法                                                                                                                                                          

分析算法计算复杂性时,加法乘法当做基本运算来处理,即一次加法或者乘法当做一个仅取决于计算机硬件处理速度的常数。

正常的二进制整数X,Y要用O(n2)才能算出。如果分割为两段,

X=A2^(n/2)+B,Y=C2^(n/2)+D。

XY = (A2^(n/2)+B)(C2^(n/2)+D)=AC2^n+(AD+BC)2^(n/2)+BD

要进行4次N/2位整数的乘法,以及3次不超过2n为的整数加法,好要做2次移位。

T(n) = O(n^2);

XY=AC2^n+((A-B)(D-C)+AC+BD)2^(n/2)+BD

仅作3次N/2位整数的乘法,6次加减法,2次移位..

时间复杂度变为t(n)=O(n^1.59)

本文转自博客园xingoo的博客,原文链接:大整数乘法,如需转载请自行联系原博主。
相关文章
|
2月前
|
SQL 存储 关系型数据库
Mysql数据库 1.SQL语言分类 DDL.数据定义语言
Mysql数据库 1.SQL语言分类 DDL.数据定义语言
63 0
|
9月前
|
机器学习/深度学习 传感器 人工智能
2023需要重点关注的四大AI方向
本文是我认为2023年需要重点关注的四大AI方向,这四个方向有望在今年进一步推动AI的发展,并帮助解决行业面临的一些核心挑战。
263 0
2023需要重点关注的四大AI方向
|
机器学习/深度学习 Dart 算法
LightGBM的参数详解以及如何调优(上)
LightGBM的参数详解以及如何调优
419 0
LightGBM的参数详解以及如何调优(上)
|
网络协议 应用服务中间件 Shell
|
移动开发 Dart 前端开发
从架构到源码:一文了解Flutter渲染机制
Flutter从本质上来讲还是一个UI框架,它解决的是一套代码在多端渲染的问题。在渲染管线的设计上更加精简,加上自建渲染引擎,相比ReactNative、Weex以及WebView等方案,具有更好的性能体验。本文将从架构和源码的角度详细分析Flutter渲染机制的设计与实现。较长,同学们可收藏后再看。
6872 1
从架构到源码:一文了解Flutter渲染机制
|
6天前
|
人工智能 自然语言处理 搜索推荐
AiChat—智能办公助手
在当今的数字化时代,人工智能(AI)已经在各个领域中展现出了强大的能力和潜力。AI在许多方面都为我们的生活带来了便利,其中最显著的一点就是在我们的日常交流和工作中。 现在,最简单的低门槛软件应该是AiChat……
183889 11
AiChat—智能办公助手
|
5天前
|
SQL 算法 关系型数据库
PolarDB-X的XPlan索引选择
对于数据库来说,正确的选择索引是基本的要求,选错索引轻则导致查询缓慢,重则导致数据库整体不可用。PolarDB-X存在多种不同的索引,局部索引、全局索引、列存索引、归档表索引。本文主要介绍一种CN上的局部索引算法:XPlan索引选择。
PolarDB-X的XPlan索引选择
|
6天前
|
人工智能 Prometheus 监控
面向智算服务,构建可观测体系最佳实践
面向智算服务,构建可观测体系最佳实践
136468 40
|
6天前
|
运维 Kubernetes 应用服务中间件
Higress × OpenKruiseGame 游戏网关最佳实践
Higress × OpenKruiseGame 游戏网关最佳实践
133273 0
|
11天前
|
开发工具 数据库 git
向量检索服务体验评测
通过一个实用的例子带你全方位了解向量检索服务DashVector
119985 2