Don't take life too seriously: it's just a temporary situation

Porter (costante di)

Teoria dei numeri 

L’algoritmo di Euclide per trovare il massimo comun divisore tra due numeri naturali è probabilmente il più antico algoritmo di uso generale, cioè non valido solo per casi speciali, del quale si abbia traccia.

 

L’algoritmo consiste nell’esaminare il resto ottenuto dividendo il maggiore dei due numeri per il minore: se è zero, il minore dei due numeri è il massimo comun divisore cercato, altrimenti si ripete l’algoritmo col resto e il divisore.

Per esempio, iniziando con 3276 e 1190 si procede così:

  • il resto della divisione tra 3276 e 1190 è 896;

  • il resto della divisione tra 1190 e 896 è 284;

  • il resto della divisione tra 896 e 284 è 14;

  • il resto della divisione tra 284 e 14 è 0, quindi 14 e il numero cercato.

Questo algoritmo è talmente semplice ed efficiente che si insegna alle elementari e si usa ancora dopo oltre 25 secoli.

 

L’algoritmo termina sicuramente dopo un numero finito di passi, perché produce numeri sempre minori; dato che il numero di passi dipende dai valori iniziali, ha senso chiedersi quanti possano essere nel caso peggiore e in media.

I casi peggiori sono facili da trovare: sono dati da due numeri di Fibonacci consecutivi. Il minimo comune multiplo di due qualsiasi numeri di Fibonacci consecutivi è 1 e partendo con Fn + 2 e Fn + 1, l’algoritmo impiega n passi a determinarlo; nessuna coppia di interi positivi inferiori ne richiede altrettanti (de Lagny 1733).

Dato che i numeri di Fibonacci ci danno i successivi record di numero di passi, possiamo stabilire tramite la formula di Binet che se il maggiore dei due numeri è n, il numero di passi non supera Numero massimo di passi per calcolare il massimo comun divisore tra due interi positivi non superiori a n (G. Lamé).

Si può anche esprimere approssimativamente questo risultato dicendo che il numero di passi è inferiore a 5 volte il numero di cifre del maggiore dei due numeri.

 

Il numero di operazioni necessarie in media è però molto inferiore, ma anche molto complesso da calcolare, tanto che la risposta è stata ottenuta solo in tempi relativamente recenti: ancora negli anni ’70 Knuth lamentava come una grave carenza della moderna teoria degli algoritmi il fatto che l’algoritmo più antico non fosse stato analizzato in modo soddisfacente.

 

Chiamando n il maggiore dei due interi, H. Heibronn dimostrò nel 1969 che il numero medio di passi, scegliendo a caso il numero minore, tende a Limite asintotico cui tende il numero medio di passi per calcolare il massimo comun divisore tra n e un intero positivo inferiore e la stima venne in seguito raffinata come tendente a Limite asintotico cui tende il numero medio di passi per calcolare il massimo comun divisore tra n e un intero positivo inferiore.

 

J.W. Porter dimostrò nel 1975 che la media del numero di passi, calcolata su tutti gli interi inferiori a n e primi rispetto a n, tende a Limite asintotico cui tende il numero medio di passi per calcolare il massimo comun divisore tra n e un intero positivo inferiore e primo rispetto a n.

G.H. Norton dimostrò nel 1990 che la media del numero di passi, calcolatasu tutti gli interi inferiori a n e primi rispetto a n, tende a Limite asintotico cui tende il numero medio di passi per calcolare il massimo comun divisore tra n e un intero positivo inferiore e primo rispetto a n, mentre se si scelgono due interi a caso non superiori a n, la media tende a Limite asintotico cui tende il numero medio di passi per calcolare il massimo comun divisore tra due interi positivi non superiori a n, con Formula per la definizione della costante di Norton, detta “costante di Norton”.

In queste espressioni C è Formula per la definizione della costante di Porter, ed è nota come “costante di Porter” o “costante di Porter – Hensley”.

Qui trovate le prime 1001 cifre decimali della costante di Porter.

 

Donald Erwin Knuth suggerì di chiamare la costante “costante di Lochs – Porter”, per ricordare il contributo di Gustav Lochs alla soluzione del problema. Nel 1961, infatti, Lochs aveva menzionato la costante Formula per (1 – 2*B) / 4

nei suoi lavori.

Qui trovate le prime 1000 cifre decimali della costante menzionata da Lochs.

Knuth calcolò le prime 40 cifre decimali della costante di Porter, esprimendola come 4 * P + 5 / 2, dove Formula per il calcolo di P.

J.W. Wrench Jr. notò che Formula per il la semplificazione della serie e Formula per il la semplificazione dell'integrale indefinito, da cui Formula per il la semplificazione dell'integrale definito, quindi la formula può essere semplificata, riducendola a Formula per il calcolo di P.

 

Norton notò che la costante di Porter si può esprimere come Formula per il calcolo di P, dove A è la costante di Glaisher – Kikelin.

 

Da notare che il numero di passi per trovare il massimo comun divisore tra m e n (con n > m) è uguale al numero di termini della rappresentazione di m / n come frazione continua regolare; data tale connessione con le frazioni continue, forse non è del tutto sorprendente l’apparizione della costante di Lévy in tutte le formule.

 

E’ interessante notare che esiste una variante dell’algoritmo, detto algoritmo binario di Euclide, che richiede solo sottrazioni e divisioni per due.

Si inizia dividendo i due numeri per due finché possibile e annotando la massima potenza di due che divide entrambi; si procede quindi ripetendo le seguenti operazioni:

  • si divide uno dei due numeri, se pari, per 2, sino a restare con due numeri dispari;

  • se i due numeri sono diversi, si sottrae il minore dall’altro e si continua;

  • altrimenti il numero ottenuto, moltiplicato per la potenza di 2 annotata in precedenza, è il massimo comun divisore cercato.

Per esempio, iniziando con 6552 e 2380 si divide il primo per 8 e il secondo per 4, annotandosi il 4 e restando con 819 e 595.

A questo punto si ha a che fare con numeri dispari: si divide la differenza tra i due per la massima potenza di 2 possibile e si ripete l’operazione considerando ogni volta il quoziente ottenuto e minore dei due numeri, fino a quando la differenza è uguale al minore.

Nell’esempio, otterremo successivamente:

  • 819 – 595 = 224, che diviso per 32 dà 7;

  • 595 – 7 = 588, che diviso per 32 dà 147;

  • 147 – 7 = 140, che diviso per 4 dà 35;

  • 35 – 7 = 28, che diviso per 4 dà 7, uguale al minore dei due numeri considerati.

Il prodotto tra l’ultima differenza e la potenza di due precedentemente annotata dà il massimo comun divisore, nel nostro caso 7 • 4 = 28.

L’algoritmo impiega in genere qualche passo in più di quello di Euclide, ma ha il vantaggio di richiedere solo semplici divisioni per due e non divisioni tra numeri qualsiasi, quindi è in genere più rapido, sia procedendo manualmente, sia con un calcolatore.

 

L’analisi del comportamento medio di questo algoritmo è ancora più complessa di quella dell’algoritmo originale e non è stata ancora portata a termine; se sono vere alcune congetture tuttora non dimostrate, il numero medio di passi per interi non superiori a n tende a circa 1.0185012157logn.

Il caso peggiore è però facile da determinare: è dato da numeri della forma 2n – 1 + 1 e 2n – 1 – 1, che richiedono n passi. Pertanto se il maggiore dei due numeri è n, il numero di passi non supera log2(n – 1) = log(n – 1) / log(2), vale a dire che nel caso peggiore questo algoritmo richiede meno passi di quello di Euclide.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.