Come determinare in anticipo se un calcolo senza segno può eventualmente traboccare?

Come progetto personale sto lavorando all'implementazione di un tipo di numero di precisione arbitraria per un mio progetto per animali domestici.Come determinare in anticipo se un calcolo senza segno può eventualmente traboccare?

Conosco già tutte le librerie popolari, testate e robuste che fanno questo. Voglio lavorare su una soluzione come progetto di educazione autoformativa.

Sto studiando la zona e cercando di capire se c'è qualche modo per circa prevedere se un'operazione provocherà un overflow prima che io in realtà fare i calcoli. Nemmeno io sono così preoccupato per i falsi positivi.

Desidero poter utilizzare lo spazio più piccolo adatto al calcolo. Se il calcolo rimarrà entro i limiti nativi, lo terrò lì.

Ad esempio: Multiplying two 64 bit Integers if each are large enough will cause an overflow. Voglio rilevare questo e up-convertire i numeri per il mio tipo di numero solo se il risultato può superare 64 bit di risoluzione. In questo esperimento lavorerò con i numeri firmati.

Qual è il modo più corretto ed efficace per rilevare un overflow/underflow?

fonte

2011-11-08 Jarrod Roberson

Non ha mai provato un progetto simile, quindi ha solo le domande: qual è il punto in cui si conosce l'overflow in anticipo? Ottimizzazione per i piccoli nmbers per essere veloci, o qualcosa di meno ovvio? Hai bisogno di una soluzione esatta, o accettarne una che potrebbe dare falsi allarmi di overflow? – vmatyi

La tua domanda e il tuo commento in risposta a una delle risposte dicono che stai usando gli operandi firmati, ma il titolo dice non firmato. Cos'è questo?L'aritmetica senza segno è probabilmente più facile da gestire ed è probabilmente più adatta per lavorare con numeri arbitrari di precisione. –

Effettuerò i calcoli arbitrari firmati utilizzando i tipi primitivi non firmati come componenti di base, come in una matrice di bit senza segno a 64 bit che rappresentano la base –

prende solo il più alto bit in entrambi i numeri, sinistra shift per uno, se il risultato (ad esempio: moltiplicazione) di quei numeri causerebbe un overflow, si ha una buona possibilità per un overflow.

Anche se non è preciso, è incredibilmente veloce e un buon indicatore del fatto che è necessario un tipo di dati più grande per il risultato.

Questo potrebbe aver senso solo per i grandi tipi di dati per i quali l'operatore è costosa, per le cose semplici (anche per i numeri a 64 bit), penso che si può fare affidamento su aritmetica integrato del CPU .. vedi questa domanda: Undefined behavior when exceed 64 bits

fonte

2011-11-08 23:32:20

Perché spostare a sinistra di 1? –

Perché è così che potresti causare un overflow. Se ciò si verifica effettivamente, significa che uno dei tuoi numeri è già grande. –

A proposito c'è il numero paper di John Regehr.

fonte

2011-11-08 23:37:40

È quasi sempre più semplice (e spesso più veloce) eseguire l'ingenuo calcolo e rilevare se si è verificato un overflow. C'è un motivo specifico per cui vorresti rilevare la possibilità prima del facendo il calcolo?

È generalmente abbastanza facile rilevare se si è verificato un overflow una volta terminato il calcolo. Poiché le operazioni ingenue sono economiche, questo non aggiunge molto al costo del calcolo se si verifica un overflow, anche se si finisce per dover ripetere un lavoro. (Di solito, comunque, non avrai nemmeno bisogno di farlo).

Ecco un esempio (molto) semplice: se aggiungo due numeri a 64 bit senza segno, è possibile verificare l'overflow confrontando la somma con uno degli addendi, se è inferiore, si è verificato un overflow. Quindi, rilevare l'overflow dopo il calcolo richiede solo un singolo confronto (davvero molto economico).

fonte

2011-11-08 23:42:22

L'esempio è vero solo nel caso di operandi senza segno, non è valido nel caso generale. –

E il comportamento di overflow con segno non è definito. –

@Keith: per i tipi primitivi, ovviamente. L'OP sta parlando dell'implementazione di un tipo di precisione arbitraria. Deve essere in grado di gestire l'overflow per far crescere la rappresentazione (e quindi prevenire l'overflow!). –

Come determinare in anticipo se un calcolo senza segno può eventualmente traboccare?

risposta

Problemi correlati