алгоритм — Умножение 2 64-значных чисел в переполнении стека

Question

алгоритм — Умножение 2 64-значных чисел в переполнении стека

У меня реализован алгоритм умножения Карацубы. Я хочу улучшить его таким образом, чтобы я мог умножить 2 64-значных числа, но я не знаю, как это сделать. Мне дали подсказку, что оба числа содержат количество цифр, которое является степенью двойки, но это ничего не говорит мне. Не могли бы вы дать какие-нибудь другие советы? Либо подсказка по математике, либо подсказка по улучшению алгоритма.

#include <iostream>
#include <math.h>
using namespace std;

int getLength(long long value);
long long multiply(long long x, long long y);

int getLength(long long value)
{
int counter = 0;
while (value != 0)
{
counter++;
value /= 10;
}
return counter;
}

long long multiply(long long x, long long y)
{
int xLength = getLength(x);
int yLength = getLength(y);

// the bigger of the two lengths
int N = (int)(fmax(xLength, yLength));

// if the max length is small it's faster to just flat out multiply the two nums
if (N < 10)
return x * y;

//max length divided and rounded up
N = (N / 2) + (N % 2);

long long multiplier = pow(10, N);

long long b = x / multiplier;
long long a = x - (b * multiplier);
long long d = y / multiplier;
long long c = y - (d * N);

long long z0 = multiply(a, c);
long long z1 = multiply(a + b, c + d);
long long z2 = multiply(b, d);return z0 + ((z1 - z0 - z2) * multiplier) + (z2 * (long long)(pow(10, 2 * N)));

}

int main()
{
long long a;
long long b;
cin >> a;
cout << '\n';
cin >> b;
cout << '\n' << multiply(a, b) << endl;
return 0;
}

2

algorithm c++karatsuba math

Решение

Другие решения

Чтобы применить Карацубу или любое другое умножение к арифметике с меньшей битовой шириной, вам нужно разделить свое число на более мелкие «цифры». Прежде всего, вам нужно получить доступ к этим «цифрам», вот как это сделать:

у тебя есть номер 1234 и хочу разделить его на 10^1 цифры так

1234 = 1*1000 + 2*100 + 3*10 + 4

Вы можете получить цифры, как это:

x=1234;
a0=x%10; x/=10; // 4
a1=x%10; x/=10; // 3
a2=x%10; x/=10; // 2
a3=x%10; x/=10; // 1

если ты хочешь 10^2 цифры тогда:

x=1234;
a0=x%100; x/=100; // 34
a1=x%100; x/=100; // 12

Теперь проблема в том, что для этого вам нужно иметь деление на полный номер, которого у вас нет. Если вы получили число в виде строки, то это легко сделать, но предположим, что нет. Компьютеры основаны на двоичных вычислениях, поэтому рекомендуется использовать степень 2 в качестве базы для «цифр», поэтому:

x = 1234 = 0100 1101 0010 bin

Теперь, если мы хотим иметь, например, 2^4=16 базовые цифры тогда:

a0=x%16; x/=16; // 0010
a1=x%16; x/=16; // 1101
a2=x%16; x/=16; // 0100

Теперь, если вы понимаете, что деление на степень 2 — это просто сдвиг бит вправо, а остаток можно выразить как AND, тогда:

a0=x&15; x>>=4; // 0010
a1=x&15; x>>=4; // 1101
a2=x&15; x>>=4; // 0100

Сдвиг битов может быть наложен на любые битовые числа, так что теперь вы получили все, что вам нужно. Но это еще не все, если вы выберите, например, «цифра» 2^8 который BYTE вместо этого вы можете использовать указатели, например:

DWORD x=0x12345678; // 32 bit number
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x

a0=db[0]; // 0x78
a1=db[1]; // 0x56
a2=db[2]; // 0x34
a3=db[3]; // 0x12

так что вы можете напрямую получить доступ к цифрам или восстановить x из цифр:

DWORD x; // 32 bit number
BYTE *db=(BYTE*)(&x); // 8bit pointer that points to x
db[0]=0x78;
db[1]=0x56;
db[2]=0x34;
db[3]=0x12;
// here x should be 0x12345678

Помните, что порядок зависит от платформы MSB или LSB первого порядка. Теперь вы можете применять умножение. Например, 32 * 32 = 64-битное, 16-битное умножение выполняется так же, как наивный. O(n^2) подход:

x(a0+a1<<16) * y(b0+b1<<16) = a0*b0 + a0*b1<<16 + a1*b0<<16 + a1*b1<<32

Где a0, a1, b0, b1 — цифры операндов. Обратите внимание, что результат каждого ai*bj умножение имеет ширину 2 цифры, поэтому вам нужно разбить его на цифры и сохранить в результирующую цифру с учетом сдвига битов. Помните, что добавление может вызвать переполнение до старшего разряда. Чтобы справиться с этим, вам нужно либо использовать как минимум удвоенную ширину арифметики для сложения (16 * 16 бит, муль -> 32 бит) или использовать флаг переноса. К сожалению, кроме использования ассемблера в C ++, у вас нет доступа к флагу Carry. к счастью, это может быть смоделировано увидеть:

Не могу сделать ценность распространяться через нести

И теперь вы можете построить свой Карацуба или более сложные умножения для получения дополнительной информации смотрите:

Быстрое вычисление квадрата

1

Источник

Accepted Answer

Вот подсказка:

(A + kB) * (C + kD) = AC + k(BC + AD) + k^2(BD)

Это помогает, если k это сила базы, в которой вы храните свои номера. Например, если k равен 1’000’000’000, а ваши числа основаны на 10, то умножение на k выполняются простым смещением чисел вокруг (добавление нулей).

В любом случае, рассмотрите возможность разбить свои 64-значные числа на две части, каждая из которых состоит из 32 цифр, и выполните математику, как описано выше. Вычислять AC, BC, AD, а также BD Вы умножаете пару 32-значных чисел, что можно сделать аналогично.

Поскольку количество ваших цифр является степенью двойки, вы можете разбивать свои числа пополам до тех пор, пока не доберетесь до размеров, которыми можно управлять (например, однозначные числа).

Кстати, из вашего вопроса не ясно, говорите ли вы о 64 битах или 64 десятичных цифрах. Если вам нужно только умножить 64-битные числа, просто сделайте это:

// I haven't actually run this code, so...

typedef unsigned long long u64;

u64 high32 (u64 x) {return x >> 32;}
u64 low32  (u64 x) {return x & 0xFFFFFFFF;}

u64 add_with_carry (u64 a, u64 b, u64 * carry)
{
u64 result = a + b;
if (result < a) // and/or b?
*carry = 1;
return result;
}

void mul (u64 a, u64 b, u64 * result_low, u64 * result_high)
{
u64 a0 = low32(a), a1 = high32(a);
u64 b0 = low32(b), b1 = high32(b);

u64 a0b0 = a0 * b0;
u64 a0b1 = a0 * b1;
u64 a1b0 = a1 * b0;
u64 a1b1 = a1 * b1;

u64 c0 = 0, c1 = 0;
u64 mid_part = add_with_carry(a0b1, a1b0, &c1);

*result_low  = add_with_carry(a0b0, (low32(mid_part) << 32, &c0);
*result_high = high32(mid_part) + a1b1 + (c1 << 32) + c0; // this won't overflow
}

Эта реализация является той же идеей, изложенной выше. Поскольку в стандарте C / C ++ наибольшее количество значащих битов, которые мы можем иметь в результате умножения, равно 64, то мы можем умножать только два 32-разрядных числа за раз. Что мы и делаем здесь.

Окончательный результат будет 128 бит, который мы возвращаем в двух беззнаковых 64-битных числах. Мы делаем 64-битное 64-битное умножение, выполняя 4 32-битных умножения и несколько добавлений.

В качестве дополнительного примечания, это один из тех немногих случаев, когда написание этой сборки обычно намного проще, чем C. Например, в сборке x64 это буквально два movс, четыре mulс, четыре addс и четыре adcs (и это только с помощью основных инструкций процессора.)

4