2015-03-05 6 views
10

In C++, dire che:Ottenere la parte alta di 64 bit integer moltiplicazione

uint64_t i; 
uint64_t j; 

poi i * j sarà produrre un uint64_t che ha come valore la parte inferiore della moltiplicazione tra i e j, cioè (i * j) mod 2^64. Ora, e se volessi la parte più alta della moltiplicazione? So che esiste un'istruzione di assemblaggio per qualcosa di simile quando si utilizzano numeri interi a 32 bit, ma non ho alcuna familiarità con l'assembly, quindi speravo in un aiuto.

Qual è il modo più efficace per fare qualcosa di simile:

uint64_t k = mulhi(i, j); 
+2

Riferimento: http://blogs.msdn.com/b/oldnewthing/archive/2014/12/08/10578956.aspx –

+0

GCC ha 'uint128_t' per questo scopo. Tuttavia, Visual Studio non ha questa opzione. –

+0

@MooingDuck Sembra che uint128_t non esista sotto il mio ambiente (sto usando Xcode sotto osx). Inoltre, questo calcolerà esplicitamente sia la parte superiore che quella inferiore di quella moltiplicazione, che vorrei evitare. –

risposta

10

Se stai utilizzando gcc e la versione che hai supporta i numeri a 128 bit (prova ad usare __uint128_t) che eseguire il 128 multiplo ed estrarre i 64 bit superiori è probabile che sia il modo più efficiente per ottenere il risultato.

Se il compilatore non supporta i numeri a 128 bit, la risposta di Yakk è corretta. Tuttavia, potrebbe essere troppo breve per il consumo generale. In particolare, un'implementazione effettiva deve fare attenzione a traboccare interi a 64 bit.

La soluzione semplice e portatile che propone è di interrompere ciascuno di aeb in 2 numeri a 32 bit e quindi moltiplicare quei numeri a 32 bit utilizzando l'operazione di moltiplicazione a 64 bit. Se si scrive:

uint64_t a_lo = (uint32_t)a; 
uint64_t a_hi = a >> 32; 
uint64_t b_lo = (uint32_t)b; 
uint64_t b_hi = b >> 32; 

allora è evidente che:

a = (a_hi << 32) + a_lo; 
b = (b_hi << 32) + b_lo; 

e:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo) 
     = ((a_hi * b_hi) << 64) + 
     ((a_hi * b_lo) << 32) + 
     ((b_hi * a_lo) << 32) + 
      a_lo * b_lo 

disponibile il calcolo viene eseguito utilizzando 128 bit (o superiore) aritmetica.

Ma questo problema richiede che eseguiamo tutti i calcoli utilizzando l'aritmetica a 64 bit, quindi dobbiamo preoccuparci dell'overflow.

Poiché a_hi, a_lo, b_hi e b_lo sono tutti numeri a 32 bit senza segno, il loro prodotto si adatta a un numero a 64 bit senza segno di overflow. Tuttavia, i risultati intermedi del calcolo di cui sopra non lo faranno.

Il codice seguente attuerà mulhi (a, b) quando le mathemetics devono essere eseguite modulo 2^64:

uint64_t a_lo = (uint32_t)a; 
uint64_t a_hi = a >> 32; 
uint64_t b_lo = (uint32_t)b; 
uint64_t b_hi = b >> 32; 

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

uint64_t carry_bit = ((uint64_t)(uint32_t)a_x_b_mid + 
         (uint64_t)(uint32_t)b_x_a_mid + 
         (a_x_b_lo >> 32)) >> 32; 

uint64_t multhi = a_x_b_hi + 
        (a_x_b_mid >> 32) + (b_x_a_mid >> 32) + 
        carry_bit; 

return multhi; 

Come Yakk rileva, se non mente essere fuori da +1 a i 64 bit superiori, è possibile omettere il calcolo del bit di carry.

0

lungo moltiplicazione dovrebbero essere le prestazioni ok.

Split a*b in (hia+loa)*(hib+lob). Questo dà 4 moltiplicazioni a 32 bit più alcuni turni. Fateli a 64 bit, e fate i carry manualmente, e otterrete la parte alta.

Si noti che un'approssimazione della parte alta può essere eseguita con un numero inferiore di multipli - con precisione entro 2^33 o così con 1 multiplo, e all'interno di 1 con 3 moltiplica.

Non penso ci sia un'alternativa portatile.

+0

Perché non portatile? Si può anche fare matematica matematica di precisione arbitraria in modo portabile senza alcun assemblaggio. –

+2

@luru, intendo un'alternativa rapida e portatile. Questo è fondamentalmente un bignum con una dimensione massima minuscola. – Yakk