Домашнее задание: как написать собственное умножение больших чисел?
В моем проекте мне приходится иметь дело с умножением больших чисел (больше java.long), которые смотрели в моем собственном классе BigNumber
как int[]
. В основном мне нужно реализовать что-то вроде этого:
157 x
121 y
----
157 result1
314 + result2
157 + result3
------
18997 finalResult
Но как его реализовать?
Я думал о расширении результата2,3 с нулями (3140, 15700) и добавлением их. Но сначала мне как-то нужно перемещаться между каждой цифрой y и умножать ее на каждую цифру x.
Ответы
Ответ 1
Используйте диагональный подход. Создайте массив и умножьте каждую цифру на цифру друг друга и заполните цифры в каждой ячейке.
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.
Сделайте двумерный массив ваших цифр. Заполните массив с умножением отдельных цифр вместе.
Напишите некоторую логику, чтобы очистить диагонали, как я сделал выше.
Это должно работать для сколь угодно больших чисел (пока у вас все еще остается память).
Ответ 2
Вот код, который я написал. В принципе, такое же, как ручное умножение. Передайте два больших числа в виде строк этой функции, результат возвращается как строка.
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;
}
Ответ 3
Я бы избегал головных болей писать свои собственные и просто использовал класс java.math.BigInteger. Он должен иметь все, что вам нужно.
Ответ 4
Разделите перенос и умножение цифр:
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
calc: 12198213798
real: 12198213798
Конечно, 10s в функции carries
и неявное десятичное представление в prettify
- единственное, что требует, чтобы это было основанием 10. Добавление аргумента могло бы сделать эту базу n, поэтому вы могли бы переключиться на базу 1000 в чтобы уменьшить количество блоков и ускорить расчет.
Ответ 5
Вам придется обрабатывать каждый int в массиве как одну "цифру". Вместо того, чтобы использовать базу 10, где каждая цифра идет от 0 до 9, вам придется использовать базу 2 ^ 32 = 4294967296, где каждая цифра идет от 0 до 4294967295.
Сначала я бы добавил дополнение, так как ваш алгоритм умножения мог бы использовать добавление в качестве вспомогательного.
Ответ 6
Как это для домашней работы, я дам несколько советов.
Вы можете приблизиться к нему так же, как вы показываете свой пример, используя строки для хранения чисел любой длины и реализации:
- добавить один номер в другой
- умножьте свой пример, добавив нули и вызывая метод добавления за шаг (поэтому для умножения с 20 добавьте "0" и добавьте этот номер дважды
Метод добавления, который вы можете построить, извлекая char [] из строк, выделите результат char [], который на 1 длиннее самого длинного и добавит, как вы делали бы на бумаге от конца до начало обоих массивов.
Конечный результат не будет лучшим решением, но его легко показать, что оно корректно и будет обрабатывать любые номера длин (до тех пор, пока они будут соответствовать строке 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. У вас есть идея: -)
Ответ 7
Так как это домашнее задание... Вы уверены, что использовать массив int - ваш лучший снимок?
Я попытался реализовать что-то подобное год назад для работы в исследовании
проект, и мы закончили с конкатенированными примитивами.
Используя это, вы можете воспользоваться тем, что уже существует, и "только" нужно беспокоиться о переполнениях в конце. Это может оказаться довольно простым, когда вы реализуете свое умножение с < (бит сдвига слева) и добавления..
Теперь, если вам нужен реальный вызов попытаться реализовать modulo...;)
Ответ 8
сделал это по-своему:
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;
}
то я проверяю знак.
Ответ 9
Я реализовал это на С++. обратитесь к этому для логики...
#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;
}
Выход: 340282366920928463426481119284349108225
Ответ 10
Вы можете проверить приведенное ниже решение, которое учит нас как умножению, так и добавлению больших чисел. Пожалуйста, прокомментируйте, если это можно улучшить.
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(" ", "");
}
Ответ 11
Я думаю, это поможет вам
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();
}
}