当前位置:网站首页>Cartoon: how to multiply large integers? (I) revised version
Cartoon: how to multiply large integers? (I) revised version
2022-07-05 17:28:00 【Small ash】
In the new cartoon released by Xiaohui on Monday , There are two small problems :
1. about master The third condition of the theorem is incorrectly stated , Should be a+ε, instead of a-ε.
2. Divide and conquer T(n) and T(n/2) The relationship between master The first condition of the theorem , Calculation ε The process of value is wrong .
These two questions have been revised this time , Thank you very much for your correction .
Some time ago , A cartoon about the small sum of grey numbers was published , If you haven't seen it, you can have a look first :
comic : How to add big integers ?( Revised edition )
that , How to realize the multiplication of large integers ?
At first , Xiaohui thinks that as long as the idea of adding large integers is done a little deformation , You can easily multiply large integers . But with further study , Xiaohui found out that things are not so simple ......
————— the second day —————
How to list the multiplication column ? With 93281 X 2034 For example , The vertical form is as follows :
In the program , We can use int Type of the array , Store two large integers by bit , Then the elements in the array are calculated one by one like the primary vertical .
The calculation of the multiplication column can be roughly divided into two steps :
1. Integers B Every digit and integer of A All the digits are multiplied in turn , Get an intermediate result .
2. All the intermediate results add up , Get the final result .
/**
* The product of large integers
* @param bigNumberA Large integer A
* @param bigNumberB Large integer B
*/
public static String multiply(String bigNumberA, String bigNumberB) {
//1. Store two large integers in reverse order , The length of the array is equal to the sum of the lengths of two integers
int lengthA = bigNumberA.length();
int lengthB = bigNumberB.length();
int[] arrayA = new int[lengthA];
for(int i=0; i< lengthA; i++){
arrayA[i] = bigNumberA.charAt(lengthA-1-i) - '0';
}
int[] arrayB = new int[lengthB];
for(int i=0; i< lengthB; i++){
arrayB[i] = bigNumberB.charAt(lengthB-1-i) - '0';
}
//2. structure result Array , The length of the array is equal to the sum of the lengths of two integers
int[] result = new int[lengthA+lengthB];
//3. Nested loop , Integers B Each bit of, in turn, is an integer A Multiply all the digits of , And add up the results
for(int i=0;i<lengthB;i++) {
for(int j=0;j<lengthA;j++) {
// Integers B A bit and an integer of A Multiply one of the two
result[i+j] += arrayB[i]*arrayA[j];
// If result One is greater than 10, Then carry , The number of carry is the number of bits divided by 10 The business of
if(result[i+j] >= 10){
result[i+j+1] += result[i+j]/10;
result[i+j] = result[i+j]%10;
}
}
}
//4. hold result The array is reversed again and converted to String
StringBuilder sb = new StringBuilder();
// Whether to find the most significant bit of a large integer
boolean findFirst = false;
for (int i = result.length - 1; i >= 0; i--) {
if(!findFirst){
if(result[i] == 0){
continue;
}
findFirst = true;
}
sb.append(result[i]);
}
return sb.toString();
}
public static void main(String[] args) {
String x = "3338429042340042304302404";
String y = "12303231";
System.out.println(multiply(x, y));
}
————————————
below , There will be some brain burning in our derivation , Please sit down and hold on ~~
Large integers go from high to low , It's divided into two parts . Set integer 1 The high part of is A, The lower part is B; Integers 2 The high part of is C, The lower part is D, So there's the following equation :
If we abstract the length of a large integer as n, that :
therefore , Integers 1 And integers 2 The product of can be written in the following form :
In this way , The original length was n Of large integers 1 Times product , Transformed into length n/2 Of large integers 4 Times product (AC,AD,BC,BD).
What is? master And the theorem ?
master The English name of the theorem is master theorem, It's for many The recurrence relation obtained by divide and conquer method Provides a progressive time complexity analysis .
Let's set a constant a >= 1,b > 1, If the overall computational scale of an algorithm T(n) = a T(n / b) + f(n), Then there are the following rules :
Suppose two lengths are n Multiply the large integers of , The overall operation scale is T(n) .
According to the conclusion just reached , The multiplication of two large integers is split into four smaller products :
So in the first partition ,T(n) and T(n/2) Has the following relation :
T(n) = 4T(n/2) + f(n)
among f(n) yes 4 The operation scale of adding the product results ,f(n) The incremental time complexity of is obviously O(n).
Bring this relationship to master The formula of the theorem T(n) = a T(n / b) + f(n) among ,
here a=4, b=2.
here , hold a and b Value , as well as f(n) Time complexity brought to master The first law of the theorem , That's the following rule :
It's just the right thing to do .
How does it fit ? The derivation process is as follows :
So our average time complexity is :
—————END—————
边栏推荐
- CVPR 2022 best student paper: single image estimation object pose estimation in 3D space
- 激动人心!2022开放原子全球开源峰会报名火热开启!
- Oracle缩表空间的完整解决实例
- stirring! 2022 open atom global open source summit registration is hot!
- 漫画:一道数学题引发的血案
- Wsl2.0 installation
- ThoughtWorks global CTO: build the architecture according to needs, and excessive engineering will only "waste people and money"
- 33: Chapter 3: develop pass service: 16: use redis to cache user information; (to reduce the pressure on the database)
- Domain name resolution, reverse domain name resolution nbtstat
- ClickHouse(03)ClickHouse怎么安装和部署
猜你喜欢
Embedded UC (UNIX System Advanced Programming) -2
mysql中取出json字段的小技巧
Embedded UC (UNIX System Advanced Programming) -1
Judge whether a string is a full letter sentence
Judge whether a number is a prime number (prime number)
Kafaka技术第一课
北京内推 | 微软亚洲研究院机器学习组招聘NLP/语音合成等方向全职研究员
First day of learning C language
ICML 2022 | meta proposes a robust multi-objective Bayesian optimization method to effectively deal with input noise
MySQL之知识点(六)
随机推荐
一个满分的项目文档是如何书写的|得物技术
7. Scala class
張平安:加快雲上數字創新,共建產業智慧生態
Zhang Ping'an: accelerate cloud digital innovation and jointly build an industrial smart ecosystem
The third lesson of EasyX learning
【testlink】TestLink1.9.18常见问题解决方法
独立开发,不失为程序员的一条出路
IDC报告:腾讯云数据库稳居关系型数据库市场TOP 2!
Kafaka technology lesson 1
The first lesson of EasyX learning
High number | summary of calculation methods of volume of rotating body, double integral calculation of volume of rotating body
Redis+caffeine two-level cache enables smooth access speed
Embedded-c Language-4
In depth understanding of redis memory obsolescence strategy
【jmeter】jmeter脚本高级写法:接口自动化脚本内全部为变量,参数(参数可jenkins配置),函数等实现完整业务流测试
Embedded-c Language-5
基于Redis实现延时队列的优化方案小结
Error in composer installation: no composer lock file present.
[Jianzhi offer] 62 The last remaining number in the circle
Embedded -arm (bare board development) -1