Mnożenie dwóch liczb 128-bitowych w celu uzyskania 256-bitowego wyniku

Chcę pomnożyć dwie liczby 128-bitowe. Robię to tak:

__int128 a = (11400714819323198485 << 64) | 17554116967691831348;
__int128 b = (11400714819323198485 << 64) | 17554116967691831348;

__int128 wynik;

__int128 multhi(__int128 a, __int128 b)
{
    __int128 a_lo = (uint64_t)a;
    __int128 a_hi = a >> 64;
    __int128 b_lo = (uint64_t)b;
    __int128 b_hi = b >> 64;

    __int128 a_x_b_hi = a_hi * b_hi; 
    __int128 a_x_b_mid = a_hi * b_lo;
    __int128 b_x_a_mid = b_hi * a_lo;
    __int128 a_x_b_lo = a_lo * b_lo;

    __int128 carry_bit = ((__int128)(uint64_t)a_x_b_mid + (__int128)(uint64_t)b_x_a_mid + (a_x_b_lo >> 64)) >> 64;

    __int128 multhi = a_x_b_hi + (a_x_b_mid >> 64) + (b_x_a_mid >> 64) + carry_bit;

    return multhi;
}

int main()
{
    wynik = multhi(a,b);
    uint64_t Hi = a >> 64;
    uint64_t Lo = (uint64_t)a;
    std::cout << Hi << " " << Lo << "\n";
}

Ale wynik jest błędny. Dolne bity mnożą się właściwie i można je uzyskać poprzez pomnożenie a*b. Ale chodzi o wyższe 128-bitów. Cały wynik to: 44228642460293897567044858665937249460741554819946588830554614791049552939664, zaś górne 128 bitów to 129976298391535590297638237547755878347.

Nie rozumiem dlaczego wynik jest niewłaściwy, bo, gdy zmienimy zmienne na 64-bitowe, razem z przesunięciami (tak, jakbyśmy zakładali, że nie mamy do dyspozycji intów 128-bitowych), to funkcja działa prawidłowo. Więc ta sama funkcja dla intów 64-bitowych daje poprawne wyniki. Na czym polega problem?

Nie wiem, czy na tym skorzystasz, ale swego czasu napisałem program wykonujący działania na dowolnie dużych liczbach na mikrokontrolery:
link

Definicja stałych
Elementarne działania
Cztery podstawowe działania
Popatrz na pozostałe pliku.

A cały ScriptSDCC to jest symulator 8051 i Z80, w których można uruchomić również ten program. Myślę, że też nie powinno być dużym problemem przerobić to na zwykły program w C na komputer. Operacje IO masz w tym pliku, to są funkcje zaczynające nazwę od "console_print" i "console_input", taże usunąć załączanie plików "core.h" i "console.h", te dwa pliki nie są potrzebne do samego działania algorytmów kalkulatora, tylko właśnie do IO.

W skrócie, każda liczba jest reprezentowana przez tablicę liczb, w stałych jest określony tym elementu, wielkość jednego elementu i wielkość tablicy.

Myślę, że to się da wykorzystać do tego, do czego potrzebujesz. Możesz też popatrzeć na zasadę, jak to jest zrobione i zaimplementować mój pomysł po swojemu.

To, co będziesz potrzebować to jest numByte _numMul(numPtr(N1), numPtr(N2), numPtr(N3), numByte Dec, numPtr(N3Ext)) w tym pliku . Pozostałe pliki będą potrzebne, żeby zobaczyć, co jest czym (definicje typów, zmiennych, stałych, funkcje pomocnicze).

Natomiast typy uchar, schar wynikają z fragmentu tego pliku:

#define uchar unsigned char
#define schar signed char
#define uint unsigned int
#define sint signed int
#define ulong unsigned long
#define slong signed long
#define ushort unsigned short
#define sshort signed short
#define llong long long
#define ullong unsigned long long
#define sllong signed long long

__int128

ponieważ jest to typ ze znakiem, to może robiąc różne operacje wpadasz gdzieś w liczbę ujemną niechcący i stąd rozbieżność wyników?

Ale tak tylko zgaduję.

Mnożenie dwóch liczb 128-bitowych w celu uzyskania 256-bitowego wyniku

__int128 multiply(__int128 a, __int128 b)

Zwracany typ funkcji sprzeczny z założeniem. Dalej można nie czytać.

Funkcja ma zwracać górne 128 bitów. Dolne można uzyskać poprzez zwyczajne pomnożenie a*b.