Quale algoritmo dovrei usare per una divisione intera di grandi prestazioni?

Question

Sto codificando i grandi numeri interi in una matrice di size_t. Ho già le altre operazioni in funzione (aggiungi, sottrarre, moltiplicare); così come la divisione di una singola cifra. Ma mi piacerebbe abbinare la complessità temporale dei miei algoritmi di moltiplicazione se possibile (attualmente Toom-Cook).

Ho notato che ci sono algoritmi di tempo lineare per prendere varie nozioni di inversione moltiplicativa del mio dividendo. Ciò significa che potrei teoricamente ottenere una divisione nella stessa complessità temporale della mia moltiplicazione, perché l'operazione lineare-temporale è comunque "insignificante" al confronto.

La mia domanda è, come faccio a farlo? Che tipo di inversione moltiplicativa è la migliore nella pratica? Modulo 64^digitcount? Quando moltiplico l'inversione moltiplicativa del mio divisore, posso sottrarre il calcolo della parte dei dati che verrebbe buttata via a causa del troncamento di interi? Qualcuno può fornire uno pseudocodice C o C++ o fornire una spiegazione precisa di come dovrebbe essere fatto?

Oppure esiste un algoritmo di divisione dedicato che è persino migliore rispetto all'approccio basato su inverso?

Modifica: ho individuato l'approccio "inverso" sopra menzionato. Nella pagina 312 di "Art of Computer Programming, Volume 2: Algoritmi seminali", Knuth fornisce "Algorithm R" che è un reciproco ad alta precisione. Dice che la sua complessità temporale è inferiore a quella della moltiplicazione. Tuttavia, non è banale convertirlo in C e testarlo, e non è chiaro quanta memoria di overhead, ecc., Sarà consumata fino a quando non la codifico, il che richiederebbe un po 'di tempo. Lo posterò se nessuno mi picchia.

Answer 1

La libreria GMP è in genere un buon riferimento per i buoni algoritmi. Il loro numero documented algorithms for division dipende principalmente dalla scelta di una base molto ampia, in modo tale da dividere un numero a 4 cifre da un numero a 2 cifre, e quindi procedere per una lunga divisione.

La divisione lunga richiede il calcolo dei quozienti di 2 cifre per 1 cifra; questo può essere fatto in modo ricorsivo o precomputing di un inverso e stimando il quoziente come faresti con la riduzione di Barrett.

Quando dividendo un bit numero 2n da un n bit numero, i costi ricorsive versione O(M(n) log(n)), dove M(n) è il costo di moltiplicare n numeri -bit.

La versione con riduzione Barrett vi costerà O(M(n)) se si utilizza l'algoritmo di Newton per calcolare l'inverso, ma secondo la documentazione del GMP, la costante nascosta è molto più grande, quindi questo metodo è preferibile solo per i grandi divisioni.

---

Più in particolare, l'algoritmo di base dietro molti algoritmi di divisione è un "quoziente stimato con riduzione" calcolo, calcolare (q,r) modo che

x = qy + r 

ma senza la restrizione che 0 <= r < y.Il ciclo tipico è

• Stima il quoziente q di x/y
• Calcolare la riduzione corrispondente r = x - qy
• Facoltativamente regolare il quoziente in modo che la riduzione r è in qualche intervallo desiderato
• Se r è troppo grande, quindi ripetere con r al posto di x.

Il quoziente di x/y sarà la somma di tutti i prodotti q s, e il valore finale di r sarà il vero rimanente.

Schoolbook long division, ad esempio, è di questa forma. per esempio. il passaggio 3 copre quei casi in cui la cifra indovinata era troppo grande o troppo piccola e la si regola per ottenere il valore corretto.

Il divide et impera metodo stima il quoziente di x/y calcolando x'/y' dove x' e y' sono le cifre iniziali di x e y. C'è un sacco di spazio per l'ottimizzazione regolando le loro dimensioni, ma IIRC si ottiene risultati migliori se x' è il doppio delle cifre di y'.

L'approccio di moltiplicazione per inversa è, IMO, il più semplice se si configura l'aritmetica dei numeri interi. Il metodo di base è

• Stima l'inverso di y con m = floor(2^k/y)
• Stima x/y con q = 2^(i+j-k) floor(floor(x/2^i) m/2^j)

Infatti, implementazioni pratiche può tollerare ulteriori errori in m se significa che è possibile utilizzare una più veloce reciproca implementazione.

l'errore è un dolore da analizzare, ma se mi ricordo il modo per farlo, si desidera scegliere i e j in modo che x ~ 2^(i+j) a causa di come gli errori si accumulano, e si desidera scegliere x/2^i ~ m^2 per ridurre al minimo il lavoro complessivo.

La conseguente riduzione avrà r ~ max(x/m, y), in modo che dà una regola empirica per la scelta k: si desidera che la dimensione del m essere circa il numero di bit di quoziente di calcolare per ogni iterazione — o equivalentemente il numero di bit che si desidera rimuovere da x per iterazione.

Answer 2

Non conosco l'algoritmo inverso moltiplicativo ma suona come modifica di Montgomery Reduction o Barrett's Reduction.

Io divido le divisioni un po 'diversamente.

Vedere bignum division. Soprattutto dare un'occhiata al divisore di approssimazione e ai 2 link lì. Uno è il mio divisore a punti fissi e gli altri sono algos di moltiplicazione veloci (come karatsuba, Schönhage-Strassen su NTT) con misure e un collegamento alla mia implementazione NTT molto veloce per base a 32 bit.

Non sono sicuro se il moltiplicatore inverso è la via.

Viene utilizzato principalmente per l'operazione modulo in cui il divisore è costante. Temo che per le divisioni arbitrarie il tempo e le operazioni necessarie per acquisire il bigint inverso possano essere maggiori delle stesse divisioni standard, ma poiché non ho familiarità con esso potrei sbagliarmi.

Il divisore più comune in uso che ho visto nelle implementazioni è la divisione di Newton-Raphson che è molto simile al separatore di approssimazione nel link sopra.

I separatori di approssimazione/iterativi di solito utilizzano la moltiplicazione che definisce la loro velocità.

Per i numeri abbastanza piccolo è di solito lunga divisione binaria e 32/64bit divisione base di cifre abbastanza veloce se non più veloce: di solito hanno piccole spese generali, e lasciare che n essere il valore massimo elaborato

(non il numero di cifre!)

Binary esempio divisione:

Is O(log32(n).log2(n)) = O(log^2(n)).
Attraversa tutti i bit significativi. In ogni iterazione è necessario compare, sub, add, bitshift. Ciascuna di queste operazioni può essere eseguita in log32(n) e log2(n) è il numero di bit.

Ecco esempio di divisione binaria da uno dei miei modelli bigint (C++):

template <DWORD N> void uint<N>::div(uint &c,uint &d,uint a,uint b) 
    { 
    int i,j,sh; 
    sh=0; c=DWORD(0); d=1; 
    sh=a.bits()-b.bits(); 
    if (sh<0) sh=0; else { b<<=sh; d<<=sh; } 
    for (;;) 
     { 
     j=geq(a,b); 
     if (j) 
      { 
      c+=d; 
      sub(a,a,b); 
      if (j==2) break; 
      } 
     if (!sh) break; 
     b>>=1; d>>=1; sh--; 
     } 
    d=a; 
    } 

N è il numero di 32 bit DWORD s utilizzati per memorizzare un numero bigint.

• c = a/b
• d = a % b
• qeq(a,b) è un confronto: a >= b maggiore o uguale (fatto in log32(n)=N)
  Restituisce 0 per a < b, 1 per a > b, 2 per a == b
• sub(c,a,b) è c = a - b

L'incremento di velocità è maturata che questo non fa uso di moltiplicazione (se non si conta il turno di bit)

Se si utilizza cifre con una grande base come 2^32 (blocchi ALU), allora si può riscrivere l'intero in stile polinomiale usando la compilazione a 32 bit nelle operazioni ALU.
Questo è in genere ancora più veloce della divisione lunga binaria, l'idea è di elaborare ogni DWORD come una singola cifra, o dividere in modo ricorsivo l'aritmetica utilizzata della metà fino a raggiungere le capacità della CPU.
Vedere division by half-bitwidth arithmetics

In cima a tutto ciò che durante il calcolo con bignum

Se avete ottimizzato le operazioni di base, quindi la complessità può abbassare ancora di più come sub-risultati diventano più piccoli con iterazioni (cambiando la complessità delle operazioni di base Un buon esempio di ciò sono le moltiplicazioni basate su NTT.

Il sovraccarico può rovinare tutto.

A causa di questo il tempo di esecuzione a volte non copia la complessità O grande, quindi è sempre necessario misurare le tenute e utilizzare un approccio più rapido per il conteggio dei bit utilizzato per ottenere le massime prestazioni e ottimizzare ciò che è possibile.