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 🐱👓博主在前端领域还有很多知识和技术需要掌握,正在不断努力填补技术短板。(如果出现…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
