Utilizzare il Raspberry PI per eseguire task math related non è in genere un sistema valido. A meno che non si parli di ottimizzazione.
Lavorare con catene socievoli e numeri narcisisti è sempre stato divertente: si lavora su alcune caratteristiche del numero (posizione delle cifre, divisibilità, presenza di fattori) e si valuta un algoritmo di ricerca in grado di garantire un risultato valido in un tempo definito.
Tra l’altro questo genere di lavori consente da un lato notevoli spunti di ottimizzazione, mentre dall’altro restano sufficientemente semplici per l’utilizzo di un algoritmo.
I numeri di Armstrong
Narciso secondo la leggenda si innamorò della propria figura riflessa in uno specchio d’acqua e così affogò, per poi venire trasformato in fiore. I numeri narcisisti sono quelli tali per cui se si eleva ciascuna cifra all’esponente pari al numero di cifre del numero stesso e si sommano i risultati di queste operazioni, si ottiene il numero di partenza.
I numeri di Armstrong sono numeri narcisisti con esponente 3. In altri termini soddisfano la seguente equazione:
a, b, c sono numeri interi compresi tra 0 e 9.
a3 + b3 + c3 = abc (1)
o, in esempio:
13 + 53 + 33 = 153
Scrivere un programma che preveda di trovare le soluzioni di questa equazione è immediato. per testare i primi diecimila numeri sarà sufficiente assegnare a quattro variabili (a, b c e d, appunto) i valori rispettivamente di migliaia, centinaia, decine e unità, facendoli ciclare tra 0 e 9. Avremo così 10 x 10 x 10 x 10 = 10.000 diverse combinazioni delle cifre che ci daranno i primi 10.000 numeri, tra 0 e 9999.
Complessità del calcolo
Per diecimila volte testeremo quindi la seguente operazione:
|
1 |
if ((a*1000 + b*100 + c*10 + d) == (a*a*a + b*b*b + c*c*c + d*d*d)) |
che rappresenta l’istruzione in codice C dell’espressione definita in (1).
L’espressione conta 11 moltiplicazioni, 6 addizioni ed un confronto, per un totale di 18 operazioni singole. Calcolate su 10.000 numeri ci danno poco meno di 200.000 operazioni. Un compito che anche un piccolo processore ARM riesce a svolgere in una manciata di millesimi di secondo.
Ma perché fermarci a 9.999?
Euristiche e ottimizzazioni
Perché i numeri di Armstrong non sono infiniti. Anzi, quelli mostrati nell’immagine sono tutti i numeri di Armstrong esistenti. In teoria è possibile dimostrare che già con meno di 3000 numeri si arriva al massimo teorico. Vediamo come.
Nella formula (1), scopriamo che la parte destra dell’espressione è rappresentata da una somma di cubi. Il numero di addendi è pari al numero di cifre del numero calcolato. Dal momento che le cifre variano tra 0 e 9, avremo i seguenti numeri massimi rappresentabili:
1) Con una cifra: 93 = 729
2) Con due cifre: 93 + 93 = 1458
3) Con tre cifre: 93 + 93 + 93 = 2187
4) Con quattro cifre: 93 + 93 + 93 + 93 = 2916
Ma attenzione: con quattro cifre siamo in grado di ottenere il numero 9999, che è molto più grande di quanto si possa rappresentare con la somma di cubi. Quindi potremmo tranquillamente limitarci a verificare la nostra equazione esclusivamente per i valori di a compresi tra 0 e 2, tralasciando così i valori di a tra 3 e 9 e risparmiando in tal modo il 70 per cento dei calcoli.
In questo caso una euristica analitica è stata in grado di abbattere il tempo di elaborazione di un fattore 3.
Con un vantaggio del genere il mio primo programma di ricerca di numeri di Armstrong, scritto in BASIC sul Commodore 64, sarebbe durato solo un giorno anziché tre…
Il nostro sorgente
E a proposito di sorgenti, ecco il semplice programma armstrong.c.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <stdio.h> int main() { int a,b,c,d; for (a = 0; a <= 9; a++) { for (b = 0; b <= 9; b++) for (c = 0; c <= 9; c++) for (d = 0; d <= 9; d++) { if ((a*1000 + b*100 + c*10 + d) == (a*a*a + b*b*b + c*c*c + d*d*d)) printf ("%5i\n",a*1000 + b*100 + c*10 + d); } } } |
Il codice potrebbe essere ulteriormente ottimizzato. Si osservi ad esempio che se un numero da testare è pari, allora dovrà avere un numero pari di cifre dispari (o nessuna cifra dispari). Infatti è noto che l’elevazione al cubo mantiene la parità originale della cifra. Un test simile è possibile per i numeri divisibili per 5. Nel nostro caso tuttavia l’ulteriore complicazione del codice non offrirebbe un guadagno di velocità sensibile.
Ovviamente, volendo cercare tutti i numeri narcisisti (sono 88, tutti inferiori a 1060) queste ultime ottimizzazioni del codice sarebbero invece molto utili. Ma in tal caso dovremmo utilizzare anche una libreria per i calcoli in precisione multipla.
Conclusioni
Anche per oggi abbiamo concluso. Se avete idee per altre ottimizzazioni, o codice simile da presentare, scrivetemi.
Luigi_Morelli
Definire ciò che si è non risulta mai semplice o intuitivo, in specie quando nella vita si cerca costantemente di migliorarsi, di crescere tanto professionalmente quanto emotivamente. Lavoro per contribuire al mutamento dei settori cardine della computer science e per offrire sintesi ragionate e consulenza ad aziende e pubblicazioni ICT, ma anche perche’ ciò che riesco a portare a termine mi dà soddisfazione, piacere. Così come mi piace suonare (sax, tastiere, chitarra), cantare, scrivere (ho pubblicato 350 articoli scientfici e 3 libri sinora, ma non ho concluso ciò che ho da dire), leggere, Adoro la matematica, la logica, la filosofia, la scienza e la tecnologia, ed inseguo quel concetto di homo novus rinascimentale, cercando di completare quelle sezioni della mia vita che ancora appaiono poco ricche.