作业：如何写自己的大数字乘法？
在我的项目中，我必须处理在我自己的BigNumber类中作为int[]的大数字（大于java.long）的BigNumber 。 基本上我需要实现这样的事情：
157 x 121 y ---- 157 result1 314 + result2 157 + result3 ------ 18997 finalResult
但是我该如何实现呢？
我想用零（3140,15700）扩展result2,3并添加它们。 但首先，我需要在y的每个数字之间导航并将其乘以x的每个数字。
使用对角线方法。 创建一个数组，并将每个数字乘以每个其他数字并填入每个单元格中的数字。
36 x 92 3 6 +-----+-----+ | 2 / | 5 / | 9 | / | / | | / 7 | / 4 | +-----+-----+ | 0 / | 1 / | 2 | / | / | | / 6 | / 2 | +-----+-----+
在每个对角线上添加数字。 从最低有效位（在右下方）移动到最高位（左上角）。
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)
答案是3312。
制作数字的二维数组。 使用单个数字的乘法填充数组。
写一些逻辑来刮掉对角线，如上所述。
这适用于任意大数（只要你还有内存）。
这是我写的代码。 与手动乘法基本相同。 将两个大数字作为字符串传递给此函数，结果将作为字符串返回。
public String multiply(String num1, String num2){ int product, carry=0, sum=0; String result = new String(""); String partial = new String(""); ArrayList partialList = new ArrayList (); /* 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= 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
我会避免编写自己的头痛，只使用java.math.BigInteger类。 它应该拥有你需要的一切。
分离携带和数字乘法：
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))
然后我们可以称之为：
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))
产量：
1234762 * 9879 计算：12198213798 真实：12198213798
当然，carry函数中的10s和prettify中的隐式十进制表示是唯一要求它作为基数10的东西。添加参数可以使这个基数为n，所以你可以切换到base 1000以减少块的数量并加快计算速度。
您将不得不将数组中的每个int视为单个“数字”。 而不是使用每个数字从0到9的基数10，你将不得不使用base 2 ^ 32 = 4294967296，其中每个数字从0到4294967295。
我会先实现加法，因为你的乘法算法可能会使用加法作为辅助。
由于这是作业，我会给出一些提示。
你可以像显示你的例子一样接近它，使用字符串来保存任意长度的数字并实现：
- 将一个数字添加到另一个
- 通过附加零并且每步调用加法来乘以你的例子（因此，对于乘以20，追加“0”并将该数加两次
您可以通过从字符串中检索char []来构建的添加方法，分配比最长的1更长的结果char []，并添加就像您在纸上从末尾返回到两个数组的开头一样。
最终结果将不是性能最佳的解决方案，但它很容易显示它是正确的并且将处理任何长度数字（只要它们适合Java字符串。）
更新
好的，如果你解决了添加两个数字，你可以：
- 乘以10乘以
- 通过重复添加实现乘法，如您的示例中所示
要么：
- 乘以2乘以（左移）
- 通过相同的概念实现二进制乘法，只有这次x 2并加一次
说明后者，
13 5 x ---- 13 x 1 26 x 0 52 x 1 ---- + 65
请注意，1 0 1是您乘以的数字（5）中的位数，26 = 13 x 2,52 = 26 x 2.您明白了:-)
以我自己的方式做到了：
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; }
然后我检查了标志。
因为这是作业……你确定使用int数组是最好的镜头吗？
我试图在一年前实施类似的研究表现
项目，我们最终使用连接的原语 ..
使用它你可以利用已经存在的东西，并且“只”必须担心两端附近的溢出。当你用<< s（位移左移）和加法实现乘法时，这可能会相当简单。 。
现在，如果你想要一个真正的挑战尝试实现模数…;）
我用C ++实现了这个。 参考这个逻辑……
#include #include using namespace std; void print_num(deque &num) { for(int i=0;i < num.size();i++) { cout< sum(deque &oppA, deque &oppB) { if (oppA.size() == 0) return oppB; if (oppB.size() == 0) return oppA; deque result; unsigned int carry = 0; deque ::reverse_iterator r_oppA = oppA.rbegin(); deque ::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 multiply(deque & multiplicand, deque & multiplier) { unsigned int carry = 0; deque result; int deci_cnt = 0; deque ::reverse_iterator r_multiplier = multiplier.rbegin(); deque tmp_result; while (r_multiplier != multiplier.rend()) { for (int i=0; i::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_to_deque(unsigned long num) { deque result; if (num == 0) { result.push_front(0); } while (num > 0) { result.push_front(num % 10); num = num / 10; } return result; } int main() { deque num1 = int_to_deque(18446744073709551615ULL); deque num2 = int_to_deque(18446744073709551615ULL); deque result = multiply(num1, num2); print_num(result); return 0; }
输出：340282366920928463426481119284349108225
您可以查看以下解决方案，该解决方案教会我们乘法和添加更大的数字。 请评论是否可以改进。
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(" ", ""); }
我想这会对你有所帮助
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 addTheList(List> myList) { ArrayList result=new ArrayList<>(); for(int i=0;i a=new ArrayList<>(myList.get(index)); ArrayList 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 multiply(ArrayList list1, Integer integer) { ArrayList result=new ArrayList<>(); int prvs=0; for(int i=0;i0)) { 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 changeToNumber(String str1) { ArrayList list1=new ArrayList<>(); for(int i=0;i 1){ sb.deleteCharAt(0); } return sb.toString(); } }