java 作业：如何写出自己的大数乘法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2120493/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Homework: how to write own multiplication of big numbers?
提问by sasklacz
In my project I have to deal with multiplication of big numbers ( greater then java.long ) stared in my own BigNumberclass as int[]. Basically I need to implement something like this :
在我的项目中，我必须处理在我自己的BigNumber类中作为int[]. 基本上我需要实现这样的东西：
157 x
121 y
----
157 result1
314 + result2
157 + result3
------
18997 finalResult
But how do I implement it?
但是我该如何实施呢？
I thought about expanding result2,3 with zeros (3140, 15700) and adding them. But first I somehow need to navigate between each digit of y and multiply it by each digit of x.
我想过用零 (3140, 15700) 扩展 result2,3 并添加它们。但首先我需要在 y 的每个数字之间导航并将其乘以 x 的每个数字。
回答by James Cronen
Use the diagonal approach. Make an array, and multiply each digit by each other digit and fill in the numbers in each cell.
使用对角线方法。制作一个数组，并将每个数字与其他数字相乘，然后填写每个单元格中的数字。
36 x 92
3 6
+-----+-----+
| 2 / | 5 / |
9 | / | / |
| / 7 | / 4 |
+-----+-----+
| 0 / | 1 / |
2 | / | / |
| / 6 | / 2 |
+-----+-----+
Add the numbers on each diagonal. Move from the least-significant digit (at the lower right) to the most (upper left).
在每个对角线上添加数字。从最不重要的数字（右下角）移到最重要的数字（左上角）。
2 2 (least-significant)
(6 + 1 + 4) = 11 (make this 1, and carry the 1 to the next digit) 1
(5 + 7 + 0 + 1(carried)) = 13 (make this 3, and carry the 1) 3
2 + 1(carried) = 3 3 (most-significant)
The answer's 3312.
答案是 3312。
Make a two-dimensional array of your digits. Fill the array with the multiplications of the single digits together.
制作一个二维数组。用单个数字的乘法填充数组。
Write some logic to scrape the diagonals as I did above.
像我上面那样写一些逻辑来刮掉对角线。
This should work for arbitrarily large numbers (as long as you still have memory left).
这应该适用于任意大的数字（只要你还有内存）。
回答by Max
Here's the code I had written. Basically same as manual multiplication. Pass the two big numbers as strings to this function, the result is returned as a string.
这是我写的代码。与手动乘法基本相同。将两个大数字作为字符串传递给该函数，结果作为字符串返回。
public String multiply(String num1, String num2){
int product, carry=0, sum=0;
String result = new String("");
String partial = new String("");
ArrayList<String> partialList = new ArrayList<String>();
/* computing partial products using this loop. */
for(int j=num2.length()-1 ; j>=0 ; j--) {
for(int i=num1.length()-1 ; i>=0 ; i--) {
product = Integer.parseInt((new Character(num1.charAt(i))).toString()) *
Integer.parseInt((new Character(num2.charAt(j))).toString()) + carry;
carry = product/10;
partial = Integer.toString(product%10) + partial;
}
if(carry != 0)
partial = Integer.toString(carry) + partial;
partialList.add(partial);
partial = "";
carry = 0;
}
/* appending zeroes incrementally */
for(int i=0 ; i<partialList.size() ; i++)
partialList.set(i, partialList.get(i) + (Long.toString( (long)java.lang.Math.pow(10.0,(double)i))).substring(1) );
/* getting the size of the largest partial product(last) */
int largestPartial = partialList.get(partialList.size()-1).length();
/* prefixing zeroes */
int zeroes;
for(int i=0 ; i<partialList.size() ; i++) {
zeroes = largestPartial - partialList.get(i).length();
if(zeroes >= 1)
partialList.set(i, (Long.toString( (long)java.lang.Math.pow(10.0,(double)zeroes))).substring(1) + partialList.get(i) );
}
/* to compute the result */
carry = 0;
for(int i=largestPartial-1 ; i>=0 ; i--) {
sum = 0;
for(int j=0 ; j<partialList.size() ; j++)
sum = sum + Integer.parseInt(new Character(partialList.get(j).charAt(i)).toString());
sum = sum + carry;
carry = sum/10;
result = Integer.toString(sum%10) + result;
}
if(carry != 0)
result = Integer.toString(carry) + result;
return result;
}
回答by Mike Clark
I would avoid the headaches of writing your own and just use the java.math.BigIntegerclass. It should have everything you need.
我会避免编写自己的麻烦，只使用java.math.BigInteger类。它应该有你需要的一切。
回答by sdomalap
I have implemented this in C++. refer to this for logic...
我已经在 C++ 中实现了这个。参考这个逻辑...
#include <iostream>
#include <deque>
using namespace std;
void print_num(deque<int> &num) {
for(int i=0;i < num.size();i++) {
cout<<num[i];
}
cout<<endl;
}
deque<int> sum(deque<int> &oppA, deque<int> &oppB) {
if (oppA.size() == 0) return oppB;
if (oppB.size() == 0) return oppA;
deque<int> result;
unsigned int carry = 0;
deque<int>::reverse_iterator r_oppA = oppA.rbegin();
deque<int>::reverse_iterator r_oppB = oppB.rbegin();
while ((r_oppA != oppA.rend()) && (r_oppB != oppB.rend())) {
int tmp = *r_oppA + *r_oppB + carry;
result.push_front(tmp % 10);
carry = tmp / 10;
r_oppB++;
r_oppA++;
}
while (r_oppA != oppA.rend()) {
int tmp = *r_oppA + carry;
result.push_front(tmp % 10);
carry = tmp / 10;
r_oppA++;
}
while (r_oppB != oppB.rend()) {
int tmp = *r_oppB + carry;
result.push_front(tmp % 10);
carry = tmp / 10;
r_oppB++;
}
return result;
}
deque<int> multiply(deque<int>& multiplicand, deque<int>& multiplier) {
unsigned int carry = 0;
deque<int> result;
int deci_cnt = 0;
deque<int>::reverse_iterator r_multiplier = multiplier.rbegin();
deque<int> tmp_result;
while (r_multiplier != multiplier.rend()) {
for (int i=0; i<deci_cnt ;i++) {
tmp_result.push_front(0);
}
deque<int>::reverse_iterator r_multiplicand = multiplicand.rbegin();
while (r_multiplicand != multiplicand.rend()) {
int tmp = (*r_multiplicand) * (*r_multiplier) + carry;
tmp_result.push_front(tmp % 10);
carry = tmp / 10;
r_multiplicand++;
}
if (carry != 0) {
tmp_result.push_front(carry);
carry = 0;
}
result = sum(result, tmp_result);
deci_cnt++;
tmp_result.clear();
r_multiplier++;
}
return result;
}
deque<int> int_to_deque(unsigned long num) {
deque<int> result;
if (num == 0) {
result.push_front(0);
}
while (num > 0) {
result.push_front(num % 10);
num = num / 10;
}
return result;
}
int main() {
deque<int> num1 = int_to_deque(18446744073709551615ULL);
deque<int> num2 = int_to_deque(18446744073709551615ULL);
deque<int> result = multiply(num1, num2);
print_num(result);
return 0;
}
Output: 340282366920928463426481119284349108225
输出：340282366920928463426481119284349108225
回答by Phil H
Separating out the carrying and the digit multiplication:
分离进位和数字乘法：
def carries(digitlist):
digitlist.reverse()
for idx,digit in enumerate(digitlist):
if digit>9:
newdigit = digit%10
carry = (digit-newdigit)/10
digitlist[idx] = newdigit
if idx+1 > len(digitlist)-1:
digitlist.append(carry)
else:
digitlist[idx+1] += carry
digitlist.reverse()
return True
def multiply(first,second):
digits = [0 for place in range(len(first)+len(second))]
for fid,fdig in enumerate(reversed(first)):
for sid,sdig in enumerate(reversed(second)):
offset = fid+sid
mult = fdig*sdig
digits[offset] += mult
digits.reverse()
carries(digits)
return digits
def prettify(digitlist):
return ''.join(list(`i` for i in digitlist))
Then we can call it:
然后我们可以调用它：
a = [1,2,3,4,7,6,2]
b = [9,8,7,9]
mult = multiply(a,b)
print prettify(a)+"*"+prettify(b)
print "calc:",prettify(mult)
print "real:",int(prettify(a))*int(prettify(b))
Yields:
产量：
1234762*9879 calc: 12198213798 real: 12198213798
Of course the 10s in the carriesfunction and the implicit decimal representation in prettifyare the only thing requiring this to be base 10. Adding an argument could make this base n, so you could switch to base 1000 in order to reduce the numbers of blocks and speed up the calculation.
当然，carries函数中的 10和中的隐式十进制表示prettify是唯一需要以 10 为基数的东西。添加一个参数可以使这个以 n 为基数，因此您可以切换到以 1000 为基数以减少块数和速度上计算。
回答by sasklacz
did it my own way :
以我自己的方式做到了：
int bigger = t1.length;
int smaller = t2.length;
int resultLength = bigger + smaller;
int []resultTemp = new int[resultLength];
int []result = new int[bigger + smaller];
int []temporary = new int[resultLength+1];
int z = resultLength-1;
int zet = z;
int step = 0;
int carry = 0;
int modulo = 0;
for(int i=smaller-1; i>=0; i--){
for(int k = bigger-1; k>= -1; k--){
if(k == -1 && carry != 0 ){
resultTemp[z] = carry;
carry = 0;
break;
}
else if(k == -1 && carry == 0){
resultTemp[z] = 0;
break;
}
resultTemp[z] = carry + t1[k]*t2[i];
carry = 0;
if( resultTemp[z] > 9 ){
modulo = resultTemp[z] % 10;
carry = resultTemp[z]/10;
resultTemp[z] = modulo;
}
else{
resultTemp[z] = resultTemp[z];
}
z--;
}
temporary = add(resultTemp, result);
result = copyArray(temporary);
resultTemp = clear(resultTemp);
z = zet;
step++;
z = z - step;
}
then I check the sign.
然后我检查标志。
回答by Bimal Panigrahi
You can check the below solution which teaches us both multiplication and addition of bigger numbers. Please comment if it can be improved.
您可以查看下面的解决方案，它教我们乘法和加法更大的数字。如果可以改进，请发表评论。
public static void main(String args[]) {
String s1 = "123666666666666666666666666666666666666666666666669999999999999999999999999666666666666666666666666666666666666666666666666666666666666666666";
String s2 = "45688888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
System.out.println(multiply(s1, s2));
}
private static String multiply(String s1, String s2) {
int[] firstArray = convert(s1);
int[] secondArray = convert(s2);
//System.out.println(Arrays.toString(firstArray));
//System.out.println(Arrays.toString(secondArray));
// pass the arrays and get the array which is holding the individual
// rows while we multiply using pen and paper
String[] result = doMultiply(firstArray, secondArray);
//System.out.println(Arrays.toString(result));
// Now we are almost done lets format them as we like
result = format(result);
//System.out.println(Arrays.toString(result));
//Add elements now and we are done
String sum="0";
for(String s:result){
sum=add(sum,s);
}
return sum;
}
private static String[] doMultiply(int[] firstArray, int[] secondArray) {
String[] temp = new String[secondArray.length];
for (int i = secondArray.length - 1; i >= 0; i--) {
int result = 0;
int carry = 0;
int rem = 0;
temp[secondArray.length - 1 - i] = "";
for (int j = firstArray.length - 1; j >= 0; j--) {
result = (secondArray[i] * firstArray[j]) + carry;
carry = result / 10;
rem = result % 10;
temp[secondArray.length - 1 - i] = rem
+ temp[secondArray.length - 1 - i];
}
// if the last carry remains in the last digit
if (carry > 0)
temp[secondArray.length - 1 - i] = carry
+ temp[secondArray.length - 1 - i];
}
return temp;
}
public static int[] convert(String str) {
int[] arr = new int[str.length()];
for (int i = 0; i < str.length(); i++) {
arr[i] = Character.digit(str.charAt(i), 10);
}
return arr;
}
private static String[] format(String[] result) {
for (int i = 0; i < result.length; i++) {
int j = 0;
while (j < i) {
result[i] += "0";
j++;
}
}
return result;
}
public static String add(String num1, String num2) {
//System.out.println("First Number :" + num1);
//System.out.println("Second Number :" + num2);
int max = num1.length() > num2.length() ? num1.length() : num2.length();
int[] numArr1 = new int[max];
int[] numArr2 = new int[max];
for (int i = 0; i < num1.length(); i++) {
numArr1[i] = Integer.parseInt(""
+ num1.charAt(num1.length() - 1 - i));
}
for (int i = 0; i < num2.length(); i++) {
numArr2[i] = Integer.parseInt(""
+ num2.charAt(num2.length() - 1 - i));
}
int carry = 0;
int[] sumArr = new int[max + 1];
for (int k = 0; k < max; k++) {
int tempsum = numArr1[k] + numArr2[k] + carry;
sumArr[k] = tempsum % 10;
carry = 0;
if (tempsum >= 10) {
carry = 1;
}
}
sumArr[max] = carry;
/* System.out.println("Sum :"
+ new StringBuffer(Arrays.toString(sumArr)).reverse()
.toString().replaceAll(",", "").replace("[", "")
.replace("]", "").replace(" ", ""));*/
return new StringBuffer(Arrays.toString(sumArr)).reverse().toString()
.replaceAll(",", "").replace("[", "").replace("]", "")
.replace(" ", "");
}
回答by Thomas Gates
I think this will help you
我想这会帮助你
import java.util.ArrayList;
import java.util.List;
public class Multiply {
static int len;
public static void main(String[] args) {
System.out.println(multiply("123456789012345678901","123456789012345678901");
}
private static ArrayList<Integer> addTheList(List<ArrayList<Integer>> myList) {
ArrayList<Integer> result=new ArrayList<>();
for(int i=0;i<len;i++)
{
result.add(0);
}
int index=0;
for(int i=0;i<myList.size();i++)
{
ArrayList<Integer> a=new ArrayList<>(myList.get(index));
ArrayList<Integer> b=new ArrayList<>(myList.get(index+1));
for (int j = 0; j < a.size()||j < b.size(); i++) {
result.add(a.get(i) + b.get(i));
}
}
return result;
}
private static ArrayList<Integer> multiply(ArrayList<Integer> list1, Integer integer) {
ArrayList<Integer> result=new ArrayList<>();
int prvs=0;
for(int i=0;i<list1.size();i++)
{
int sum=(list1.get(i)*integer)+prvs;
System.out.println(sum);
int r=sum/10;
int m=sum%10;
if(!(r>0))
{
result.add(sum);
}
else
{
result.add(m);
prvs=r;
}
if(!(i==(list1.size()-1)))
{
prvs=0;
}
}
if(!(prvs==0))
{
result.add(prvs);
}
return result;
}
private static ArrayList<Integer> changeToNumber(String str1) {
ArrayList<Integer> list1=new ArrayList<>();
for(int i=0;i<str1.length();i++)
{
list1.add(Character.getNumericValue(str1.charAt(i)));
}
return list1;
}
public static String multiply(String num1, String num2) {
String n1 = new StringBuilder(num1).reverse().toString();
String n2 = new StringBuilder(num2).reverse().toString();
int[] d = new int[num1.length()+num2.length()];
//multiply each digit and sum at the corresponding positions
for(int i=0; i<n1.length(); i++){
for(int j=0; j<n2.length(); j++){
d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');
}
}
StringBuilder sb = new StringBuilder();
//calculate each digit
for(int i=0; i<d.length; i++){
int mod = d[i]%10;
int carry = d[i]/10;
if(i+1<d.length){
d[i+1] += carry;
}
sb.insert(0, mod);
}
//remove front 0's
while(sb.charAt(0) == '0' && sb.length()> 1){
sb.deleteCharAt(0);
}
return sb.toString();
}
}
回答by Danny Roberts
You're going to have to treat each int in the array as a single "digit". Instead of using base 10 where each digit goes from 0 to 9, you'll have to use base 2^32 = 4294967296, where every digit goes from 0 to 4294967295.
您将不得不将数组中的每个 int 视为单个“数字”。不是使用基数 10，其中每个数字从 0 到 9，您必须使用基数 2^32 = 4294967296，其中每个数字从 0 到 4294967295。
I would first implement addition, as your algorithm for multiplication might use addition as an auxiliary.
我将首先实现加法，因为您的乘法算法可能使用加法作为辅助。
回答by rsp
As this is for homework I'll give a few hints.
由于这是家庭作业，我将给出一些提示。
You could approach it the same way you show your example, using strings to hold numbers of any length and implementing:
您可以采用与展示示例相同的方式来处理它，使用字符串来保存任意长度的数字并实现：
- add one number to another
- multiply as your example by appending zeroes and calling the addition method per step (so for multiply with 20, append the "0" and addd that number twice
- 将一个数字加到另一个数字上
- 作为示例，通过附加零并每步调用加法方法（因此对于乘以 20，附加“0”并将该数字相加两次
The addition method you can build by retrieving the char[] from the strings, allocate a result char[] that is 1 longer than the longest and add like you would do on paper from the end back to the start of both arrays.
您可以通过从字符串中检索 char[] 来构建加法方法，分配一个比最长长度长 1 的结果 char[] 并像在纸上一样从末尾添加到两个数组的开头。
The end result will not be the best performing solution, but it it easy to show it is correct and will handle any length numbers (as long they will fit a Java string.)
最终结果不会是性能最好的解决方案，但很容易证明它是正确的，并且可以处理任何长度的数字（只要它们适合 Java 字符串。）
Update
更新
Ok, if you solved adding two numbers, you could:
好的，如果你解决了两个数字相加的问题，你可以：
- implement multiplication by 10
- implement multiplication by repeated addition like in your example
- 实现乘以 10
- 通过重复加法实现乘法，如您的示例
or:
或者：
- implement multiplication by 2 (left shift)
- implement a binary multiplication via the same concept, only this time x 2 and add once
- 实现乘以 2（左移）
- 通过相同的概念实现二进制乘法，只是这次 x 2 并添加一次
to illustrate the latter,
为了说明后者，
13
5 x
----
13 x 1
26 x 0
52 x 1
---- +
65
note that the 1 0 1 are the bits in the number (5) you multiply with and 26 = 13 x 2, 52 = 26 x 2. Your get the idea :-)
请注意，1 0 1 是您乘以的数字 (5) 中的位，26 = 13 x 2, 52 = 26 x 2。您明白了:-)
