Dove sono “Numeri speciali” di cui alla matematica calcestruzzo usati?

Question

Stavo sfogliando il contenuto della matematica calcestruzzo in linea. Avevo almeno sentito parlare la maggior parte delle funzioni e trucchi menzionati ma c'è un'intera sezione sui Numeri Speciali. Questi numeri includono i numeri di Stirling, numeri di Eulero, numeri armonici così via. Ora ho mai incontrato uno di questi numeri strani. Come si aiutano a problemi computazionali? Dove sono generalmente utilizzati?

Answer 1

La maggior parte di questi numeri contano certi tipi di strutture discrete (per esempio, numeri di Stirling contano sottoinsiemi e Cicli). Tali strutture, e quindi queste sequenze, implicitamente sorgere nell'analisi di algoritmi .

una lunga lista in cui sono elencati OEIS < em> quasi tutte le sequenze che appaiono in calcestruzzo Math . Un breve riassunto da quella lista:

• Sequenza di Golomb
• binomiali coefficienti
• Rencontres Numbers
• I numeri Stirling
• Numeri Euleriani
• Hyperfactorials
• I numeri di Genocchi

È possibile sfogliare le pagine OEIS per le rispettive sequenze per ottenere informazioni dettagliate sulle "proprietà" di queste sequenze (anche se non esattamente le applicazioni, se è questo che siete più interessati).

Inoltre, se si desidera vedere nella vita reale utilizza di queste sequenze in analisi di algoritmi, sfogliare l'indice d'Arte di Knuth of Computer Programming, e troverete molti riferimenti a "Applicazioni" di queste sequenze. John D. Cook già accennato applicazioni dei numeri di Fibonacci e armonico; ecco alcuni esempi:

numero di cicli Stirling sorgere nell'analisi dell'algoritmo standard che trova il elemento massimo di un array (TAOCP Sec 1.2.10.): Quante volte deve il corrente valore massimo viene aggiornato quando trovare il valore massimo? Si scopre che la probabilità che il massimo dovrà essere volte k aggiornati quando trovare un massimo di un array di elementi n è p[n][k] = StirlingCycle[n, k+1]/n!. Da questo, si può ricavare che in media, di circa saranno necessari aggiornamenti Log(n).

Numeri Genocchi sorgono in connessione con conteggio del numero di BDDS che sono "sottile" (TAOCP 7.1.4 esercizio 174).

Answer 2

numeri armonici appaiono un po 'ovunque! Armonie musicali, l'analisi di Quicksort ... Numeri Stirling (primo e secondo tipo) insorgere in una varietà di combinatoria e problemi di partizionamento. Numeri Euleriane verificano anche diversi posti, in particolare in permutazioni e coefficienti di funzioni polilogaritmo.

Answer 3

Un sacco di numeri che hai citato sono utilizzati per l'analisi degli algoritmi. Non si può avere questi numeri nel codice, ma avrete bisogno di loro se si vuole stimare quanto tempo ci vorrà per il codice per l'esecuzione. Si potrebbe vederli nel codice troppo. Alcuni di questi numeri sono legati al calcolo combinatorio, contando quanti modi può sempre capitare qualcosa.

A volte non è sufficiente per sapere quante possibilità ci sono perché è necessario enumerate sopra le possibilità. Volume 4 di di Knuth TAOCP , in corso, dà gli algoritmi necessari.

Ecco un esempio di utilizzo di Fibonacci come parte di un problema di integrazione numerica.

numeri armoniche sono un analogo discreto di logaritmi e così arrivano in equazioni di differenza come tronchi venire nelle equazioni differenziali. Ecco un esempio di applicazioni fisiche di media armonica , relativi a numeri armonici. Vedi il libro Gamma per molti esempi di numeri armonici in azione, in particolare il capitolo "E 'un mondo armonico".

Answer 4

Questi numeri speciali possono aiutare in problemi computazionali in molti modi. Ad esempio:

• Si vuole sapere quando il programma per calcolare il MCD di 2 numeri sta andando a prendere la quantità di tempo più lungo:. Prova 2 numeri di Fibonacci consecutivi

• Si desidera avere una stima approssimativa del fattoriale di un numero elevato, ma il vostro programma fattoriale sta impiegando troppo tempo: Usare di Stirling Approssimazione .

• Si sta testando per i numeri primi, ma per alcuni numeri si ottiene sempre la risposta sbagliata: Potrebbe essere che stai utilizzando il test Prime di Fermat, nel qual caso il noreferrer numeri Carmicheal sono i vostri colpevoli.

Il caso generale più comune che viene in mente è in loop. Il più delle volte si specifica un ciclo utilizzando un tipo (start;stop;step) della sintassi, nel qual caso potrebbe essere possibile ridurre il tempo di esecuzione utilizzando le proprietà dei numeri coinvolti.

Per esempio, sommando tutti i numeri da 1 a n quando n è grande in un ciclo è sicuramente più lento rispetto all'uso del sum = n*(n + 1)/2 identità.

Ci sono un gran numero di esempi come questi. Molti di loro sono in crittografia, dove la sicurezza dei sistemi informativi a volte dipende su trucchi come questi. Essi possono anche aiutare con problemi di prestazioni, problemi di memoria, perché quando si conosce la formula, si può trovare un modo più veloce / più efficiente per calcolare le altre cose -. Cose che effettivamente interessano

Per ulteriori informazioni, Check out Wikipedia, o semplicemente provare Project Euler. Potrai iniziare a trovare modelli piuttosto veloce.

Answer 5

Non necessariamente una numero magico dal riferimento che lei ha citato, ma comunque -

0x5f3759df

- il numero magico noto utilizzato per calcolare la radice quadrata inverso di un numero, dando una buona prima stima a Newton di Ravvicinamento delle Radici , spesso attribuiti al lavoro di John Carmack - maggiori informazioni qui .

Non programmazione relativa, eh? :)

Answer 6

E 'questo direttamente programmazione relativa? Sicuramente correlate, ma non so quanto strettamente.

Numeri speciali, come ad esempio e, pi, ecc, vengono su tutto il luogo. Non credo che qualcuno possa discutere su questi due. Il Golden_ratio compare anche con sorprendente frequenza, in tutto, dall'arte alla altri numeri speciali stessi (vedi il rapporto tra i numeri di Fibonacci successivi.)

Diverse sequenze e le famiglie di numeri appaiono anche in molti luoghi in matematica e quindi, in programmazione anche. Un bel posto da vedere è il Encyclopedia of sequenze intere .

Ti suggerisco questa è una cosa esperienza. Per esempio, quando ho preso l'algebra lineare, molti, molti anni fa, ho imparato a conoscere gli autovalori e autovettori di una matrice. Devo ammettere che non ho affatto apprezzato il significato di autovalori / autovettori fino a quando li ho visti in uso in una varietà di luoghi. In statistica, in termini di ciò che ti dicono per l'incertezza di una stima da una matrice di covarianza, la dimensione e la forma di un ellisse di fiducia, in termini di analisi delle componenti principali, o lo stato di lungo termine di un processo di Markov. In metodi numerici, dove si raccontano la convergenza di un metodo, sia nell'ottimizzazione o un risolutore ODE. In ingegneria meccanica, dove si vede come tensioni principali e le tensioni.

Answer 7

Discussione in Reddit