2016-07-04 21 views
8

Per diversi giorni, mi sono chiesto come sarebbe possibile calcolare il seno di numeri enormi con grandezza intorno a 100000! (radianti). Il fattoriale è solo un esempio del numero stesso che può essere qualsiasi non solo un prodotto fattoriale ...) Ovviamente non uso double ma cpp_rational dalla libreria boost multiprecision. Ma non posso semplicemente fare 100000! mod 2pi e quindi utilizzare la funzione incorporata sinl (non ho bisogno di più di 10 cifre decimali ..) poiché avrei bisogno di diversi milioni di cifre di pi per farlo con precisione.Come calcolare il seno di numeri enormi

Esiste un modo per raggiungere questo obiettivo?

+2

Questo è davvero un problema molto difficile: le buone librerie matematiche usano infatti un gran numero di cifre di pi (l'approssimazione infinito-pi), mentre altre usano un'approssimazione peggiore, ma più economica, finita-pi. –

+0

@duffymo ti sei perso il punto. Da alcune unità astronomiche, per così dire. – sehe

+0

Non puoi vincerli tutti. Forse dovremmo chiedere perché/come ha inteso calcolare 100000 !. Questo è solo ignorante. – duffymo

risposta

5

Questo è in generale un compito non banale, in quanto ha molte somiglianze con lo Discrete Logarithm Problem, che implica a sua volta un calcolo intensivo dal punto di vista computazionale.
Detto questo, il calcolo potrebbe essere più semplice se si considera il logaritmo di 100000!/pi, poiché si riduce alla somma dei registri di tutti gli interi positivi uguali o inferiori a 100000 e una sottrazione: log(N!/pi) = \sum_{i=0}^N (log i) - log(pi). Se esponenti questo numero, hai una valutazione approssimativa di (N!/pi). Sottrarre la parte intera e moltiplicare il risultato per pi. Questa è la stima del tuo N! mod pi.
Nella formula:

Come si può notare, ho usato molte volte la parola approssimativa. Ciò è dovuto alle seguenti considerazioni:

  • si deve calcolare molte log s, che hanno alcuni costi e gli errori
  • si consiglia di cambiare la base del registro, secondo la vostra dimensione del problema; ancora una volta questo sta andando a influenzare l'accuratezza e la precisione del vostro risultato
  • bisogna exponentiate indietro: piccoli errori possono portare a quelle di grandi dimensioni
  • sottrarre grandi numeri: può portare a grandi cancellazioni
  • moltiplicare per pi e valutare le sin: errori di nuovo

se si pensa che può essere utile, è possibile utilizzare il Stirling's approximation.

Come ultima osservazione, non esiste una soluzione facile a questo tipo di problemi, è sempre necessario gestirli caso per caso.

+0

Il problema è: io in realtà non computo' sin (100000!) 'ma ho solo un numero _come big_ 100000!' per il quale voglio calcolare il seno. – borchero

+0

Ok, puoi usare 'log's per qualsiasi numero positivo, giusto? :-) – fedino

+0

Sì, certo, ma non posso usare la somma nel modo in cui la descrivi. – borchero

-2

Forse è possibile utilizzare cpp_rational per calcolare il seno direttamente dal tuo numero molto grande:

sin(x): x/1! - x^3/3! + x^5/5! - x^7/7! + ... 

Ripetere questa serie fino a quando non si verificano (per l'applicazione) cambiamenti significativi. In questo modo si evita il numero pi completamente.

+0

L'espansione della serie taylor su x = 0 è solo un'approssimazione per i primi pochi periodi del seno, o dovrei passare attraverso la somma diverse migliaia di volte che non è pratico (non posso usare l'espansione in x = molto grande sia perché avrei bisogno di calcolare il seno ...) – borchero

+1

Come vedi, la "sin' Taylor expantion si alterna nel suo segno. Quindi finisci per riassumere molti termini, con qualche cancellazione. Ciò potrebbe ridurre l'accuratezza, in modo tale da avere un risultato stabile, ma ciò è sbagliato. Considera anche che devi valutare la potenza di un numero già molto grande, che peggiora e peggiora. – fedino

+0

@fedino Con razionali di precisione arbitraria, ciò non accadrà. –

0

Wikipedia elenca molte identità trigonometriche. Alcuni includono i prodotti nell'argomento, come ad esempio Chebyshev's Method che è ricorsivo ma la ricorsione può essere ridotta utilizzando Chebyshev Polynomials e/o la memoizzazione. Se il tuo argomento è facile da considerare fattoriale, allora questo potrebbe essere un metodo fattibile.

0

Nota:  = pi

Per calcolare il peccato di un numero molto grande in radianti (cambiarli a multipli di  dividendo per 3,1415)
1. Osservare questo: sin 0 = 0, il peccato 0.5 pi = 1, sin pi = 1, sin1.5pi = -1, sin 2pi = 0
2. I valori interi pari o dispari davanti a pi, il sin è 0
3. Per valori reali (quelli con punti decimali), per i numeri pari prima del punto decimale, prendi come 0. qualcosa come il valore del seno, per strano, quindi prendi il 1. qualcosa come valore del seno.
4. Vedi esempi * Nota che sin e cosine sono di natura periodica, per cui è possibile farlo in questo modo per numeri grandi o piccoli. :)

Es. (Utilizzare le calcolatrici per verificare i calcoli)

1.0 in radianti: peccato 100 = -0,506
Divide by 3.1415
fare deg
Sin 31.831pi (31,831 è un valore reale) = sin1.831 (180) = -0,506, controllare

2.0 in radianti: sin 50 = -0,2623
Divide by 3.1415
fare deg
Sin 15.9155pi = sin1.9155 (180) = -0,2623

3.0 in radianti: peccato 700 = 0,5439
Divide by 3.1415
fare deg
Sin 222.8169pi = sin0.8169 (180) = -0,5440, controllare

4.0 in radianti: peccato 15000 = 0,8934
divide by 3.1415
fare deg
Sin 4774.6483pi = sin0.6483 (180) = 0,893, controllare

Si può vedere che tutte le risposte controllato con il calcolo diretto dei valori utilizzando la calcolatrice in modalità radianti . Spero che questo sia utile.

Se si desidera scrivere un programma di calcolo, buona fortuna nel capire l'algoritmo.

Problemi correlati