Aritmetica punto fisso in programmazione C

Question

Sto cercando di creare un'applicazione che memorizzi i prezzi delle azioni con alta precisione. Attualmente sto usando un doppio per farlo. Per risparmiare sulla memoria posso usare qualsiasi altro tipo di dati? So che questo ha qualcosa a che fare con l'aritmetica in virgola fissa, ma non riesco a capirlo.

Answer 1

L'idea dietro l'aritmetica in virgola fissa è quella di memorizzare i valori moltiplicati per una certa quantità, utilizzare i valori moltiplicati per tutti i calcoli e dividerli dello stesso importo quando si desidera il risultato. Lo scopo di questa tecnica è di utilizzare l'intero aritmetico (int, long ...) pur essendo in grado di rappresentare le frazioni.

Il modo più semplice e più efficiente di farlo in C è l'utilizzo degli operatori di spostamento dei bit (< < e >>).Spostare i bit è un'operazione abbastanza semplice e veloce per l'ALU e fare ciò ha la proprietà di moltiplicare (< <) e dividere (>>) il valore intero di 2 su ogni turno (inoltre, molti turni possono essere fatti esattamente per lo stesso prezzo di uno solo). Naturalmente, lo svantaggio è che il moltiplicatore deve essere un potere di 2 (che di solito non è un problema da solo in quanto non ci interessa davvero quel valore moltiplicatore esatto).

Ora diciamo che vogliamo usare interi a 32 bit per memorizzare i nostri valori. Dobbiamo scegliere una potenza del 2 moltiplicatore. Dividiamo la torta in due, quindi dite 65536 (questo è il caso più comune, ma potete davvero usare qualsiasi potenza di 2 a seconda delle vostre esigenze in modo preciso). Questo è 2 e il 16 qui significa che useremo i 16 bit meno significativi (LSB) per la parte frazionaria. Il resto (32 - 16 = 16) è per i bit più significativi (MSB), la parte intera.

 integer (MSB) fraction (LSB) 
      v     v 
    0000000000000000.0000000000000000 

Mettiamo questo in codice:

#define SHIFT_AMOUNT 16 // 2^16 = 65536 
#define SHIFT_MASK ((1 << SHIFT_AMOUNT) - 1) // 65535 (all LSB set, all MSB clear) 

int price = 500 << SHIFT_AMOUNT; 

Questo è il valore che si deve mettere in deposito (struttura, base di dati, a prescindere). Si noti che int non è necessariamente 32 bit in C anche se oggigiorno è per lo più il caso. Inoltre, senza ulteriori dichiarazioni, è firmato per impostazione predefinita. È possibile aggiungere unsigned alla dichiarazione per essere sicuro. Meglio di così, puoi usare uint32_t o uint_least32_t (dichiarato in stdint.h) se il tuo codice dipende molto dalla dimensione del bit intero (puoi introdurre alcuni hack a riguardo). Nel dubbio, usa un typedef per il tuo tipo di punto fisso e sei più sicuro.

Quando si desidera eseguire il calcolo su questo valore, è possibile utilizzare i 4 operatori di base: +, -, * e /. È necessario tenere presente che quando si aggiunge e si sottrae un valore (+ e -), tale valore deve anche essere spostato. Diciamo che vogliamo aggiungere 10 al nostro prezzo di 500:

price += 10 << SHIFT_AMOUNT; 

Ma per la moltiplicazione e la divisione (* e /), il moltiplicatore/divisore non deve essere spostato. Diciamo che vogliamo moltiplicare per 3:

price *= 3; 

Ora diamo rendere le cose più interessanti dividendo il prezzo da 4 in modo che facciamo per un non-zero parte frazionaria:

price /= 4; // now our price is ((500 + 10) * 3)/4 = 382.5 

Questo è tutto su le regole. Quando si vuole recuperare il prezzo reale in qualsiasi punto, è necessario shift destro:

printf("price integer is %d\n", price >> SHIFT_AMOUNT); 

Se avete bisogno della parte frazionaria, è necessario mascherare fuori:

printf ("price fraction is %d\n", price & SHIFT_MASK); 

Naturalmente, questo valore non è ciò che possiamo chiamare una frazione decimale, infatti è un numero intero nell'intervallo [0 - 65535]. Ma mappa esattamente con l'intervallo di frazione decimale [0 - 0,9999 ...]. In altre parole, la mappatura è simile a: 0 => 0, 32768 => 0,5, 65535 => 0,9999 ...

Un modo semplice per vederlo come una frazione decimale è quella di ricorrere a C galleggiante incorporato aritmetica a questo punto:

printf("price fraction in decimal is %f\n", ((double)(price & SHIFT_MASK)/(1 << SHIFT_AMOUNT))); 

Ma se non si dispone di supporto FPU (hardware o software) , è possibile utilizzare le nuove abilità come questo per prezzo completo:

printf("price is roughly %d.%lld\n", price >> SHIFT_AMOUNT, (long long)(price & SHIFT_MASK) * 100000/(1 << SHIFT_AMOUNT)); 

il numero di 0 di nell'espressione è più o meno il numero di cifre che si desidera dopo il punto decimale. Non sopravvalutare il numero di 0 dato la precisione della frazione (nessuna vera trappola qui, è abbastanza ovvio). Non usare una lunghezza lunga come sizeof (long) può essere uguale a sizeof (int). Utilizzare long long nel caso int sia 32 bit come lungo lungo è garantito per essere minimo di 64 bit (o utilizzare int64_t, int_least64_t e tale, dichiarato in stdint.h). In altre parole, usa un tipo due volte la dimensione del tuo tipo di punto fisso, questo è abbastanza giusto. Infine, se non si ha accesso a> = 64 tipi di bit, forse è il momento di esercitarsi ad emularli, almeno per il proprio output.

Queste sono le idee di base dietro l'aritmetica in virgola fissa.

Fare attenzione ai valori negativi. A volte può diventare complicato, specialmente quando è il momento di mostrare il valore finale. Inoltre, C è definito sull'implementazione degli interi con segno (anche se le piattaforme in cui questo è un problema sono molto rari al giorno d'oggi). Dovresti sempre eseguire test minimi nel tuo ambiente per assicurarti che tutto vada come previsto. Altrimenti, puoi aggirarlo intorno se sai quello che fai (non svilupperò su questo, ma questo ha qualcosa a che fare con lo spostamento aritmetico vs spostamento logico e la rappresentazione del complemento a 2). Con gli interi non firmati, tuttavia, sei per lo più sicuro qualunque cosa tu faccia, dato che i comportamenti sono comunque ben definiti.

fa inoltre notare che se un numero intero di 32 bit non può rappresentare valori più grandi di 2 - 1, con usando aritmetica a virgola fissa con 2 limita l'intervallo da 2 - 1! (e dividere tutto questo per 2 con interi con segno, che nel nostro esempio ci lascerebbero con un intervallo disponibile di 2 - 1). L'obiettivo è quindi scegliere un SHIFT_AMOUNT adatto alla situazione. Questo è un compromesso tra la grandezza della parte intera e la precisione della parte frazionaria.

Ora per i veri avvertimenti: questa tecnica non è assolutamente adatta in aree in cui la precisione è una priorità assoluta (finanziaria, scientifica, militare ...). Solitamente il floating point (float/double) spesso non è abbastanza preciso, anche se hanno proprietà migliori rispetto al fixed-point complessivo. Il punto fisso ha la stessa precisione indipendentemente dal valore (questo può essere un vantaggio in alcuni casi), dove la precisione del float è inversamente proporzionale alla grandezza del valore (cioè minore è la magnitudine, maggiore è la precisione che si ottiene ... beh, questo è più complesso di così, ma ottieni il punto). Anche i float hanno una grandezza molto maggiore degli interi (in numero di bit) equivalenti (a virgola fissa o meno), al costo di una perdita di precisione con valori alti (puoi persino raggiungere un punto di magnitudine dove aggiungere 1 o anche valori maggiori non avranno alcun effetto, qualcosa che non può accadere con gli interi).

Se lavori in quelle aree sensibili, è meglio usare librerie dedicate allo scopo di precisione arbitraria (vai a dare un'occhiata allo gmplib, è gratuito). Nella scienza dell'informatica, essenzialmente, ottenere precisione riguarda il numero di bit utilizzati per memorizzare i valori. Vuoi alta precisione? Usa i bit. È tutto.

Answer 2

Non ti consiglierei di farlo, se il tuo unico scopo è quello di risparmiare memoria. L'errore nel calcolo del prezzo può essere accumulato e stai per rovinarlo.

Se si desidera implementare materiale simile, è sufficiente prendere l'intervallo minimo del prezzo e quindi utilizzare direttamente l'operazione int e integer per manipolare il proprio numero? Devi solo convertirlo al numero in virgola mobile durante la visualizzazione, il che ti semplifica la vita.

Answer 3

Vedo due opzioni per voi. Se lavori nel settore dei servizi finanziari, ci sono probabilmente degli standard che il tuo codice dovrebbe rispettare per precisione e accuratezza, quindi devi solo andare avanti, indipendentemente dal costo della memoria. Capisco che il business è generalmente ben finanziato, quindi pagare più memoria non dovrebbe essere un problema. :)

Se questo è per uso personale, quindi per la massima precisione, ti consiglio di utilizzare numeri interi e moltiplicare tutti i prezzi per un fattore fisso prima della memorizzazione. Ad esempio, se vuoi che le cose siano accurate al centesimo (probabilmente non abbastanza buono), moltiplica tutti i prezzi per 100 in modo che la tua unità sia effettivamente centesima invece di dollari e passi da lì. Se vuoi più precisione, moltiplica di più. Ad esempio, per essere precisi al centesimo di un centesimo (uno standard che ho sentito è comunemente applicato), moltiplicare i prezzi per 10000 (100 * 100).

Ora con numeri interi a 32 bit, moltiplicando per 10000 lascia poco spazio a un grande numero di dollari. Un limite pratico di 32 miliardi di 32 bit significa che possono essere espressi solo prezzi fino a $ 20000: 2000000000/10000 = 20000. Questo peggiora se moltiplichi 20000 per qualcosa, in quanto potrebbe non esserci spazio per contenere il risultato. Per questo motivo, consiglio di utilizzare numeri interi a 64 bit (long long). Anche se moltiplicate tutti i prezzi per 10000, c'è ancora abbastanza spazio per contenere grandi valori, anche attraverso le moltiplicazioni.

Il trucco con punto fisso è che ogni volta che si esegue un calcolo, è necessario ricordare che ogni valore è in realtà un valore sottostante moltiplicato per una costante. Prima di aggiungere o sottrarre, è necessario moltiplicare i valori con una costante più piccola per farli corrispondere a quelli con una costante più grande. Dopo aver moltiplicato, devi dividere per qualcosa per ottenere il risultato di essere moltiplicato per la costante desiderata. Se usi una non potenza di due come costante, dovrai eseguire una divisione intera, che è costosa, in termini di tempo. Molte persone usano i poteri di due come loro costanti, in modo che possano spostarsi invece di dividere.

Se tutto ciò sembra complicato, lo è. Penso che l'opzione più semplice sia usare il doppio e comprare più RAM se ne hai bisogno. Hanno 53 bit di precisione, ovvero circa 9 quadrilioni o quasi 16 cifre decimali. Sì, potresti comunque perdere soldi quando lavori con miliardi, ma se ti interessa, non sei miliardario nel modo giusto. :)