【分治算法】大整数乘法Python实现

文章目录

    • @[toc]
      • 问题描述
      • 基础算法
        • 时间复杂性
      • 优化算法
        • 时间复杂性
      • `Python`实现

因上努力

个人主页:丷从心.

系列专栏:Python基础

学习指南:Python学习指南

果上随缘


问题描述

  • X X X Y Y Y都是 n n n位二进制整数,计算它们的乘积 X Y XY XY

基础算法

  • n n n位二进制整数 X X X Y Y Y都分为 2 2 2段,每段的长为 n / 2 n / 2 n/2位(假设 n n n 2 2 2的幂)
    • X = A × 2 n / 2 + B X = A \times 2^{n / 2} + B X=A×2n/2+B
    • Y = C × 2 n / 2 + D Y = C \times 2^{n / 2} + D Y=C×2n/2+D
    • X Y = ( A × 2 n / 2 + B ) ( C × 2 n / 2 + D ) = A C × 2 n + ( A D + B C ) × 2 n / 2 + B D XY = (A \times 2^{n / 2} + B)(C \times 2^{n / 2} + D) = AC \times 2^{n} + (AD + BC) \times 2^{n / 2} + BD XY=(A×2n/2+B)(C×2n/2+D)=AC×2n+(AD+BC)×2n/2+BD
时间复杂性
  • 如果按此式计算 X Y XY XY,必须进行 4 4 4 n / 2 n / 2 n/2位整数的乘法, 3 3 3次不超过 2 n 2n 2n位的整数加法,以及 2 2 2次移位,所有这些加法和移位共用 O ( n ) O(n) O(n)步运算

T ( n ) = { O ( 1 ) n = 1 4 T ( n / 2 ) + O ( n ) n > 1 T(n) = \begin{cases} O(1) & n = 1 \\ 4 T(n / 2) + O(n) & n > 1 \end{cases} T(n)={O(1)4T(n/2)+O(n)n=1n>1

T ( n ) = O ( n 2 ) T(n) = O(n^{2}) T(n)=O(n2)


优化算法

  • 要想改进算法的计算复杂性,必须减少乘法次数,把 X Y XY XY写成另一种形式
    • X Y = A C × 2 n + ( ( A − B ) ( D − C ) + A C + B D ) × 2 n / 2 + B D XY = AC \times 2^{n} + ((A - B)(D - C) + AC + BD) \times 2^{n / 2} + BD XY=AC×2n+((AB)(DC)+AC+BD)×2n/2+BD
时间复杂性
  • 需做 3 3 3 n / 2 n / 2 n/2位整数的乘法, 6 6 6次加减法和 2 2 2次移位

T ( n ) = { O ( 1 ) n = 1 3 T ( n / 2 ) + O ( n ) n > 1 T(n) = \begin{cases} O(1) & n = 1 \\ 3 T(n / 2) + O(n) & n > 1 \end{cases} T(n)={O(1)3T(n/2)+O(n)n=1n>1

T ( n ) = O ( n log ⁡ 3 ) = O ( n 1.59 ) T(n) = O(n^{\log{3}}) = O(n^{1.59}) T(n)=O(nlog3)=O(n1.59)


Python实现

def karatsuba_multiply(x, y):
    # 如果乘数之一为 0, 则直接返回 0
    if x == 0 or y == 0:
        return 0

    # 将乘数转换为字符串, 并获取它们的位数
    x_str = str(x)
    y_str = str(y)

    n = max(len(x_str), len(y_str))

    # 达到基本情况时, 使用传统的乘法
    if n == 1:
        return x * y

    # 将乘数补齐到相同的位数
    x_str = x_str.zfill(n)
    y_str = y_str.zfill(n)

    # 将乘数划分为两部分
    m = n // 2

    high1, low1 = int(x_str[:m]), int(x_str[m:])
    high2, low2 = int(y_str[:m]), int(y_str[m:])

    # 递归地计算三个乘法
    z0 = karatsuba_multiply(low1, low2)
    z1 = karatsuba_multiply((low1 + high1), (low2 + high2))
    z2 = karatsuba_multiply(high1, high2)

    # 计算结果
    res = (z2 * 10 ** (2 * m)) + ((z1 - z2 - z0) * 10 ** m) + z0

    return res


x = 123456789012345678901234567890
y = 987654321098765432109876543210

res = karatsuba_multiply(x, y)

print(f'{x} * {y} = {res}')
123456789012345678901234567890 * 987654321098765432109876543210 = 1118682545728135594602764865374020721634181747367148900

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/526207.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

猫冻干可以每天吃吗?5大优选品牌脆弱肠胃闭眼入

近年来,冻干猫粮作为备受追捧的高品质猫粮,吸引了越来越多养猫人的关注,对于像我这样的养猫达人来说,早已尝试并认可了冻干喂养。但对于新手来说,他们可能会感到困惑:冻干到底是什么?猫冻干可以…

腾讯电商运营起来竟然这么简单!视频号小店操作玩法一文详解!

大家好,我是电商小布。 在新型电商玩法的兴起下,很多的平台都在电商行业内分到了一杯羹。 腾讯自然也就坐不住了,背靠自身的视频号平台,推出了视频号小店这个项目。 有很多的小伙伴想要趁着这个初期阶段,来加入到其…

CentOS部署Apache Superset大数据可视化BI分析工具并实现无公网IP远程访问

文章目录 前言1. 使用Docker部署Apache Superset1.1 第一步安装docker 、docker compose1.2 克隆superset代码到本地并使用docker compose启动 2. 安装cpolar内网穿透,实现公网访问3. 设置固定连接公网地址 前言 Superset是一款由中国知名科技公司开源的“现代化的…

cesium 地图旋转 整个场景旋转 开场动画

设置camera旋转能实现整个场景的旋转,多用于开场动画 开始旋转 function onTickCallback() {viewer.scene.camera.rotate(Cesium.Cartesian3.UNIT_Z, -0.02);}viewer.clock.onTick.addEventListener(onTickCallback); 停止旋转 viewer.clock.onTick.removeEvent…

掼蛋八大定律

1、首引定律 沟通是掼蛋的灵魂,原则上前三手牌都需要沟通。第一手牌,沟通牌力强弱;第二手牌沟通上游概率;第三手牌沟通双下可能。首引定律有几个公式:(1)首引小单牌示弱;&#xff0…

CCIE-10-IPv6-TS

目录 实验条件网络拓朴 环境配置开始Troubleshooting问题1. R25和R22邻居关系没有建立问题2. 去往R25网络的下一跳地址不存在、不可用问题3. 去往目标网络的下一跳地址不存在、不可用 实验条件 网络拓朴 环境配置 在我的资源里可以下载(就在这篇文章的开头也可以下…

FDFB with smaller noise

参考文献: [CZB22] Clet P E, Zuber M, Boudguiga A, et al. Putting up the swiss army knife of homomorphic calculations by means of TFHE functional bootstrapping[J]. Cryptology ePrint Archive, 2022.[MHW23] Ma S, Huang T, Wang A, et al. Fast and ac…

富家千金私奔破产小子:卓文君与渣男司马相如

当戏文里爱唱的千金大小姐爱上穷小子成为现实,是否会像电视剧里的一样美好。 司马相如与卓文君的爱情故事就上演了这样的戏码,他所作的一首《凤求凰》更是被传成佳话,千古流传。 让大多数人误以为他们伉俪情深,可是事情的真相却…

低代码平台种草推荐

告别繁琐,拥抱未来!只需简单拖拽,Vue代码即刻生成,一键下载,轻松上手。我们的低代码平台,不仅高效便捷,更完全开源,让你自由探索编程的无限可能! 下载网址:ht…

elasticsearch -- mapping(动态映射)

Dynamic field mapping (动态字段类型映射) ES 官方文档地址 个人理解: 本篇主要描述的是 ES会根据保存的字段动态的设置字段类型,不像MySQL创建表时需要定义字段类型 Date detection 数据检测(默认开启) _mapping 命令:查看文档中各个字段的数据类型 PUT my-index-000001…

免费试用!英智未来BayStone平台提供高性能算力服务

英智未来BayStone人工智能公共服务平台聚焦全球高端算力资源,提供基于英伟达HGX1系列GPU算力服务,现面向所有政企和科研机构提供现货算力资源服务。点击申请试用 BayStone平台通过全球算力资源调度,帮助用户高效使用高端算力资源,…

学透Spring Boot — 004. Spring Boot Starter机制和自动配置机制

如果你项目中一直用的是 Spring Boot,那么恭喜你没有经历过用 Spring 手动集成其它框架的痛苦。 都说 Spring Boot 大大简化了 Spring 框架开发 Web 应用的难度,这里我们通过配置 Hibernate 的两种方式来深刻体会这一点: 使用 Spring 框架集…

【MIT6.S081】Lab1: Xv6 and Unix utilities(详细解答版)

实验内容网址:https://xv6.dgs.zone/labs/requirements/lab1.html Sleep 关键点:函数参数判断、系统函数调用 思路: 通过argc来判断函数参数是否正确,通过atoi函数来讲字符串转化为整型,调用sleep函数后退出程序。 代…

守护人类健康:人工智能赋能医疗领域创新应用

编者按:每年的4月7日是世界卫生日,又称世界健康日,旨在引起世界各国人民对卫生、健康工作的关注,提高人们对卫生领域的素质和认识,强调健康对于劳动创造和幸福生活的重要性。那么,如果医疗技术能够更加智能…

vue vue3 日期选择的组件,封装组件

一、背景 基于element日期选择组件,自行封装了一个组件。 以下是达到的效果: 1.选择年,日期选择组件默认填充是:当时的年; 2.选择月,日期选择组件默认填充的是:当时的年月; 3.选择日…

Redis监控方案以及相关黄金指标提升稳定性和可靠性

Redis监控方案以及相关黄金指标提升稳定性和可靠性 1. 需要了解的词2. 「基准性能」相关指标2.1 Latency2.2 最大响应延迟2.3 平均响应延迟2.4 OPS(instantaneous_ops_per_sec)2.5 Hit Rate 3. 「内存」相关指标3.1 内存使用量(used_memory)3.2 内存碎片率(mem_fragmentation_r…

商业银行布局AI大模型的“三大路径”

随着人工智能技术的迅猛发展,AI创新应用模式持续涌现,2022年11月OpenAI推出的对话式通用人工智能工具ChatGPT正式上线,标志着人工智能技术的发展迈入了全新阶段。随着ChatGPT的蹿红,一时间,人工智能大模型技术迅速成为…

区块链相关概念

区块链是什么,就算是做计算机技术开发的程序员,100个当中都没有几个能把这个概念理解明白,更不要说讲清楚了。那对于普通人来说,就更扯了。 除了“挖矿”表面意思似乎比较好理解外,其他的基础概念真TMD绕。 去中心化、…

OpenHarmony应用启动流程分析——ApplicationAbility初始化

作者:汪语 一、引言 本文基于OpenAtom OpenHarmony(以下简称“OpenHarmony”) 4.0 Release版本的源码,对应用进程初始化后MainThread初始化及调用AttachApplication、LaunchApplication、LaunchAbility的过程做了分析和总结&…