Claudio Cherubino's blog Life of a Googler

28Dec/080

Random testing in F# with FsCheck

One of the emerging trends in software development is TDD or Test-Driven Development, a methodology based on writing tests first and then coding in order to pass the tests.

Besides unit testing libraries inherited by the .Net Framework, F# can now count on FsCheck, a random testing framework cloned from Haskell's QuickCheck.

A random testing library generates a set of test cases and attempts to falsify the properties defined by the developer.

This approach is not exhaustive but if all the tests of large enough test suite are passed we can safely assume that the code is correct.

Let's see how to get started using FsCheck to validate the RSA implementation written some time ago.

The first step is to download the latest release (currently 0.3) of FsCheck from the Download page.

You can either get the binaries or the source code, that also contains an example console application.

Assuming that you downloaded the binaries, you have then to open/create an F# application and add a Reference (Project - Add Reference) to the FsCheck.dll library file:

Project referencing FsCheck library

Project referencing FsCheck library

In order to use the methods provided by FsCheck we have to include its namescope into our code by adding a open FsCheck clause at the beginning of our program.

For the sake of example, let's fix the two distinct random prime numbers p and q and the public exponent e.

We have then to define our first property, that I'm going to call prop_rsa, which basically asserts that decrypting a message that was previously encrypted we get back the original message.

In order to run a property prop_myproperty we just have to run quickCheck myproperty, so in this case we'll run quickCheck prop_rsa.

#light
open System
open FsCheck

// RSA sample data
let p = 61
let q = 53
let e = 17
let n = p * q
let d = private_exponent e p q

let prop_rsa message =
  let encrypted = encrypt message e n
  decrypt encrypted d n = message

quickCheck prop_rsa

Console.ReadKey() |> ignore

If everything goes well, we should see a console window like the following one, with the number of tests passed (by default, FsCheck generates 100 test cases).

FsCheck shows the number of passed tests

FsCheck shows the number of passed tests

If a test fails, FsCheck will stop the execution and show which test failed. If you want to see all the generated test cases, you can run verboseCheck instead of quickCheck.

The next step should be writing a custom generator in order to generate not only the message but also the prime numbers and the public exponent, but I think we can cover that in a future post.

You can download the complete solution here.

22Dec/080

Soddisfazioni da informatico

Vedere il proprio nome nei credits di un software importante come Songbird costituisce sicuramente una soddisfazione impagabile per chi come me vede l'informatica non solo come lavoro ma anche come grande passione:


songbird_credits

Vi ricordo che è stata rilasciata la versione 1.0 di Songbird, l'avete provata?

Avete commenti/suggerimenti/lamentele?

17Dec/081

Project Euler in F# – Problem 55

As in the last post, in the description of Project Euler problem 55 there is a detailed step-by-step solution of the problem itself and we just have to write the F# code to perform the tasks.

The only thing that I really had to understand is the definition of Lychrel numbers:

If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

As usual, it is suggested to break down the problem into little pieces that can be easily solved with a few lines of code each.

First, we need a function to reverse an integer and another one to check whether a number is palindromic, i.e. it is equal to its reverse.

Then we define a function that will be used during each iteration to take a number and sum it with its reverse. This new number is the one that will be checked next for being a palindrome inside the isLychrel function.

If we found a palindrome then the number under testing is not a Lychrel, otherwise we can start the next iteration up to a maximum of 50 times. If we hit this limit then we can conclude the number is a Lychrel.

We have now all the pieces required to answer the original question. Just take all numbers smaller then 10000, filter the Lychrel ones and count them:

#light

let reverse n =
  n.ToString().ToCharArray()
  |> Array.rev
  |> Array.map (fun x -> x.ToString())
  |> Array.reduce_left (^)
  |> bigint.Parse

let isPalindromic n =
  n = reverse n

let reverseAndAdd n =
  n + reverse n

let isLychrel n =
  let rec isLychrelIter n i =
    match i with
    | 50 -> true
    | _ ->
      let r = reverseAndAdd n
      if isPalindromic r then
        false
      else
        isLychrelIter r (i+1)
  isLychrelIter n 1

let answer = [1I .. 10000I]
             |> Seq.filter (fun x -> isLychrel x)
             |> Seq.length
15Dec/081

Wordle, la nuova tag cloud

Poco più di un anno fa vi spiegavo come inserire una tag cloud all'interno del vostro blog basato su WordPress, ma da allora le mode sono cambiate e pare che adesso non ci sia blogger che si sia convertito a Wordle.

Di cosa si tratta?

Sostanzialmente si tratta di una variante della tag cloud che è basata su tutte le parole di un sito e non solo i tag.

Per generarlo basta andare sul sito Wordle.net e indicare l'indirizzo del proprio sito o feed.

L'applicazione, realizzata come applet Java, genererà rapidamente il wordle e successivamente sarà possibile personalizzarlo variando font, colori e altre impostazioni.

L'unico problema è che non è prevista alcuna possibilità di esportazione del risultato ottenuto, ma saremo costretti a catturare lo schermo per salvare l'immagine.

Ho provato a far analizzare questo blog ed ecco il risultato ottenuto:

Wordle

Bello, no? Peccato che non abbia ancora capito a che possa servire! :???:

7Dec/081

Project Euler in F# – Problem 53

Some of the problems proposed by Project Euler actually present the solution together with the description of the problem itself.

This is the case with Problem 53:

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, ^(5)C_(3) = 10.

In general,
^(n)C_(r) =
n!

r!(n?r)!
,where r ? n, n! = n×(n?1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: ^(23)C_(10) = 1144066.

How many, not necessarily distinct, values of ^(n)C_(r), for 1 ? n ? 100, are greater than one-million?

The only knowledge required in this problem is the binomial coefficient, but its formula is also described in the text above, so we can simply generate all couples (n, r) and check if the value of the binomial coefficient is greater than one million.

In F# this is equivalent to coding a function for the binomial coefficient and testing the items of a sequence:

#light
open Microsoft.FSharp.Math

let binomial_coefficient n k = BigInt.Factorial n /
                               (BigInt.Factorial k * BigInt.Factorial (n-k))

let answer =
  seq { for n in 1I .. 100I do
          for k in 1I .. n -> n,k } |> Seq.filter (fun (a,b) -> binomial_coefficient a b > 1000000I ) |> Seq.length

The approach adopted is almost the same that I used to solve Project Euler problem number 9. It is not the smartest nor the quickest since it is essentially a brute-force algorithm, but without any doubt it is the easiest to implement.

Which optimizations would you consider?

1Dec/082

Implementation of RSA in F#

During my university course I had to learn and use two functional programming languages: Haskell and Scheme. I fell in love with the former but I never managed to do the same with the syntax of Scheme and the incredibly huge number of parenthesis you have to type in order for your code to work!

That's why I decided to steal borrow a short implementation of the RSA algorithm written in Scheme and translate it into F#.

As you may know, RSA is an algorithm used for public-key encryption based on prime numbers and factorization that is widely use on the web to secure e-commerce transactions.

At the end of the following code there is also a working example that can be executed to better understand the steps required to encrypt and decrypt a message (in this case a single number):

#light
// Modulus operator that handles negative numbers correctly
let modulus n m =
  ((n % m) + m) % m

// Greater Common Divisor
let rec gcd a b =
  match b with
  | b when b = 0 -> a
  | b -> gcd b (a % b)

// extended_gcd = (x,y), such that a*x + b*y = gcd(a,b)
let rec extended_gcd a b =
  if (a % b = 0) then
    (0, 1)
  else
    let (x, y) = extended_gcd b (a % b)
    (y, x - y * (a / b))

// modulo_inverse(a,n) = b, such that a*b = 1 [mod n]
let modulo_inverse a n =
  let (x, y) = extended_gcd a n
  modulus x n

// totient(n) = (p - 1)*(q - 1),
// where pq is the prime factorization of n.
let totient p q = (p - 1) * (q - 1)

// square(x) = x^2
let square x = x * x

// modulo-power(base,exp,n) = base^exp [mod n]
let rec modulo_power b exp n =
  if (exp = 0) then
    1
  else
    if (exp % 2 = 1) then
      (((modulo_power b (exp - 1) n) * b) % n)
    else
      ((square (modulo_power b (exp / 2) n)) % n)

// RSA routines.

// A legal public exponent e is between
// 1 and totient(n), and gcd(e,totient(n)) = 1
let is_legal_public_exponent e p q =
  (1 < e) && (e < (totient p q)) && (1 = (gcd e (totient p q)))

// The private exponent is the inverse of the public exponent, mod n.
let private_exponent e p q =
  if (is_legal_public_exponent e p q) then
    modulo_inverse e (totient p q)
  else
    raise (new System.Exception("Not a legal public exponent for that modulus"))

// An encrypted message is c = m^e [mod n]
let encrypt m e n =
  if (m > n) then
    raise (new System.Exception("The modulus is too small to encrypt the message"))
  else
    modulo_power m e n

// A decrypted message is m = c^d [mod n]
let decrypt c d n =
  modulo_power c d n

// RSA example.
let p = 61
let q = 53
let n = p * q
let e = 17
let d = private_exponent e p q
let message = 123
let c = encrypt message e n
let m = decrypt c d n

I think the code presented is self-explainatory and each function is briefly described in the comments, but there is a strange thing that you may have noticed.

The first function I defined is the modulus operator, but F# already has a modulus operator, so why bothering?

Before writing that function I was about to getting crazy, since everything else was already written but the encryption was not working properly. I debugged and tested again and again and eventually I found out that sometimes the result of the native modulo operation was a negative number.

After a short lookup on Wikipedia, I discovered that each programming language implements the modulo operator differently and while in Scheme the result has the same sign as the divisor, in F# the sign of the result is the same as the dividend!