Algoritmo per trovare un moltiplicatore comune per convertire i numeri decimali in numeri interi

https://stackoverflow.com/questions/58493

09-06-2019
|

Domanda

Ho una serie di numeri che potenzialmente hanno fino a 8 cifre decimali e devo trovare il numero comune più piccolo per cui posso moltiplicarli in modo che siano tutti numeri interi.Ne ho bisogno in modo che tutti i numeri originali possano essere moltiplicati sulla stessa scala ed essere elaborati da un sistema sigillato che tratterà solo numeri interi, quindi posso recuperare i risultati e dividerli per il moltiplicatore comune per ottenere i miei risultati relativi .

Attualmente eseguiamo alcuni controlli sui numeri e moltiplichiamo per 100 o 1.000.000, ma l'elaborazione eseguita dal sistema *sealed può diventare piuttosto costosa quando si ha a che fare con numeri grandi, quindi moltiplicare tutto per un milione solo per il gusto di farlo non è proprio un'ottima opzione.Per approssimazione, diciamo che l'algoritmo sigillato diventa 10 volte più costoso ogni volta che si moltiplica per un fattore 10.

Qual è l'algoritmo più efficiente, che fornirà anche il miglior risultato possibile, per realizzare ciò di cui ho bisogno ed esiste un nome matematico e/o una formula per ciò di cui ho bisogno?

*Il sistema sigillato non è realmente sigillato.Possiedo/mantengo il codice sorgente, ma contiene 100.000 righe dispari di magia proprietaria ed è stato accuratamente testato su bug e prestazioni, alterarlo per gestire i float non è un'opzione per molte ragioni.È un sistema che crea una griglia di celle X per Y, poi i retti che sono X per Y vengono inseriti nella griglia, avviene la "magia proprietaria" e i risultati vengono emessi - ovviamente questa è una versione estremamente semplificata della realtà, ma è un'approssimazione sufficientemente buona.

Finora ci sono alcune buone risposte e mi sono chiesto come dovrei fare per scegliere quella “corretta”.All’inizio ho pensato che l’unico modo giusto fosse creare ogni soluzione e testarla in termini di prestazioni, ma in seguito mi sono reso conto che la velocità pura non era l’unico fattore rilevante: anche una soluzione più accurata è molto importante.Ho comunque scritto i test delle prestazioni, ma attualmente sto scegliendo la risposta corretta in base alla velocità e alla precisione utilizzando una formula "istinto".

I miei test sulle prestazioni elaborano 1000 diversi set di 100 numeri generati casualmente.Ogni algoritmo viene testato utilizzando lo stesso insieme di numeri casuali.Gli algoritmi sono scritti in .NET 3.5 (sebbene finora sarebbe stato compatibile con 2,0) ho cercato di rendere i test il più equo possibile.

Greg - Moltiplica per grande numero e quindi dividi per GCD - 63 millisecondi
Andy - Analisi delle stringhe - 199 millisecondi
Eric – Decimal.GetBits – 160 millisecondi
Eric - Ricerca binaria - 32 millisecondi
IMA - scusa non sono riuscito a capire come implementare facilmente la tua soluzione in .NET (non volevo passare troppo a lungo)
Bill - Immagino che la tua risposta fosse abbastanza vicina a quella di Greg, quindi non l'ha implementata.Sono sicuro che sarebbe un flash più veloce ma potenzialmente meno accurato.

Quindi la soluzione "Moltiplica per un numero grande e poi dividi per GCD" di Greg è stata il secondo algoritmo più veloce e ha fornito i risultati più accurati, quindi per ora lo definisco corretto.

Volevo davvero che la soluzione Decimal.GetBits fosse la più veloce, ma era molto lenta, non sono sicuro se ciò sia dovuto alla conversione di un Double in un Decimal o al mascheramento e allo spostamento del Bit.Dovrebbe esserci una soluzione utilizzabile simile per un doppio dritto usando BitConverter.getbytes e alcune conoscenze contenute qui: http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point-types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew- greig.aspx ma i miei occhi continuavano a velarsi ogni volta che leggevo quell'articolo e alla fine ho esaurito il tempo per provare a implementare una soluzione.

Sono sempre aperto ad altre soluzioni se qualcuno riesce a pensare a qualcosa di meglio.

Soluzione

Moltiplicherei per qualcosa di sufficientemente grande (100.000.000 con 8 cifre decimali), quindi dividerei per GCD dei numeri risultanti.Ti ritroverai con una pila di numeri interi più piccoli che puoi fornire all'altro algoritmo.Dopo aver ottenuto il risultato, invertire il processo per ripristinare l'intervallo originale.

Altri suggerimenti

Più tutti i numeri di 10 fino a quando non hai numeri interi.
Dividi per 2,3,5,7 mentre hai ancora tutti i numeri interi.

Penso che questo copra tutti i casi.

2.1 * 10/7 -> 3
0.008 * 10^3/2^3 -> 1

Ciò presuppone che il tuo moltiplicatore possa essere una frazione razionale.

Se vuoi trovare un intero N tale che N*x sia anche un intero esatto per un insieme di numeri in virgola mobile x in un dato insieme sono tutti interi, allora hai un problema sostanzialmente irrisolvibile.Supponiamo che x = il più piccolo float positivo che il tuo tipo possa rappresentare, diciamo che è 10^-30.Se moltiplichi tutti i tuoi numeri per 10^30 e poi provi a rappresentarli in binario (altrimenti, perché ti sforzi così tanto di renderli interi?), perderai praticamente tutte le informazioni degli altri numeri a causa traboccare.

Ecco quindi due suggerimenti:

Se hai il controllo su tutto il codice correlato, trova un altro approccio.Ad esempio, se hai una funzione che prende solo INT, ma hai galleggianti e vuoi riempire i tuoi galleggianti nella funzione, basta riscrivere o sovraccaricare questa funzione per accettare anche i galleggianti.
Se non hai il controllo sulla parte del tuo sistema che richiede INT, allora scegli una precisione a cui tieni, accetta che dovrai semplicemente perdere alcune informazioni a volte (ma sarà sempre "piccolo" in un certo senso ), e quindi moltiplica tutti i tuoi galleggianti da quella costante e rotonda all'intero più vicino.

A proposito, se hai a che fare con le frazioni, piuttosto che con il float, allora è un gioco diverso.Se hai un sacco di frazioni a/b, c/d, e/f;e vuoi un moltiplicatore minimo comune N tale che N*(ogni frazione) = un numero intero, quindi N = aBc / mcd(a,b,c);e mcd(a,b,c) = mcd(a, mcd(b, c)).Puoi usare Algoritmo di Euclide per trovare il MCD di due numeri qualsiasi.

Greg:Bella soluzione, ma il calcolo di un GCD comune in una serie di oltre 100 numeri non diventerà un po' costoso?E come faresti a riguardo?È facile fare GCD per due numeri ma per 100 diventa più complesso (credo).

Andy malvagio:Sto programmando in .Net e la soluzione che proponi corrisponde praticamente a ciò che facciamo ora.Non volevo includerlo nella mia domanda originale perché speravo in un pensiero fuori dagli schemi (o comunque dai miei schemi) e non volevo contaminare le risposte delle persone con una potenziale soluzione.Sebbene non disponga di solide statistiche sulle prestazioni (perché non ho avuto nessun altro metodo con cui confrontarlo), so che l'analisi delle stringhe sarebbe relativamente costosa e ho pensato che una soluzione puramente matematica potesse essere potenzialmente più efficiente.Per essere onesti, l'attuale soluzione di analisi delle stringhe è in produzione e non ci sono ancora state lamentele riguardo alle sue prestazioni (è anche in produzione in un sistema separato in un formato VB6 e nessuna lamentela neanche lì).È solo che non mi sembra giusto, immagino che offenda la mia sensibilità di programmazione, ma potrebbe essere la soluzione migliore.

Detto questo sono ancora aperto a qualsiasi altra soluzione, puramente matematica o meno.

In che linguaggio stai programmando?Qualcosa di simile a

myNumber.ToString().Substring(myNumber.ToString().IndexOf(".")+1).Length

ti darebbe il numero di cifre decimali per un doppio in C#.Potresti scorrere ogni numero e trovare il maggior numero di cifre decimali (x), quindi moltiplicare ciascun numero per 10 alla potenza di x.

Modificare:Per curiosità, cos'è questo sistema sigillato a cui puoi passare solo numeri interi?

In un ciclo ottieni la mantissa e l'esponente di ciascun numero come numeri interi.Puoi usare frexp per l'esponente, ma penso che per la mantissa sarà necessaria la maschera di bit.Trova l'esponente minimo.Trova le cifre più significative nella mantissa (scorri i bit cercando l'ultimo "1") o utilizza semplicemente un numero predefinito di cifre significative.Il tuo multiplo sarà quindi qualcosa come 2^(numberOfDigits-minMantissa)."Qualcosa come" perché non ricordo pregiudizi/compensazioni/intervalli, ma penso che l'idea sia abbastanza chiara.

Quindi in pratica vuoi determinare il numero di cifre dopo la virgola decimale per ogni numero.

Sarebbe piuttosto più semplice se avessi la rappresentazione binaria del numero.I numeri vengono convertiti da notazioni razionali o scientifiche in precedenza nel tuo programma?Se è così, potresti saltare la conversione precedente e divertirti molto più facilmente.Altrimenti potresti voler passare ogni numero a una funzione in una DLL esterna scritta in C, dove potresti lavorare direttamente con la rappresentazione in virgola mobile.Oppure potresti trasformare i numeri in decimali e lavorarci un po' Decimal.GetBits.

L'approccio più veloce che riesco a pensare sul posto e seguendo le tue condizioni sarebbe quello di trovare la più piccola potenza di dieci necessaria (o 2, o qualsiasi altra cosa) come suggerito prima.Ma invece di farlo in un ciclo, risparmia alcuni calcoli eseguendo una ricerca binaria sulle possibili potenze.Supponendo un massimo di 8, qualcosa del tipo:

int NumDecimals( double d )
{
   // make d positive for clarity; it won't change the result
   if( d<0 ) d=-d;

   // now do binary search on the possible numbers of post-decimal digits to 
   // determine the actual number as quickly as possible:

   if( NeedsMore( d, 10e4 ) )
   {
      // more than 4 decimals
      if( NeedsMore( d, 10e6 ) )
      {
          // > 6 decimal places
          if( NeedsMore( d, 10e7 ) ) return 10e8;
          return 10e7;
      }
      else
      {
         // <= 6 decimal places
         if( NeedsMore( d, 10e5 ) ) return 10e6;
         return 10e5;
      }
   }
   else
   {
      // <= 4 decimal places
      // etc...
   }

}

bool NeedsMore( double d, double e )
{
   // check whether the representation of D has more decimal points than the 
   // power of 10 represented in e.
   return (d*e - Math.Floor( d*e )) > 0;
}

PS:non passeresti i prezzi dei titoli a un motore di determinazione dei prezzi delle opzioni, vero?Ha esattamente il sapore...

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow