Умножение 2 64-значных чисел в C++

Question

У меня реализован алгоритм умножения karatsuba. Я хочу улучшить его таким образом, чтобы я мог умножить 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; 
} 

Answer 1

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

(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-значных чисел, которые могут быть выполнены аналогичным образом.

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

Кстати, это не ясно из ваш вопрос, говорите ли вы о 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-битных умножения и несколько добавлений.

Как примечание стороны, это один из тех немногих случаев, когда пишешь это сборка, как правило, легче, чем waaaaay C. Например, в сборке x64, это буквально два mov s, четыре mul s, четыре add с, и четыре adc s (и это просто использует основные инструкции процессора.)

Answer 2

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

вы получили номер 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 только немного сдвинуть вправо и остаток может быть выражен как и затем:

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 

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

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 бит mul -> 32bit add), либо использовать флаг переноса. К сожалению, с помощью сборки на C++ у вас нет доступа к флагом Carry. к счастью, он может быть смоделирован см:

• Cant make value propagate through carry

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

• Fast bignum square computation