Come implementare l'arrotondamento in un linguaggio cumulativo per tutti gli usi utilizzando tipi diversi?

Naviga le tue risposte
1

Dichiarazione di non responsabilità: se non sei terribilmente interessato a numeri e processi matematici, questo probabilmente non è niente per te.

Al momento sono un po 'bloccato in un processo di sviluppo di un progetto privato che ho seguito a lungo e penso di aver bisogno di un input perché non posso decidere come farlo al meglio. Purtroppo devo spiegare un po 'il problema.

EDIT: NON riguarda l'implementazione dell'arrotondamento. Questo è già fatto, sia per il float / doppio che per la precisione arbitraria. Puoi presumere di avere una conoscenza sufficiente numeri, modalità di arrotondamento e problemi in virgola mobile, il problema è come progettare gli operatori di arrotondamento in un programma basato su stack.

Sono interessato al problema della riproducibilità nei calcoli numerici. A causa dell'immenso potere (miliardi di operazioni al secondo) e di alcuni problemi delle lingue utilizzate per il numero crunch (C e FORTRAN), le persone non possono controllare ciò che la macchina sta effettivamente facendo al contrario di ciò che la macchina è presumibilmente facendo (Deteoriation di standard di linguaggio come indifferenza a qNaNs e sNaNs, permette di "ottimizzare" a + (b + c) == (a + b) + c, x86 vs MME a virgola mobile, supporto FMA silenzioso ecc. ecc.) . Questa visione è condivisa da William Kahan, il progettista dell'architettura x86 in virgola mobile.

Quindi ho lavorato su un linguaggio basato su stack come FORTH che consente risultati riproducibili. Hai tipi: aggregati (Vector, Matrix, Tensor) e numeri (complessi, reali). Metti due istanze nello stack, esegui un ADD e ottieni la somma risultante. Se gli spazi erano due galleggianti, ottieni un galleggiante. Se gli spazi erano due doppi, si ottiene un doppio. Se i due spazi erano numeri di precisione arbitrari, si ottiene un numero di precisione arbitrario. Lo stesso con i vettori e le matrici.

Il mio problema dolente è l'arrotondamento. Se escludiamo i razionali esatti, dopo la divisione ogni operazione superiore (operazioni algebriche e trascendentali) richiede l'arrotondamento. Esistono due operazioni di arrotondamento già implementate: arrotondamento , impostazione della posizione esatta dell'arrotondamento (arrotondamento: 2.345 utilizzando 0 = > 2 / 2.345 utilizzando -1 = > 2.3) e < em> arrotondamento cifre significative impostando la lunghezza del risultato (arrotondamento per difetto: 2.345 utilizzando 1 = 2 / 2.345 utilizzando 2 = 2.3).

Gli approcci:

  • Un anello per domarli tutti : solo un'impostazione di arrotondamento per tutti i tipi disponibili. Problema: alcune operazioni sono esatte e dovrebbero essere eseguite come tali; numeri arbitrari di precisione offrono l'aggiunta esatta e la moltiplicazione esatta. Se definisco ad es. ADD_EXACT Includo una parola chiave che non è implementata dalla maggior parte dei tipi di dati e sarà quindi un normale ADD e il pericolo è che io (o altri) dimentichi di usare ADD_EXACT quando necessario. Un altro problema è che è opportuno utilizzare diverse modalità di arrotondamento per alcune operazioni: arrotondamento per l'aggiunta e arrotondamento di cifre significative per la moltiplicazione. Ho paura di inondare il programma con interruttori non necessari per impostare la modalità di arrotondamento.

  • Forse altri anelli .... : diverse modalità di arrotondamento impostabili. Consente l'aggiunta e la moltiplicazione in modo indipendente. Problema: molte più possibilità (impostare e recuperare la modalità di arrotondamento, l'arrotondamento e il parametro di arrotondamento). Quante scelte offro? Solo due e rischiando che se ad es. Le FMA non possono essere supportate o molte di più e rischiano di sopraffare il programma con troppa burocrazia di arrotondamento?

L'arrotondamento è un'operazione cruciale e una volta implementata, non può essere modificata facilmente. Questo deve essere risolto nel miglior modo possibile.

Quello di cui ho bisogno è un modello semplice ed elegante e temo di aver lavorato così a lungo su di esso che semplicemente non lo vedo e / o ho bisogno di un piano per trovare la soluzione giusta. L'aiuto è molto apprezzato e aggiornerò questo post per chiarire alcuni aspetti che potrei aver dimenticato.

EDIT: Prestazioni: non è l'obiettivo di progettazione. Non ti aiuta a ottenere una risposta sbagliata incredibilmente veloce. Non ti aiuta se due programmatori su macchine diverse ottengono un risultato diverso o (anche simile) se nessuno sa qual è la risposta giusta (o che anche entrambi sono sbagliati). L'obiettivo del programma è esattamente questo: scoprire quando la precisione IEEE 754R fallirà e trovare indicatori e metodi per convalidare i risultati numerici. Se sai che la doppia precisione e lo strumento ti porteranno alla soluzione, usa C e FORTRAN.

    
posta Thorsten S. 09.05.2015 - 20:08
fonte

2 risposte

0

A causa del potere inspiegabile di debugging dell'anatra di gomma ora ho una soluzione che trovo migliore di tutti gli altri approcci che ho pensato a.

Implementerò una pila di arrotondamenti. Quando viene inserita una subroutine, l'ultima voce verrà duplicata e inserita come primo elemento nello stack (verrà utilizzata anche se lo stack è stato completamente cancellato). Lo stack è strettamente locale, l'accesso ai valori di arrotondamento delle superroutine non è possibile. Quando la subroutine viene lasciata, la pila verrà cancellata; nessun sopravvissuto.

Lo stack ha le seguenti operazioni: ROUND_DUP (per salvare lo stato originale se necessario), ROUND_PUSH, ROUND_POP, ROUND_CYCLE (vedi più avanti) e le funzioni accessorie per l'arrotondamento corrente.

ROUND_CYCLE passa in rassegna le modalità di arrotondamento. Se nella pila ci sono 3 modalità di arrotondamento, ciò significa la modalità di arrotondamento 1,2,3,1,2,3 ... Se nella pila c'è solo una modalità di arrotondamento, l'istruzione non fa nulla.

Le funzioni di test aumentate sono: EXACT_ADD_SUPPORTED EXACT_MUL_SUPPORTED (Non è consigliabile utilizzare solo IS_ARBITRARY_PRECISION perché è possibile  il sistema potrebbe avere un accumulatore lungo da aggiungere (anche nell'hardware) e non lo è  supporta la moltiplicazione esatta).

Quindi posso scrivere funzioni generali sia per precisione arbitraria che per precisione fissa. 

EXACT_ADD_SUPPORTED  
IF  
  ROUND_PUSH EXACT  
ENDIF

DO
 ....
 ROUND_CYCLE
 ADD
 ROUND_CYCLE
LOOP

Se si tratta di precisione arbitraria, i due valori di arrotondamento vengono commutati e io ho l'aggiunta esatta. Se questa precisione è fissa, rimane e viene utilizzato solo un valore di arrotondamento; ROUND_CYCLE non fa nulla. Quindi posso impostare gli arrotondamenti necessari all'inizio del programma, facilitando la ricerca e la comprensione. Dato che CYCLE esegue solo gli switch, devo pensare prima a come devono essere impostate le modalità di arrotondamento durante l'esecuzione, evitando approcci superflui e non strutturati. Ho solo una modalità di arrotondamento corrente, evitando il sovraccarico.

Se hai miglioramenti e critiche, sii invitato a condividere.

    
risposta data 10.05.2015 - 23:46
fonte
3

Ho un paio di note:

  • Non capisco il tuo problema di ADD_EXACT . Se l'operazione è esatta, non arrotondare. In alternativa, se deve esserci un passaggio di arrotondamento (che include la maggior parte delle operazioni della FPU), non deve introdurre errori.
  • FMA dovrebbe probabilmente essere un'operazione completamente separata sia dall'aggiunta che dalla moltiplicazione, poiché il suo arrotondamento è fondamentalmente diverso: si arrotonda solo una volta. I due arrotondamenti dell'aggiunta di moltiplicazione separata devono essere preveggenti per abbinare l'arrotondamento FMA, indipendentemente dall'esatta strategia di arrotondamento.
  • I termini che usi per parlare di arrotondamenti mi preoccupano. Sembra che tu non sia a conoscenza o in partenza di un punto di virgola mobile e che l'arrotondamento effettivamente vari in IEE-754 e in generale (arrotondato al più vicino, rotondo verso lo zero, rotondo verso l'infinito positivo , ecc.).
  • Sembri inspiegabilmente focalizzato sull'aspetto estetico, ma in gran parte irrilevante, di come nominare la cifra a cui si arrotonda. Nessuna menzione della strategia di arrotondamento attuale (vedi sopra).
  • Dal punto di vista del design, dovrebbe esserci una modalità di arrotondamento predefinita, con l'opzione di utilizzare esplicitamente gli altri. Se fare questa scelta su base operazione per operazione, con un blocco with_rounding mode { ... code ... } con scope lessicale, o con scope dinamiche (vale a dire impostare una variabile globale o thread-local che controlli tutti gli arrotondamenti ovunque) è una domanda molto difficile. Tutte le opzioni hanno gravi inconvenienti e non mi sento qualificato per avere un'opinione in merito.
  • Poni il tuo design come una potenziale alternativa a FORTRAN, C, ecc. per il numero crunch, ma rendere le prestazioni competitive con FPU (occasionalmente imprecise) costruite in silicio è difficilmente impossibile, e non ti sembra preoccupato. sarà che dovrà occuparsi di virgola mobile binario, a larghezza fissa (vale a dire, IEEE-754) e delle idiosincrasie delle sue implementazioni hardware. (La tipizzazione essenzialmente dinamica non aiuta neanche).
risposta data 09.05.2015 - 20:47
fonte

Leggi altre domande sui tag

Il modo migliore per mappare i colori RGB da HTML a LED PHP MVC come accedere all'utente corrente?