Archive for giugno 2021
Formula di Luhn
Chi era Luhn? Cosa ha fatto?
Cosa è la formula di Luhn?
Voi sicuramente non lo sapete e non ci penserete, ma la formula di Luhn la usiamo tutti i giorni inconsapevolmente, quando prendiamo in mano una carta da credito per fare un acquisto online o fisicamente in negozio.
Cosa centra una formula matematica con la carta di credito?
Vediamo prima la vita di questo Luhn.
Hans Peter Luhn (1o luglio 1896 – 19 agosto 1964) è stato ricercatore nel campo dell’informatica e della Library & Information Science per IBM,e creatore dell’algoritmo luhn, dell’indicizzazione KWIC (Key W ords In Context) e della diffusione selettiva delle informazioni ("SDI"). Le sue invenzioni hanno trovato applicazioni in diversi settori come l’informatica, l’industria tessile, la linguistica e la scienza dell’informazione. Gli sono stati concessi oltre 80 brevetti.
Luhn nacque a Barmen,in Germania (ora parte di Wuppertal)il 1o luglio 1896. Dopo aver completato la scuola secondaria, Luhn si trasferì in Svizzera per imparare il commercio di stampa in modo da poter entrare nell’azienda di famiglia. La sua carriera nella stampa fu interrotta dal suo servizio come ufficiale di comunicazione nell’esercito tedesco durante la prima guerra mondiale. Dopo la guerra, Luhn entrò nel settore tessile, che alla fine lo portò negli Stati Uniti, dove inventò un indicatore di conteggio dei fili (il Lunometro) ancora sul mercato. Dalla fine degli anni venti ai primi anni quaranta, durante i quali ottenne brevetti per una vasta gamma di invenzioni, Luhn lavorò nel tessile e come consulente ingegneristico indipendente. Nel 1941 entrò a far parte di IBM come ingegnere di ricerca senior e presto divenne direttore della divisione di ricerca sul recupero delle informazioni.
La formula di Luhn, anche conosciuta come Modulo 10, è un semplice algoritmo che consente di generare e verificare la validità di vari numeri identificativi. Venne ideata nel 1954 dall’informatico dell’IBM Hans Peter Luhn e brevettata nel 1960. Ora di pubblico dominio ha molteplici applicazioni, ad esempio per i numeri delle carte di credito.
Ogni carta di credito ha un suo numero di carta (es. 0000-1234-5678-9123) dove la prima parte identifica il circuito internazionale (Visa, American Express, Mastercard…) mentre il resto la banca emittente ed il cliente.
Vediamo quindi come scrivere una funziona in VB.NET per la verifica di una carta di credito.
Si sommano tutte le cifre in posizione pari al doppio della somma di quelle in posizione dispari. Si considera quindi il modulo rispetto a 10 (ovvero il resto della divisione per 10) del valore così ottenuto; si determina quindi la cifra di Luhn come segue:
- se il modulo è 0 (la somma è divisibile per 10) la cifra di controllo sarà 0. Ad esempio se la somma = 60 che diviso per 10 dà resto 0, la cifra di Luhn sarà 0
- altrimenti la cifra di Luhn sarà la differenza tra 10 ed il modulo. Ad esempio se la somma = 61 che diviso per 10 dà resto 1, la cifra di Luhn sarà 9 (10-1)
La cifra di Luhn è la 16° cifra della carta di credito.
Dim NumeroCarta As String = "4716435917330099"
Dim cifraRaddoppiata As Integer
Dim cifraCorrente As Integer
Dim daSommare As Integer
Dim somma As Integer
For i = 1 To Len(NumeroCarta)
cifraCorrente = CInt(Mid(NumeroCarta, Len(NumeroCarta) + 1 – i, 1))
If (i Mod 2) <> 0 Then
cifraRaddoppiata = cifraCorrente * 2
If cifraRaddoppiata >= 10 Then
daSommare = 1 + (cifraRaddoppiata Mod 10) ‘somma le cifre se il numero è > 10
Else
daSommare = cifraRaddoppiata
End If
Else
daSommare = cifraCorrente
End If
somma = somma + daSommare
Next
If (somma Mod 10) = 0 Then
Console.Write(NumeroCarta & " è una carta valida")
Else
Console.Write(NumeroCarta & " è una carta non valida")
End If
Vi dico che la carta di esempio non è mia, quindi non provate a usare quella carta : – )
Alla prossima
Leggi l'articolo intero | Make a Comment ( None so far )Come ottenere la costante Pi Greco
Un articolo per calcolare il Pi Greco? Vi starete dicendo che Piero è impazzito. Mai stato così lucido come ora…
Vi starete dicendo che lo sanno anche i gatti che Pi Greco vale circa 3 e magari qualcuno si ricorda che vale 3,14.
Ma non è esattamente 3,14. E’ una costante ma possiamo usare diversi metodi per ottenere con precisione il valore di Pi Greco.
Vedremo in questo articolo come ottenere il valore 3,141592653589795028841971693993751058209749445923078164062862089986280348253421170679 etc etc etc
Intanto diamo una definizione di Pi Greco. Cosa è il Pi Greco?
Nella geometria piana il Pi Greco viene definito come il rapporto tra la lunghezza della circonferenza e quella del suo diametro, o anche come l’area di un cerchio di raggio 1. Molti libri moderni di analisi matematica definiscono il Pi Greco usando le funzioni trigonometriche
Il Pi Greco è conosciuto anche come costante di Archimede (da non confondere con il numero di Archimede) e costante di Ludolph o numero di Ludolph. Il Pi Greco non è una costante fisica o naturale, ma una costante matematica definita in modo astratto, indipendente da misure di carattere fisico.
La formula più semplice per otteberlo è questa: =4*ARCTAN(1) anche se ha una logica non corretta, ma matematicamente dà il valore corretto.
Il codice in VB.NET sarà quindi: Dim pg = 4 * Math.Atan(1)
Il risultato è:
Altro metodo facile è 2: * Math.Asin(1)
Oppure ancora: 2 * (Math.Asin(Math.Sqrt(1 – 1 ^ 2)) + Math.Abs(Math.Asin(1)))
Esistono poi delle formule più specifiche che vedremo e partono da un numero che dà un risultato. Questo risultato sarà usato per riapplicare quella specifica formula e avere un risultato più preciso da riusare e così via.
Sono delle interazioni e quando arriveremo al risultato che sarà uguale a quello precedente significa che avremo ottenuto il risultato.
Oppure con selle sequenze numeriche dove più si procede con la sequenza maggiore sarà la precisione.
Vediamo quali sono queste formule e come applicarle.
Serie di Gregory-Leibiniz:
=4/1-4/3+4/5-4/7+4/9-4/11+4/13-4/15 e così via. Per arrivare a una precisione di 10 cifre decimali dovremo arrivare a 500.000 interazioni.
Scriviamo il codice VB.NET:
Dim pigreco As Double = 0
For t = 1 To 2000000 Step 4
pigreco = pigreco + 4 / t – 4 / (t + 2)
Next
Alla prima iterazione pigreco vale 2.66, alla 2° iterazione vale 2.895, alla 3° 2.976 e così via. Ho messo l’arrivo dopo 2.000.000 perché nel ciclo incremento t di 4 unità e quindi sono 500000 cicli.
con t=500 arriviamo a 3.140793931672452, con t=5.000 pigreco vale 3.14119297334996, con t= 100.000 pigreco vale 3.1415726543897491.
Alla fine arrivo con un Pi greco pari a 3.1415916535897743
La settima cifra decimale non è ancora precisa. Aumentiamo il numero dei cicli e arriviamo a 10 milioni, sul mio pc è solo questioni di secondi.
Un miliardo di iterazioni sono 3.1415926515892578
A cento miliardi (una decina di minuti di elaborazione) pigreco vale 3.1415926535685275
Vediamo infine la serie di Nilakantha.E’ più veloce della formula si Leibiniz.
Per calcolare questa formula, parti da tre e inizia ad alternare somme e sottrazioni di frazioni in cui il numeratore è 4 e il denominatore è il prodotto di tre numeri interi consecutivi che vengono incrementati ad ogni nuova iterazione. Il denominatore di ogni frazione successiva è il prodotto di tre numeri, il primo dei quali è il più alto della frazione precedente.
=3 + 4/(2*3*4) – 4/(4*5*6) + 4/(6*7*8) – 4/(8*9*10) + 4/(10*11*12) – (4/(12*13*14) e così via.
Il codice corrispondente è:
Dim pigreco As Double = 3
For tr = 2 To 100000000000 Step 4
pigreco = pigreco + 4 / (tr * (tr + 1) * (tr + 2)) – 4 / ((tr + 2) * (tr + 3) * (tr + 4))
Next
Anche qua faccio l’iterazione fino ad arrivare a tr=100 miliardi, impiegando un terzo del tempo della formula di Leibiniz..
Il risultato finale sarà: 3.1415926535897869 diventando anche più preciso a parità di numero di iterazioni.
Concludendo, abbiamo visto come grazie alla programmazione, possiamo ottenere con un valore molto preciso il Pi Greco.
Nei prossimi articoli vedremo altri teoremi matematici come possono essere risolti con l’informatica.
Leggi l'articolo intero | Make a Comment ( None so far )LA SEQUENZA DI fIBONACCI
Secondo articolo sull’informatica applicata alla matematica.
Oggi vedremo la sequenza di Fibonacci. Sicuramente è un argomento che non tutti i comuni mortali conoscono, ma che abbiamo almeno la password per la matematica e/o l’astronomia e/o informatica
Prima di tutto vediamo chi è Fibonacci e cosa è questa sequenza.
Leonardo Pisano detto Fibonacci (Pisa, settembre 1170 circa – Pisa, 1242 ) è stato un matematico italiano.
È considerato uno dei più grandi matematici di tutti i tempi. Con altri dell’epoca contribuì alla rinascita delle scienze esatte dopo la decadenza dell’età tardo-antica e dell’Alto Medioevo. Con lui, in Europa, ci fu l’unione fra i procedimenti della geometria greca euclidea (gli Elementi) e gli strumenti matematici di calcolo elaborati dalla scienza araba (in particolare egli studiò per la parte algebrica il Liber embadorum dello studioso ebreo spagnolo Abraham ibn ‛Ezra).
Fibonacci è noto soprattutto per la sequenza di numeri da lui individuata e conosciuta, appunto, come "successione di Fibonacci" in cui ogni termine, a parte i primi due, è la somma dei due che lo precedono.
Una particolarità della sequenza o successione di Fibonacci è che il rapporto fra le coppie di termini successivi tende molto rapidamente al numero 1,61803…, noto con il nome di rapporto aureo o sezione aurea.
L’intento di Leonardo Fibonacci era quello di trovare una legge matematica che descrivesse la crescita di una popolazione di conigli.
Assumendo per ipotesi che:
- si disponga di una coppia di conigli appena nati
- questa prima coppia diventi fertile al compimento del primo mese e dia alla luce una nuova coppia al compimento del secondo mese;
- le nuove coppie nate si comportino in modo analogo;
- le coppie fertili dal secondo mese di vita in poi diano alla luce una coppia di figli al mese;
si verifica quanto segue:
- dopo un mese una coppia di conigli sarà fertile,
- dopo due mesi ci saranno due coppie di cui una sola fertile,
- nel mese seguente, terzo mese dal momento iniziale, ci saranno 2+1=3 coppie perché solo la coppia fertile avrà generato; di queste tre, due saranno le coppie fertili, quindi nel mese seguente (quarto mese dal momento iniziale) ci saranno 3+2=5 coppie
In questo esempio, il numero di coppie di conigli di ogni mese esprime la successione di Fibonacci.
La sequenza di Fibonacci la troviamo nella realtà, nella quotidianità, ci circonda tanto che andiamo a fare la spesa, tanto che andiamo a lavorare o torniamo a casa.
Ecco alcuni casi pratici:
– spirali delle conchiglie
– Foglie delle piante
– Fiori
– I rami degli alberi
– Spirali delle galassie
– Fiocco di neve
e così via.
Sembrerebbe che anche i nostri polmoni con le aorte e vene che portano sangue, essendo come gli alberi seguano la sequenza di Fibonacci.
Vediamo ora matematicamente come ottenere questi numeri.
I primi numeri sono: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …
Ossia 1+1 = 2
Il precedente di 2 è 1 e quindi 1+2=3
Il precedente di 3 è 2, quindi 2+3=5
Il precedente di 5 è 3, quindi 3+5=8
Il precedente di 8 è 5, quindi 5+8= 13
Il precedente di 13 è 8, quindi 8+13=21
Il precedente di 21 è 13, quindi 13+21=34
Il precedente di 34 è 21, quindi 21+34= 55
Il precedente di 55 + 34, quindi 34+55= 89 e così via.
Il nuovo numero si ottiene con la somma dei due numeri precedenti.
Vediamo ora come tradurre questo concetto matematico in un qualunque linguaggio di programmazione.
Io userò VB.NET ma è facile convertirlo in qualunque altro linguaggio.
Ma a cosa serve aver un programma che mi calcola la sequenza di Fibonacci?
Vediamo.
I numeri di Fibonacci sono importanti nell’analisi computazionale in fase di esecuzione dell’algoritmo di Euclide per determinare il più grande divisore comune di due interi: l’input del caso peggiore per questo algoritmo è una coppia di numeri di Fibonacci consecutivi.
I numeri di Fibonacci sono usati in una versione polifase dell’algoritmo di ordinamento unione in cui una lista non ordinamento è divisa in due liste le cui lunghezze corrispondono a numeri di Fibonacci sequenziali , dividendo la lista in modo che le due parti abbiano lunghezze nella proporzione approssimativa φ. Un’implementazione su nastro dell’ordinamento di unione polifase è stata descritta in The Art of Computer Programming.
Un albero di Fibonacci è un albero binario i cui alberi figlio (ricorsivamente) differiscono in altezza esattamente di 1. Quindi è un albero AVLe uno con il minor numero di nodi per una data altezza – l’albero AVL "più sottile". Questi alberi hanno un certo numero di vertici che è un numero di Fibonacci meno uno, un fatto importante nell’analisi degli alberi AVL.
I numeri di Fibonacci sono usati da alcuni generatori di numeri pseudocasuali.
I numeri di Fibonacci sorgono nell’analisi della struttura dati dell’heap di Fibonacci.
Un metodo di ottimizzazione unidimensionale, denominato tecnica di ricerca di Fibonacci, utilizza numeri di Fibonacci.
La serie numerica di Fibonacci è utilizzata per la compressione con perdita opzionale nel formato di file audio IFF 8SVX utilizzato sui computer Amiga. La serie numerica compands l’onda audio originale simile ai metodi logaritmici come μ-law.
Sono anche utilizzati nella pianificazione del poker, che è un passo nella stima in progetti di sviluppo software che utilizzano la metodologia Scrum.
Alcune di queste le vedremo in prossimi articoli.
Vediamo ora il codice per scrivere la sequenze di Fibonacci.
Useremo diversi metodi.
Quello che andremo a ottenere con i vari metodi sarà questo:
Ecco il codice:
Dim n1 As Integer
Dim n2 As Integer
n1 = 1
n2 = 1
Console.WriteLine("{0}", n1)
While n2 < FinoAQualeNumeroSiVuoleArrivare
Console.WriteLine(n2)
n2 = n2 + n1
n1 = n2 – n1
End While
Console.ReadLine()
Secondo metodo:
For i As Integer = 0 To QuantiNumeriScrivere
Console.WriteLine(Fibonacci(i))
Next
………..
Function Fibonacci(ByVal n As Integer) As Integer
Dim a As Integer = 0
Dim b As Integer = 1
‘ Add up numbers.
For i As Integer = 0 To n – 1
Dim temp As Integer = a
a = b
b = temp + b
Next
Return a
End Function
Terzo metodo:
Dim a As Integer = 0
Dim b As Integer = 1
Dim fib As Integer
Do
Console.WriteLine(a.ToString)
fib = a + b
a = b
b = fib
Loop While a <= FinoAQualeNumeroSiVuoleArrivare
Esistono poi altri metodi, ma non voglio diluire l’articolo.
Abbiamo visto quindi come “informatizzare” una serie numerica vecchia di 800 anni.
Alla prossima!
Leggi l'articolo intero | Make a Comment ( None so far )Ottenere i numeri primi
Con questo articolo inizia una serie di articoli su come risolvere i problemi matematici grazie all’aiuto dell’informatica e della programmazione e come applicare la matematica nell’informatica.
La matematica è una dei miei tanti hobby e risolvere problemi ed equazioni nei giorni di festa mi rilassa.
Oggi vediamo i numeri primi.
Come abbiamo imparato a scuola, il numero primo è un intero positivo maggiore di 1 divisibile solo per sé stesso e per 1.
Questi sono numeri primi: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 e così via.
Fin dall’antichità i grandi matematici cercarono di ottenere un metodo di calcolo veloce e preciso.
In questo articolo useremo il Crivello di Eratostene, scritto dal matematico, astronomo, poeta, filosofo e geografo greco Eratostene di Cirene (276 a.C. – 194 a.C.).
Il Crivello di Erastotene è un antico algoritmo per il calcolo delle tabelle di numeri primi fino a un certo numero prefissato.
Il procedimento è il seguente: si scrivono tutti i numeri naturali a partire da 2 fino n in un elenco. Poi si cancellano tutti i multipli del primo numero dell’elenco (escluso lui stesso). Si prende poi il primo numero non cancellato maggiore di 2 e si ripete l’operazione con i numeri che seguono, proseguendo fino a che non si applica l’operazione all’ultimo numero non cancellato. I numeri che restano sono i numeri primi minori o uguali a n.
Vediamo quindi di tradurre tutto questo in codice, io lo scrivo in VB.NET ma voi potete convertirlo facilmente in un altro linguaggio.
Questo elenco per noi sarà un vettore, un array. Se ad esempio vogliamo scrivere i numeri primi fino a 30 scriveremo a partire dal numero 2 fino a 30 in questo array.
Andiamo poi a tirare via tutti i multipli di 2 (i numeri pari non saranno mai primi perché divisibili per 2) escluso lo stesso 2.
La nostra lista diventa quindi 3,5,7,9,11,13,15,17,19,21,23,25,27,29
Dobbiamo ora eliminare i multipli di 3, quindi la lista diventerà: 2,3,5,7,11,13,17,19,23,25,29
Dobbiamo ora eliminare i multipli di 5, quindi la lista diventerà: 2,3,5,7,11,13,17,19,23,29
Dobbiamo ora eliminare i multipli di 7 ma non ce ne sono, quindi la lista sarà così.
Anziché andare a togliere, noi nell’array ci metteremo solo i numeri che non sono multipli dei precedenti.
Da 1 a 10 dobbiamo fare la verifica che non sia multiplo di 2, di 3, di 5 e di 7. Il 4, il 6, l’8 e il 9 non saranno considerati essendo già loro multipli di 2 (2 * 2= 4; 2 * 3 = 6; 2 * 4 = 8), e di 3 (3 * 3 = 9)
Vediamo il tutto con il codice. Ho creato 3 tipi di esempi:
1) Quanti numeri primi vogliamo visualizzare.
Questo è il codice:
Dim numeri As Integer = 10 ‘QUANTI NUMERI PRIMI VOGLIO TROVARE
Dim cur As Integer = 3
Dim divisore As Integer
Dim RadiceQuadrata As Integer
Console.WriteLine(2)
For a = 1 To numeri – 1
inizio:
RadiceQuadrata = Math.Sqrt(cur)
For divisore = 3 To RadiceQuadrata Step 2
If (cur Mod divisore) = 0 Then
‘quindi aumento di due il numero analizzato
‘(ottenendo il numero disperi successivo)
cur += 2
‘e ricomincio ad analizzare
GoTo inizio
End If
Next
‘se il risultato di nessuna divisione da 0
‘il numero è primo
Console.WriteLine(cur)
cur += 2
Next
E questo il risultato:
2) Fino a quale numero voglio arrivare a sapere se è primo:
Questo è il codice:
Dim numeri As Double = 99999999999999999 ‘QUANTI NUMERI PRIMI VOGLIO TROVARE
Dim numero As Integer = 50 ‘FINO A QUALE NUMERO VOGLIO TROVARE NUMERI PRIMI
Dim cur As Integer = 3
Dim divisore As Integer
Dim RadiceQuadrata As Integer
For a = 1 To numeri – 1
inizio:
RadiceQuadrata = Math.Sqrt(cur)
For divisore = 3 To RadiceQuadrata Step 2
If (cur Mod divisore) = 0 Then
‘quindi aumento di due il numero analizzato
‘(ottenendo il numero disperi successivo)
cur += 2
‘e ricomincio ad analizzare
GoTo inizio
End If
Next
‘se il risultato di nessuna divisione da 0
‘il numero è primo
If cur >= numero Then Exit For
Console.WriteLine(cur)
cur += 2
Next
E questo il risultato:
3) Il numero xxx è primo o no?
In questo caso non andremo a cercare i numeri primi, ma semplicemente dato un certo numero, si tratta di calcolare se è primo no.
Il codice è questo:
Dim cur As Integer = 37 ‘NUMERO DA CAPIRE SE è PRIMO O NO
Dim divisore As Integer
Dim RadiceQuadrata As Integer
Console.WriteLine(2)
Dim NumeroPrimo As Boolean = False
RadiceQuadrata = Math.Sqrt(cur)
For divisore = 3 To RadiceQuadrata Step 2
If (cur Mod divisore) = 0 Then
NumeroPrimo = False
Console.WriteLine(cur & " non è un numero primo.")
Exit Sub
End If
Next
‘se il risultato di nessuna divisione da 0
‘il numero è primo
NumeroPrimo = True
Console.WriteLine(cur & " è un numero primo.")
E questo il risultato:
Proviamo con altri numeri:
Sicuramente il codice si potrà migliorare, ma non è lo scopo dell’articolo. Lo scopo dell’articolo era capire come funzionano i numeri primi e come ottenerli. Ci sono anche altri metodi per ottenere numeri primi, la prima procedura che mi è venuta in mente è questa.
Vedremo eventualmente in successivi articoli come usare altri metodi.
Per ora è tutto.
Leggi l'articolo intero | Make a Comment ( None so far )
il Blog di Pieer11 