Project Euler – Problema 5

Ecco la soluzione al problema 5 in Haskell:

divisibilefinoan (x, n)
|n==1 = if(x `mod` n)==0 then True else False
|otherwise = if(x `mod` n)==0 then divisibilefinoan (x, (n-1)) else False

loop n = if(divisibilefinoan (n, 20)) then n else loop (n+2)

– Ottimizzazione per far partire il loop che verifica se è divisibile fino a quel numero
– da un punto più avanzato: il numero che cerchiamo sarà sicuramente >2520 (che è multiplo
– di tutti i numeri fino a 10), comprenderà i fattori 11, 13, 17 e 19 (che sono numeri primi
– compresi tra 10 e 20) e un fattore 2 aggiuntivo (dovuto a 16, che è due alla quarta,
– mentre il due compariva al massimo con esponente 3 in otto). Praticamente equivale a
– risolverlo a mano.
result = loop (2520*11*13*17*19*2)

Il testo del problema:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Project Euler – Problema 7

Riporto la soluzione al problema 7 in Haskell:

–Controlla se un numero è primo
isprime 2 = True
isprime t = if (filter (==0) (map (t`mod`)[2.. ceiling(sqrt (fromIntegral t))])==[]) then True else False

findnextprime x = if(isprime(x+1)) then x+1 else findnextprime(x+1)

addnextprime xs = [findnextprime (head xs)] ++ (xs)

milleeuno xs = if (length xs==10001) then head xs else milleeuno(addnextprime xs)

result = milleeuno [2]

Testo del problema:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13.

What is the 10001^st prime number?

Project Euler – Problema 10

Riporto la soluzione al problema 10 in Haskell:

–Controlla se un numero è primo
isprime 2 = True
isprime t = if (filter (==0) (map (t`mod`)[2.. ceiling(sqrt (fromIntegral t))])==[]) then True else False

listadeiprimi = [x|x<-[3, 5..2000000], isprime x]
listaprimi = 2 : listadeiprimi
result = sum listaprimi

Il programma non è ottimizzato: è stato fatto in un paio di minuti ed è molto migliorabile.

Il testo del problema:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Project Euler – Problema 3

Riporto la soluzione in Haskell al terzo problema del Progetto Eulero:

n = 600851475143
–Controlla se un numero è primo
isprime 2 = True
isprime t = if (filter (==0) (map (t`mod`)[2.. ceiling(sqrt (fromIntegral t))])==[]) then True else False

– Risolve il problema
– N.B: L’algoritmo riporta solo i fattori primi, non l’esponente a cui compaiono
fattoriprimi = [x|x<-[x|x<-[2..ceiling((fromIntegral n)/2)], (n `mod` x)==0], isprime x]
result= maximum fattoriprimi

N.B: Testare il risultato può rihiedere molto tempo. Se e quando avrò tempo ottimizzerò il programma .

Ecco il testo del problema:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Project Euler – Problema 2

Riporto la soluzione al secondo problema del Progetto Eulero, in Haskell:

– Definizione dell’infinita lista dei numeri di Fibonacci (vantaggio della programmazione funzionale)
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
– Somma di tutti i numeri di Fibonacci minori di quattro milioni e pari (lista per proprietà)
result = sum [x|x<- takeWhile (<4000000) fibs, even x]

Ed ecco il testo del problema:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Riferimenti: http://www.haskell.org/~pairwise/intro/section1.html (per la lista di Fibonacci)

Verificare l’allineamento di una variabile (alignment) – C/C++

In inglese viene chiamato memory alignment, ed è la proprietà di un dato (una variabile in memoria) di iniziare a un indirizzo multiplo di una certa quantità di bit.Per esempio, una variabile può essere allineata a 8, 16 o 32 bit. Questo significa che l’indirizzo di memoria in cui la variabile è collocata è un multiplo di 8, 16, o 32 bit.

Nelle architetture moderne, ogni dato è sempre allineato ad almeno 8 bit, per il semplice motivo che il computer non riesce a indirizzare una quantità di memoria inferiore (infatti il computer vede la memoria suddivisa in byte, non in gruppi di bit o in singoli bit). Se il dato, supponiamo un int, è allineato a 32 bit, allora un suo indirizzo in memoria potrebbe essere, plausibilmente, 0×000044440, 0×000044444, 0×000044448 (da notare gli incrementi di 4 alla fine, che indicano un incremento di 4 byte, ovvero di 32 bit).

Esistono due metodi per verificare facilmente se una variabile è allineata o meno a un dato valore.

Il primo, il più diretto e semplice, richiede di usare l’operatore di modulo (% in C e C++). Si tratta semplicemente di prendere l’indirizzo di una variabile (con l’operatore &, o senza operatore & se si tratta di un puntatore) e fare il modulo con il valore desiderato. Se il risultato è zero, vuol dire che l’indirizzo è un multiplo esatto di quel valore e la variabile risulta allineata. In termini di codice:

int* a;

if  !( a % 32) {/* La variabile è allineata */}  // Attenzione a testare con l’operatore NOT davanti

Il secondo metodo invece è più efficiente,e sfrutta un trucco dell’aritmetica booleana. Si tratta di usare l’operatore AND con una maschera di bit che abbia tanti 1 impostati quanto è il numero a cui dobbiamo elevare 2 per ottenere il valore di allineamento. In parole più semplici, se dobbiamo allineare a 8 bit, la maschera sarà 111, a 16 sarà 1111, a 32 sarà 11111 (due alla quinta) e così via (un interessante applicazione di ciò è che per testare se un numero è pari basta fare AND con 1). Attenzione, le maschere sono in codice binario, vanno riconvertite nel formato usato per codificare l’indirizzo: se si tratta di esadecimale, per 8 bit 0×7, per 16 0xf, per 32 0×20. Il codice risulta:

int*a;

if !( a & 0×20) { /* La variabile è allineata a 32 bit */ }

E’ dunque possibile verificare l’allineamento con una sola riga di codice. A cosa serve però controllare l’allineamento? Si tratta di prestazioni: il computer può accedere alla memoria solo per blocchi, e l’allineamento garantisce che le variabili non inizino a metà blocco, costringendo il calcolatore a laboriose operazioni di recupero dell’informazione. Alcuni esempi pratici che mostrano l’uso dell’allineamento sono alcune implementazioni della funzione memcpy() e le istruzioni SSE.

Fonti:

http://cboard.cprogramming.com/cplusplus-programming/118471-fast-checking-alignment.html
http://www.undolog.com/2008/05/31/loperazione-aritmetica-modulo/
http://stackoverflow.com/questions/1054657/memory-alignment-on-a-32-bit-intel-processor
http://www.embedded.com/shared/printableArticle.jhtml?articleID=19205567

Project Euler – Problema 6

Riporto la soluzione al problema 6 in F#:

#light

(*Somma dei quadrati: “mappa” la funzione quadrato sui numeri da 1 a 100, e poi ne fa la somma
passando il risultato a List.sum*)
let sumofsquares = List.map (fun x -> x*x) [1 .. 100] |> List.sum

// Quadrato della somma: eleva al quadrato la somma.
let squareofsum = List.sum [1 .. 100]* List.sum [1 .. 100]

// Differenza tra quadrato della somma e somma dei quadrati
printf “%A” (squareofsum – sumofsquares)

Mentre ecco una versione in Haskell:

sommaquadrati = sum [(x*x)|x<-[1..100]]

quadratosomma = (sum [1..100])*(sum[1..100])

result = quadratosomma – sommaquadrati

Come al solito, se ci sono domande basta chiedere.

Ecco il testo del problema:

The sum of the squares of the first ten natural numbers is,

1² + 2² + … + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Project Euler – Problema 1

Riporto la soluzione in F# elaborata da me per questo problema:

// Sintassi semplificata
#light

// Funzione filtro, che rimuoverà i multipli di 5 dai multipli di 3
let filter x =
if(x%5<>0) then true
else false

// Lista con i multipli di 3 (sintassi tipica di F#)
let n3 = List.filter filter [3 .. 3 .. 999]
// Lista con i multipli di 5 (sintassi tipica di F#)
let n5 = [5 .. 5 .. 999]

(* Unione delle due liste (quella dei multipli di 3 è già “epurata” dai multipli di 5)*)
let n = List.append n3 n5

// Somma di tutti gli elementi della lista
let sum = List.sum n

(* Stampa a schermo del risultato (%A è il marcatore generico per qualunque tipo di dato)*)
printf “%A” sum

Se il codice dovesse aver bisogno di ulteriori spiegazioni, non esitate a chiedere.

Aggiornamento 27-08-2009:

In seguito a un interessamento verso Haskell come linguaggio di programmazione funzionale puro (almeno un po’ più di F#) sono riuscito a riscrivere il programma in questione in una sola riga, sfruttando la capacità di generare liste da regole.

main = print ( sum [x | x<-[1..999], (x `mod` 3 ==0) || (x `mod` 5 ==0)] )

Bisogna poi aggiungere l’istruzione print per visualizzare il risultato, ma comunque resta un grande passo avanti dalla prima versione del programma, che non era del tutto in “paradigma funzionale”. Comunque per correttezza ho rivisto anche la versione in F#, equivalente a quella in Haskell già riportata:

let n = [for x in [1..999] do if (x%3=0) || (x%5=0)then yield x]

// Stampa a schermo del risultato (%A è il marcatore generico per qualunque tipo di dato)
printf “%A” (List.sum n)

Ecco il testo del problema:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

F# – Programmazione funzionale

Leggendo l’articolo su Wikipedia riguardo Visual Studio 2010, ho scoperto che nella prossima versione verrà incluso questo nuovo linguaggio di programmazione (F#)  che proviene dalla divisione Research della Microsoft.

Questo linguaggio si propone come l’anello di congiunzione mancante tra la programmazione imperativa, ad oggetti e funzionale. Inoltre è costruito sul .Net, quindi ha una vasta e solida libreria di supporto (anche per quanto riguarda il comparto grafico).

Mi sono avvicinato a questo linguaggio per via del suo aspetto funzionale, e inizio a scorgere le sue potenzialità (per esempio la gestione delle liste, un altro pianeta rispetto a linguaggi come il C). Sto cercando di impararlo con un approccio pratico, risolvendo i problemi del progetto Euler.

Secondo me questo linguaggio avrà un valore inestimabile in ambito scientifico (vedi libri come F# for sicentists), ma avrà poca diffusione in ambito gestionale (per costruire applicazioni “Office-like” C# resta ancora il migliore). D’altronde il paradigma funzionale secondo me non si presta benissimo alla costruzione di GUI.

Project Euler

Su questo sito è possibile trovare interessanti quesiti matematici che richiedono l’ausilio di un linguaggio di programmazione per essere risolti.

Si tratta di implementare dei programmi che possano trovare il risultato delle operazioni descrittte, possibilmente nella maniere più diretta ed efficiente. Qualunque linguaggio può essere usato, dal C al Python, passando per i vari Visual Basic & co. Alla fine viene verificato soltanto la correttezza del risultato, perciò non importa come viene implementato il programma.

Per adesso sto utilizzando F#, perchè è mia intenzione imparare un po’ di programmazione funzionale. Questo linguaggio si presta particolarmente alla risoluzione di questi problemi, essendo appunto orientato alle funzioni e dotato di un supporto intrinseco alle liste, gestibili molto flessibilmente (almeno rispetto a linguaggi come il C).

Pubblicherò alcune soluzioni di questi problemi, ma la rete è già comunque piena di soluzioni a questi problemi in molti linguaggi (e molto più sofisticate delle mie),