C#,《小白学程序》第二十五课:大数乘法(BigInteger Multiply)的Karatsuba算法及源代码
1 文本格式
/// <summary>
/// 《小白学程序》第二十五课:大数(BigInteger)的Karatsuba乘法
/// Multiplies two bit strings X and Y and returns result as long integer
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string karatsuba_multiply(string a, string b)
{
// Find the maximum of lengths of x and Y and make
// length of smaller string same as that of larger string
int n = Math.Max(a.Length, b.Length);
if (a.Length != n) a = a.PadLeft(n, '0');
if (b.Length != n) b = b.PadLeft(n, '0');
// Base cases
if (n == 0)
{
return "0";
}
else if (n == 1)
{
return ((a[0] - '0') * (b[0] - '0')).ToString();
}
else if (n <= 9)
{
// int max 21474 83647
// long max 9223 37203 68547 75807
return (ulong.Parse(a) * ulong.Parse(b)).ToString();
}
int fh = n / 2; // First half of string
int sh = n - fh; // Second half of string
// Find the first half and second half of first string.
string x1 = a.Substring(0, fh);
string x2 = a.Substring(fh);
// Find the first half and second half of second string
string y1 = b.Substring(0, fh);
string y2 = b.Substring(fh);
// Recursively calculate the three products of
// inputs of size n/2
string p1 = karatsuba_multiply(x1, y1);
string p2 = karatsuba_multiply(x2, y2);
//string P3 = Karatsuba(AddBitStrings(Xl, Xr), AddBitStrings(Yl, Yr));
string p3 = karatsuba_multiply(big_integer_plus(x1, x2), big_integer_plus(y1, y2));
// Combine the three products to get the final result.
//return P1 * (1L << (2 * sh)) + (P3 - P1 - P2) * (1L << sh) + P2;
int[] t1 = new int[sh];
string w1 = String.Join("", t1);
string v1 = p1 + w1 + w1;
string v2 = big_integer_subtract(p3, big_integer_plus(p1, p2)) + w1;
return big_integer_plus(v1, big_integer_plus(v2, p2));
}
2 代码格式
/// <summary>
/// 《小白学程序》第二十五课:大数(BigInteger)的Karatsuba乘法
/// Multiplies two bit strings X and Y and returns result as long integer
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string karatsuba_multiply(string a, string b)
{// Find the maximum of lengths of x and Y and make// length of smaller string same as that of larger stringint n = Math.Max(a.Length, b.Length);if (a.Length != n) a = a.PadLeft(n, '0');if (b.Length != n) b = b.PadLeft(n, '0');// Base casesif (n == 0){return "0";}else if (n == 1){return ((a[0] - '0') * (b[0] - '0')).ToString();}else if (n <= 9){// int max 21474 83647// long max 9223 37203 68547 75807return (ulong.Parse(a) * ulong.Parse(b)).ToString();}int fh = n / 2; // First half of stringint sh = n - fh; // Second half of string// Find the first half and second half of first string.string x1 = a.Substring(0, fh);string x2 = a.Substring(fh);// Find the first half and second half of second stringstring y1 = b.Substring(0, fh);string y2 = b.Substring(fh);// Recursively calculate the three products of// inputs of size n/2string p1 = karatsuba_multiply(x1, y1);string p2 = karatsuba_multiply(x2, y2);//string P3 = Karatsuba(AddBitStrings(Xl, Xr), AddBitStrings(Yl, Yr));string p3 = karatsuba_multiply(big_integer_plus(x1, x2), big_integer_plus(y1, y2));// Combine the three products to get the final result.//return P1 * (1L << (2 * sh)) + (P3 - P1 - P2) * (1L << sh) + P2;int[] t1 = new int[sh];string w1 = String.Join("", t1);string v1 = p1 + w1 + w1;string v2 = big_integer_subtract(p3, big_integer_plus(p1, p2)) + w1;return big_integer_plus(v1, big_integer_plus(v2, p2));
}
相关文章:
C#,《小白学程序》第二十五课:大数乘法(BigInteger Multiply)的Karatsuba算法及源代码
1 文本格式 /// <summary> /// 《小白学程序》第二十五课:大数(BigInteger)的Karatsuba乘法 /// Multiplies two bit strings X and Y and returns result as long integer /// </summary> /// <param name"a">&…...
Redis的五大数据类型详细用法
我们说 Redis 相对于 Memcache 等其他的缓存产品,有一个比较明显的优势就是 Redis 不仅仅支持简单的key-value类型的数据,同时还提供list,set,zset,hash等数据结构的存储。本篇博客我们就将介绍这些数据类型的详细使用…...
C++类与对象(6)—初始化列表、explicit关键字、static成员
目录 一、初始化列表 1、定义 2、注意事项 3、尽量使用初始化列表初始化 4、初始化顺序 二、 explicit关键字 1、定义 2、特点 三、static成员 1、定义 2、特性 3、例题 一、初始化列表 下面这段代码可以正常编译: class A { private:int _a1;//成员…...
vue3+tsx的使用
<template><div><xiaoman on-click"getItem" name"似懂非懂"></xiaoman></div> </template><script setup langts>import xiaoman from "./App"const getItem(item:any)>{console.log(item,it…...
JMeter 设置请求头信息的详细步骤
在使用 JMeter 的过程中,我们会遇到需要设置请求头信息的场景。比如: POST 传过去的 Body 数据是 json 格式的。需要填添加头信息:Content-Type:application/json。 在 header 中用 token 来传用户的认证信息。 下面,…...
从零构建属于自己的GPT系列1:预处理模块
1 训练数据 在本任务的训练数据中,我选择了金庸的15本小说,全部都是txt文件 数据打开后的样子 2 数据预处理 数据预处理需要做的事情就是使用huggingface的transformers包的tokenizer模块,将文本转化为token 最后生成的文件就是train_n…...
002、ArkTS
之——开发语言 目录 之——开发语言 杂谈 正文 1.TypeScript基础 1.1 基础类型 1.2 条件语句 1.3 函数 1.4 类 1.5 模块 1.6 迭代器 2.ArkTS 2.1 JAVA SCRIPT 2.2 TS 2.3 ArkTS 编辑 3.示例 3.1 概述性示例 3.2 自定义组件 3.3 渲染控制语法 3.4 状态管…...
如何通过nginx进行服务的负载均衡
简单介绍 随着互联网的发展,业务流量越来越大并且业务逻辑也越来越复杂,单台服务器的性能及单点故障问题就凸显出来了,因此需要多台服务器组成应用集群,进行性能的水平扩展以及避免单点故障的出现。应用集群是将同一应用部署到多台…...
FPGA程序前仿真和后仿真问题处理
参考链接:FPGA程序前仿真和后仿真问题处理 - 知乎...
C语言WFC绘制矩形
代码实现: void CCGDrawingView::Rectangle(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, COLORREF color,CDC* pDC) {CPen redPen(PS_SOLID, 1, color);CBrush redBursh(color);CPen* pOldPen pDC->SelectObject(&redPen);CBrush* p…...
SpringCloud Alibaba集成 Gateway(自定义负载均衡器)、Nacos(配置中心、注册中心)、loadbalancer
文章目录 POM依赖环境准备配置配置文件配置类 案例展示 POM依赖 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.10</version><relativePath/></p…...
HarmonyOS应用开发者基础认证【题库答案】
HarmonyOS应用开发者高级认证【题库答案】 一、判断 首选项preferences是以Key-Value形式存储数据,其中Key是可以重复。(错)使用http模块发起网络请求时,必须要使用on(‘headersReceive’)订阅请求头,请…...
[pyqt5]pyqt5设置窗口背景图片后上面所有图片都会变成和背景图片一样
pyqt5的控件所有都是集成widget,窗体设置背景图片后控件背景也会跟着改变,此时有2个办法。第一个办法显然我们可以换成其他方式设置窗口背景图片,而不是使用styleSheet样式表,网上有很多其他方法。还有个办法就是仍然用styleSheet…...
【Docker】从零开始:7.Docker命令:容器命令及参数详解
【Docker】从零开始:7.帮助启动类命令 一、帮助启动类命令启动Docker停止Docker重启Docker查看Docker状态开机启动查看docker概要信息查看docker总体帮助文档查看docker命令帮助文档 二、镜像命令列出本地主机上的镜像运行示例返回说明操作参数 搜索仓库里的某个镜像…...
Mysql 锁机制分析
整体业务代码精简逻辑如下: Transaction public void service(Integer id) {delete(id);insert(id); }数据库实例监控: 当时通过分析上游问题流量限流解决后,后续找时间又重新分析了下问题发生的根本原因,现将其总结如下…...
跟着chatgpt学习|1.spark入门
首先先让chatgpt帮我规划学习路径,使用Markdown格式返回,并转成思维导图的形式 目录 目录 1. 了解spark 1.1 Spark的概念 1.2 Spark的架构 1.3 Spark的基本功能 2.spark中的数据抽象和操作方式 2.1.RDD(弹性分布式数据集) 2…...
使用conan包 - 安装依赖项
使用conan包 - 安装依赖项 主目录 conan Using packages1 Requires2 Optional user/channel3 Overriding requirements4 Generators5 Options 本文是基于对conan官方文档Installing dependencies的翻译而来, 更详细的信息可以去查阅conan官方文档。 This section s…...
【数据库设计和SQL基础语法】--数据库设计基础--数据规范化和反规范化
一、 数据规范化 1.1 数据规范化的概念 定义 数据规范化是数据库设计中的一种方法,通过组织表结构,减少数据冗余,提高数据一致性和降低更新异常的过程。这一过程确保数据库中的数据结构遵循一定的标准和规范,使得数据存储更加高…...
复亚智能交通无人机:智慧交通解决方案大公开
城市的现代化发展离不开高效的交通管理规划。传统的交通管理系统庞大繁琐,交警在执行任务时存在安全隐患。在这一背景下,复亚智能交通无人机应运而生,成为智慧交通管理中的重要组成部分。交通无人机凭借其高灵活性、低成本、高安全性等特点&a…...
MYSQL 及 SQL 注入
文章目录 前言什么是sql注入防止SQL注入Like语句中的注入后言 前言 hello world欢迎来到前端的新世界 😜当前文章系列专栏:Mysql 🐱👓博主在前端领域还有很多知识和技术需要掌握,正在不断努力填补技术短板。(如果出现…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
