Subscribe: .NET at 9.400 ft above sea level
Language: English
Tags:
find  function  int  language  line  net  new  number  point  problem  project euler  return  sequence  solution  sum
Rate this Feed

Feed Details and Statistics
Preview: .NET at 9.400 ft above sea level

# .NET at 9.400 ft above sea level

## Programming in Quito, 2.860 m above sea level

A quick and dirty implementation of Excel NORMINV in F#

Mon, 09 Aug 2010 04:24:00 GMT

A couple of weeks ago I posted an example implementation of Excel NORMINV function in C#, in there I mentioned that what I actually needed was an F# version, but I used C# as an stepping stone moving from the C++ version I originally found. Well, here you have my attempt at implementing NORMINV in F#:let probit mu sigma p =    if p < 0. || p > 1. then failwith "The probability p must be greater than 0 and lower than 1"    elif sigma < 0. then failwith "The standard deviation sigma must be positive"    elif sigma = 0. then mu    else        let q = p - 0.5        let value =            if abs q <= 0.425 then          // 0.075 <= p <= 0.925                let r = 0.180625 - q * q                let a0, a1, a2, a3, a4, a5, a6, a7 =                     3.387132872796366608, 133.14166789178437745, 1971.5909503065514427, 13731.693765509461125,                    45921.953931549871457, 67265.770927008700853, 33430.575583588128105, 2509.0809287301226727                let b0, b1, b2, b3, b4, b5, b6, b7 =                     1., 42.313330701600911252, 687.1870074920579083, 5394.1960214247511077,                    21213.794301586595867, 39307.89580009271061, 28729.085735721942674, 5226.495278852854561                q*(((((((a7*r + a6)*r + a5)*r + a4)*r + a3)*r + a2)*r + a1)*r + a0)                    / (((((((b7*r + b6)*r + b5)*r + b4)*r + b3)*r + b2)*r + b1)*r + b0)            else                            // closer than 0.075 from {0,1} boundary                let r = sqrt -(log (if q > 0. then 1. - p else p))                let val1 =                     if r <= 5. then         // <==> min(p,1-p) >= exp(-25) ~= 1.3888e-11                 let a0, a1, a2, a3, a4, a5, a6, a7 =                      1.42343711074968357734, 4.6303378461565452959, 5.7694972214606914055, 3.64784832476320460504,                     1.27045825245236838258, 0.24178072517745061177, 0.0227238449892691845833, 7.7454501427834140764e-4                 let b0, b1, b2, b3, b4, b5, b6, b7 =                      1., 2.05319162663775882187, 1.6763848301838038494, 0.68976733498510000455,     &[...]

F#, the ACM, and the SEC

Fri, 06 Aug 2010 17:23:34 GMT

It all started with a twit from @mulambda: “Phil Wadler lists #fsharp as a candidate for SEC regulation spec language: http://tinyurl.com/2edfxka” I downloaded the, nonetheless, Association for Computer Machinery answer to the Securities and Exchange Commission proposal (and ask for comments) on requiring Python programs to be provided to explain contractual cash flow provisions. I quickly skimmed the ACM document and twitted “Java, C#, and F# recommended by the #ACM for SEC regulation spec language http://is.gd/e49Vt #fsharp /via @mulambda”. Later, I read with more care the ACM answer and I found that I really should clarify my twit: First of all, in no place the ACM explicitly recommends Java, C# or F# (sorry for my over-enthusiastic extrapolation ) What the document does do, is to put Java, C#, and F# in a (very?) positive light at several places: “Safe execution of code written by one party on a machine owned by a different party was not a strong concern in the design of Python. It was a strong concern in the design of other systems, including Java and the .Net framework (which supports multiple languages, including C#, F#, and Iron Python)” Page 4. “The widely accessible interpreted implementations of Python and Perl execute more slowly than compiled languages such as Java, C#, F#, and Scheme by as much as one or two orders of magnitude” Page 4. “Python has a specification written in English, but its specification has not received the same careful attention as those of Java or C#. Page 5 “Java, C#, and F# are designed to be executed efficiently, Python and Perl implementations are significantly less efficient” Page 6 “Statically typed languages are generally considered to produce more reliable and easier to maintain code, while dynamically typed languages are generally considered to produce more flexible code and to be better suited for prototyping. Java, C#, F# are statically typed; Python and Perl are dynamically typed” Page 6 The bolding is mine, this one is specially controversial but I for one (more like 1 cent) think it’s a good point. “Some programming languages have been designed with security in mind, and some of their implementations include “sandboxes” that can securely execute untrusted code. Java, C#, and F# are such languages; Python and Perl are not” Page 6 “Java and C# have had significant effort put into producing precise specifications; F#, Python, and Perl less so. SML and Scheme possess full formal mathematical specifications; F# is descended from SML” What the ACM does explicitly recommend (page 1): “Other programming languages may be more appropriate than Python” “Security should be enhanced by executing the code in a "virtual sandbox." ” “The SEC should consider developing a domain-specific programming language or library for writing waterfall programs.” And it is this last recommendation on DSLs that carries interesting news for F# because at the end of page 6 it states “Experience seems to show that higher-order programming languages such as F# provide a particularly good basis for domain-specific languages. There are financial domain-specific languages available in F#” . And for an encouraging ending in page 7, answering the question “Is it appropriate to require issuers to submit the waterfall computer program in a single programming language, such as Python, to give investors the benefit of a standardized process?”, the answer includes “Other choices, such as F#, may be more appropriate than Python” . So, I think I should really replace my original twit with something like this: Java, C#, and F# mentioned by the ACM as possibly better alternatives for the SEC regulation spec language. Furthermore, the ACM recommends the creation of a DSL and mentions F# as a good candidate for doing so. Finally, let me clarify that I have nothing against Python, on the contrary I like most of (the little I know o[...]

A quick and dirty implementation of Excel NORMINV function in C#

Thu, 29 Jul 2010 22:19:30 GMT

We are piloting the implementation of some financial risk models in F#, it so happens that the models are already implemented in Excel, so I was slowly digging out the formulas in the cells and translating them to F#. Everything was going fine until I found out that some formulas used the NORMINV function which doesn't exist in the .NET libraries. I started to look for F#, and then C#, implementations without luck (as we are just in the lets-see-if-this-have-any-chance-of-flying stage, we can’t afford any of the excellent but paid numerical libraries for .NET). The closest thing I found was a C++ implementation. The code looked really weird to me (my fault, not the coder's), so I decided to do the translation in two steps: first from C++ to C#, then on to F#. The C# translation seems to be working now, and you can download it from SkyDrive:

1. I am not an expert in statistics by any stretch of imagination
2. Ditto for numerical methods
3. I have made only a handful of very basic tests

Having said that, the function *seems* to be working so I hope it will help somebody (image) .

Scrum vs. CMMI Level 3

Wed, 28 Jul 2010 03:32:00 GMT

Of late, I have been helping start a Microsoft SDL implementation effort and, as part of it, it comes the decision of what flavor of MSF we should use: Agile (Scrum nowadays) or CMMI (roughly Level 3 with the Team Foundation Server template). Now, this is a corporate customer, expecting to have budgets and schedules defined in order to green light any sizeable project, so we naturally lean to CMMI but I can’t help remembering all the formal methodology implementation efforts I’ve seen (and sometimes helped ) fail (RUP, anyone?). So, after a few years, I am reading about the subject again, and in Chapter 7 “Effective Change Leadership for Process Improvement” of Michael West’s Real Process Improvement Using the CMMI (ISBN 0849321093), I find these pearls of wisdom on the behavior of top management: You are not exempt from the history or the statistically documented behavior patterns of your peer executives, you are not an exception, so here is what you’re going to say to the organization when it comes to CMMI or process improvement: We must get to CMMI Level (pick your number, 1 to 5) to remain competitive. I want everyone to support the CMMI effort. Your job (or promotion or performance review or raise, you choose) depends on your contribution to CMMI (or getting the maturity level). The long-term viability of our enterprise relies on our process capability, not on our individual heroics. These are our processes and I expect all of you to follow them. CMMI is really important to all of us and our future. I expect all of you to embrace change and do things differently. Those are the things you’ll say. Here is what you’re going to do or not do : When push comes to shove, when you are forced to choose between heroics and process to get the product out the door, you will choose heroics. You will reward the heroes, the people who work all night or all weekend to solve a customer problem. You will not reward the silent, humble engineer who puts quality first and prevents problems from ever getting to the customer. You will ask for status of the CMMI effort in terms of CMMI compliance. You will not ask for measures that indicate improvements in productivity, quality, cycle time, employee satisfaction, customer satisfaction, organizational learning, or other measures of operational excellence. You will not ask the process people to give you estimates for effort, cost, and schedule to achieve a CMMI maturity level. You will give them a target date that is tied to your bonus. You will tell the people who report to you that you want their support of the CMMI effort. You will not give them any incentive, positive or negative, for that support. You will not bother to learn the organizational processes yourself; they are for everyone else. You will not personally exhibit the change in behaviors you expect from others. Alas, as so many who have gone before you, you will fail. Oh, you will get your maturity level/bonus/promotion/raise/praise/plaque on the wall, but make no mistake, you will have failed in leading your organization to change and grow. So exactly and painfully true! I really don’t have an answer for the customer yet, but I will certainly read as much (and as fast) as I can of Michael book.[...]

Visual Studio 2010 and .NET Framework Beta 2 available on Wednesday

Mon, 19 Oct 2009 16:31:27 GMT

This blog has been abandoned for the longest time :-\$ but I’ve got great news to try and re-inaugurate it (again): it’s just been announced that beta 2 for Visual Studio 2010 and .NET Framework 4 will be available the day after tomorrow, i.e. on October 21st; moreover, we now have a firm date for the launch of the final versions of these products: March 22nd 2010. There is a lot of cool stuff in the new versions of Visual Studio and .NET Framework but my personal favorites (at least for the time being :-) are:

1. The inclusion of dynamic programming elements in C# and other framework languages. Good things from languages like Python, Groovy, or Ruby are now an integral part of C#.
2. The inclusion of F# as a first level language of the .NET Framework, welcome functional programming to the most popular commercial development platform on the planet!
3. A new version of Entity Framework, making the oficial .NET ORM tool more flexible and adequate. Less and less, we’ll need to code SQL by hand and laboriously move data from tables to objects and viceversa.

As I said, there’s a lot of cool stuff in Visual Studio 2010 and .NET Framework 4, but I plan to start using those three things as soon as possible in customer projects, after all, to have success stories by March 2010, we have to start working before this year ends.

Distance between adjacent points in F#

Fri, 13 Mar 2009 04:57:18 GMT

Let’s say you are given a list of data points:

[7;5;12;8;5]

And you are asked to find the distance between every adjacent pair, that is:

[(7-5);(5-12);(12-8);(8-5)] = [2;-7;4;3]

It turns out that there is an elegant solution to this problem:

let rec pairs = function
| h1 :: (h2 :: _ as tail) -> (h1, h2) :: pairs tail
| _ –> []

let distances dataPoints =
dataPoints |> pairs |> List.map (fun (a, b) -> a - b)

The magic happens in the pairs function, this function takes [7;5;12;8;5] and turns it into [(7,5);(5,12);(12,8);(8,5)], that is, it creates a tuple with every member of the list and its right neighbor. The trick is that tail gets bounded  to ( h2 :: _ ), so that the recursive call processes the list starting with h2. This is called a named subpattern, something I discovered in section 1.4.2.2 of F# for Scientists. You learn at least a nice thing every day!

Entity Framework, LINQ to SQL and Oracle

Tue, 18 Nov 2008 05:24:23 GMT

Amid the debate about which is better and have more future (two things that not necessarily go together) between LINQ to SQL and Entity Framework, one thing they have in common is the fact that Oracle is in “no comment” mode about both of them. It’s like Oracle would be expecting that the lack of its “official” provider for Entity Framework, let alone LINQ to SQL, would somehow move people to develop in Java instead of .NET Framework. IMHO, Visual Studio 2008 is so productive that people may first consider moving from Oracle to SQL Server before moving from VS 2008 to JDeveloper.

Luckily, .NET Framework has a big ecosystem of developers and ISV’s: enter Devart, a software house in Russia or Ukraine –I’m not sure. They’ve been offering for a while now an Entity Framework provider for Oracle, I have had the chance to use it with Oracle 10g with good success. The good news is that a few days ago they released new versions of all of its providers (changing their names while at it), including dotConnect for Oracle 5.00. Even more intriguing, this new version includes a LINQ to SQL provider for Oracle, something supposedly so complex to do that it would have taken a long time before it even existed. To be fair, I haven’t already used this last provider, but the very fact that it’s available is exciting. Now Oracle friendly Visual Studio 2008 developers (no, that’s not an oxymoron at all) has two good paths to follow. Let the debate begin!

Free F# libraries (well, almost)

Tue, 11 Nov 2008 05:36:08 GMT

In what was one of the very last PDC2008 sessions, Luca Bolognese did an encore presentation of F#, instead of trying to tell you what it was all about I invite you to watch the video (Luca is engaging and funny, and the session is so packed with information that one our will pass in no time). What I wanted to do is to talk about a couple of very interesting libraries, all written in F#, that Luca used in his demos:

(image) F# for Numerics offers a bunch of numerical analysis functions, things like matrix operations, integration and differentiation, statistical methods, maximization and minimization, Fourier transforms, you know, the stuff we all love about maths [:P].

(image) F# for Visualization allows us to visualize functions in 2D as well as 3D, including animations and PNG export. Believe me, the graphs really look good.

If you are hesitant about this, Jon Harrop, the man behind the libraries is offering free licenses of both libraries, well, with the usual banners and watermarks reminding you that you should really buy the real thing. Not that they are expensive either: you can get both by around US\$ 100.

Personally, I feel a really sweet smell from the very fact that these libraries exist: a great symptom of a language or technology readiness for the market is that libraries from third parties start to appear (as, for example, has happened in the last months with WPF, but that’s the matter for another blog entry…)

While we are on the subject, and for those of you who are really intrigued by scientic applications, I strongly suggest you to take a look to F# for Scientists, the book where Jon tells us how to use F# in this field.

(image)

Point distance, imperative vs. functional style

Fri, 19 Sep 2008 03:58:34 GMT

Let’s consider a silly simple algebra problem: given a specific point and a set of several other points, find the closest point in the set to the given point. One C# solution is:     1     static class PointMath     2     {     3         static double Distance(Point p1, Point p2)     4         {     5             double xDist = p1.X - p2.X;     6             double yDist = p1.Y - p2.Y;     7             return Math.Sqrt(xDist * xDist + yDist * yDist);     8         }     9     10         public static Point ClosestPoint(Point p, IList points)    11         {    12             double shortestDistance = Double.PositiveInfinity;    13             Point closestPoint = null;    14     15             foreach (var point in points)    16             {    17                 double distance = Distance(p, point);    18                 if (distance < shortestDistance)    19                 {    20                     shortestDistance = distance;    21                     closestPoint = point;    22                 }    23             }    24     25             return closestPoint;    26         }    27     } The Distance() function finds the distance between two points with good ol’ Pythagoras, the ClosestPoint() function does the classic loop: traverse the points list and calculate every distance, if you find a smaller one, keep it and the also keep the current point, at the end return the last point you kept. Easy, but with declarations, curly braces and whatnot, the solution takes 27 lines, OK, 14 lines if we ignore the blank lines and the curly-braces-only lines. And we didn’t even show the Point class definition… Can we do any better? What about this F# solution:     1 let distance (x1, y1) (x2, y2) : double =     2   let xDistance = x1 - x2     3   let yDistance = y1 - y2     4   sqrt (xDistance * xDistance + yDistance * yDistance)     5      6 let closestPoint toPoint fromPoints = List.min_by ([...]

The first Visual F# CTP is here!

Mon, 01 Sep 2008 04:35:20 GMT

You leave on vacation for one short week and a lot happens... for example, Don Syme & co. have released the first F# CTP, well on the way (hopefully before this year's end) to put F# on the same level as C#, C++ or VB.NET. As far as I know, this will be an historical event: for the first time a mainstream platform (commercial or otherwise) wholly adopts a functional language. Allow me to seize the occasion to reiterate that there are several reasons for the functional programming paradigm to be considered interesting important, IMHO the most relevant are: The usage of high level functions and lazy evaluation allows us to reach higher levels of abstraction and modularization, which eases the programming of the ever more complex problems that we face. The extensive use of immutable values and structures greatly paves the way to code execution parallelization, which is especially relevant in today's multi-core CPU world. Functional thinking adapts particularly well to the solution of math problems (be them symbolic or numeric). Well, this last point may not have as broad reach as the former, but it is especially fascinating and useful for mathematicians and scientists (which in more than a few cases have had to stick to FORTRAN or use very specialized products like Matlab or Mathematica). For reasons like these, functional programming has steadily invaded the programming scenario, for example: C# 3.0 has lambda and higher level functions (or a subset, at least, sort of...) and lazy evaluation (LINQ anyone?) In the Java world, people is starting to consider Scala, a functional language for the JVM There's renewed interest in specialty languages like Erlang (used at Ericsson to forge extremely scalable and reliable systems) F# will be a first class citizen in the .NET Framework world An example of the F# September CTP running on my Visual Studio 2008 SP1: If anybody is wondering what this code does, fibonacciSequence generates the Fibonacci numbers up to a given maximum, and the second function adds the even terms of the sequence up to a given limit. It's a succinct solution for Problem 2 @ Project Euler (and it would be interesting for you to try and solve it in your favorite language). It's all quechua to you? Well, that's just a matter of getting to know the language :-), IMHO the best way to learn F# is following the Expert F# book, co-authored by the language's father himself. Furthermore, Microsoft has put online the language official site, the F# Developer Center, where you will find several other resources. By the way, it seems like the official name of the release will be Visual F# 1.0 (which actually corresponds to Version 2, counting from its inception at Microsoft Research). Finally, Visual F# requires only .NET 2.0, and an intriguing consequence of this is that you will be able to run F# code on Linux, thanks to the Mono  project, that is, you will have an open source functional programming platform, courtesy from Microsoft (and Novell).[...]

F# 1.9.4.19 runs out of the box with Mono in Linux

Tue, 15 Jul 2008 04:25:39 GMT

Don Syme just announced a minor update to the F# environment, minor may be but of great interest to a certain community: it so happens that at some point F# stopped working properly in Linux, a workaround was published (and it actually works, but you've got to follow the instructions carefully). Well, not anymore, 1.9.4.19 works out of the box with Mono in Linux, you just have to download it, unzip it, and then happily type "mono fsi.exe":

So now I've got one less pretext for not writing that book "Learning to program the functional way in an open source environment using a cool Microsoft technology" that will make me famous...

Cloning objects in .NET

Sun, 18 May 2008 06:27:38 GMT

In an interesting project where I'm giving a hand, we need to clone objects of a number of different types, perhaps surprisingly the CLR doesn't offer a general cloning method, of course you could use MemberwiseClone() but this is a protected method, so it can be invoked only from inside the class of the object being cloned, which makes it difficult to use it in a general method, besides, MemberWiseClone() does just a shallow copy and what we really need is a deep copy. There is a good reason for not having such a general method: object cloning is one of those problems which have a simple solution for simple scenarios but that resist a satisfactory solution for all the scenarios, for example the objects may have references to other objects and even to themselves be it directly or after a long chain, for example a customer has invoices that have payments that refer to the customer, a general cloning algorithm for a web several times more complex than that is anything but trivial. But the need of moving objects (and their web) is inescapable in distributed environments, because you have to move the invoices and the customers from the business layer to the presentation layer, so there are indeed mechanisms, albeit with some limitations, for serializing and deserializing object graphs, with the help of these mechanisms we can try and build a general object cloner:     1      2     public static T BinaryClone(this T originalObject)     3     {     4         using (var stream = new System.IO.MemoryStream())     5         {     6             var binaryFormatter = new System.Runtime.Serialization.Formatters.Binary.BinaryFormatter();     7             binaryFormatter.Serialize(stream, originalObject);     8             stream.Position = 0;     9             return (T)binaryFormatter.Deserialize(stream);    10         }    11     }    12  We just convert, using as intermediary a memory stream, our object to a bit string and then we synthesize a *new object* from that bit string. The use of BinaryClone() flows nicely:     1      2     var clone = person.BinaryClone();     3  Easy to write, but we have to be careful of the performance and the corner cases. I run a few *very informal* performance tests with this object:     1      2     var person = new Person     3     {     4         Id = 101,     5         Name = "Sánchez, Sebastián",     6         Salary = 590.20m,     7         BirthDate = new DateTime(2000, 6, 15),     8         Address = new Address { Number = "N24-78", Street = "Pasaje Córdova" }     9     };    10  And I found th[...]

A cool way to find out whether a number is palindromic

Tue, 06 May 2008 06:40:08 GMT

In this blog entry I proposed a solution to Problem 4 at Project Euler, a crucial element of the problem is to find out whether a number is a palindrome (909 is, 809 isn't), a bit out of laziness and a bit in order to reuse existing methods, I decided to verify the palindrome by converting the number into a char array and then comparing this array with its mirror version, it works but it's not really that mathematical... Dustin Campbell proposed a solution kind of similar to mine (alas, more elegant and, above that, in F#) and using the same trick of converting the number to chars, as he didn't like this part of the solution, in this new blog entry he proposes the detection of a palindrome by mirroring the number one digit at a time. A translation of his F# code to C# 3.0 could be:

1     Func<int, int, int> TailReverseNumber = null;

2     TailReverseNumber = (n, res) => n == 0 ? res : TailReverseNumber(n / 10, 10 * res + n % 10);

3

4     Func<int, bool> IsPalindrome = n => n == TailReverseNumber(n, 0);

TailReverseNumber takes a number n and "mirrors" it, one digit at a time, for example: TailReverseNumber(237, 0) -> TailReverseNumber(23, 7) -> TailReverseNumber(2, 73) -> TailReverseNumber(0, 732), the big trick is that res works as an accumulator that is multiplied by 10, therefore moving its value to the left, and putting in the "hole" that appears at the right the least significant digit of n. As it names implies, TailReverseNumber() uses tail recursion, so that no extra call stack space is used to save any intermediate results, which makes the process pretty efficient. Actually, in my PC it's four times faster than the initial solution. More efficient and more elegant, a smart guy Dustin.

New version of F# just released

Sat, 03 May 2008 06:26:07 GMT

In its way from research language to commercial language, Don Syme just announced that, silently, on May the 1st version 1.9.4.15 of F# was released.

This new version incorporates a number of specific enhancements (F# is now basically in stabilization mode, so we really shouldn't expect significative changes to the language). By the way, the example in the picture shows my idea for solving Problema 2 of Project  Euler: find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million. For an explanation of how it works, I suggest you this Dustin Campbell blog, which proposes a solution similar to mine with a couple of elegant touches and, above all, with a detailed and engaging explanation.

Which is the ten thousand first prime?

Fri, 02 May 2008 05:09:56 GMT

Prime numbers have a good deal of practical applications (for example in cryptography) but let's face it, even if they would have none, they would still be the favorite toy of mathematicians. In Problem 7 of Project Euler, we are asked to find the 10001st element of the famous list, my approach was this: Define the *infinite* sequence of the prime numbers From this sequence, throw away the first 10000 items and then take the first of the remaining Creating an infinite sequence in C# is easy (since version 2) thanks to IEnumerables and, above all, the yield statement:     1 IEnumerable Primes()     2 {     3     yield return 2;     4      5     var primesSoFar = new List();     6     primesSoFar.Add(2);     7      8     Func IsPrime = n => primesSoFar.TakeWhile(p => p <= (int)Math.Sqrt(n)).FirstOrDefault(p => n % p == 0) == 0;     9     10     for (int i = 3; true; i += 2)    11     {    12         if (IsPrime(i))    13         {    14             yield return i;    15             primesSoFar.Add(i);    16         }    17     }    18 } The yield at line 3 returns the first item of the sequence: the always excepcional 2 (the only even prime). Then at line 5 we create a list where we will be saving the generated primes as we progress in the sequence (this way we will gain speed at the cost of memory). The IsPrime(n) function defined at line 9, proposes a method -pretty crude actually- of verifying whether a number is prime: we take all primes generated so far which are lower or equal than the square root of n, and we look for the first among them that divides n evenly, if such a divisor exists then n is not a prime, that is: if none of the primes already generated is an exact divisor of n then FirstOrDefault() returns a 0, signaling the fact that n is indeed a prime. Finally at line 10 starts the loop that, every time the Prime() invoker asks for an item, it progresses thru 3, 5, 7, 9, 11, 13, ... stopping and returning, thru yield, when it finds a new prime. With this sequence in our hands, step 2 of my plan is utterly simple: return Primes().Skip(nth - 1).First(); We take the Primes() sequence, ignore the first nth - 1 (in our case nth = 100001) and then take the first of the remaining. This little code returns the answer in far less than a second.[...]

The square of the sum vs. the sum of the squares

Mon, 28 Apr 2008 02:56:32 GMT

The sixth Project Euler problem poses an exercise that, to me, offers no major hurdles: What is the difference between the sum of the squares and the square of the sums [of a sequence of natural numbers]? The functional C# solution is fairly easy to write and read:     1     public int SquareSumsLessSumSquares(IEnumerable sequence)     2     {     3         var sum = sequence.Sum();     4         var sumSquares = sequence.Select(i => i * i).Sum();     5         return sum * sum - sumSquares;     6     } We get any sequence of integers (list, array, etc.) and we find the sum of its elements at line 3. The Select() in line 4 generates a new sequence with the square of each item from the original sequence and then we add them up. From there, getting the answer to Problem 6 is easy. Actually, the specific value that the problem asks for is to find out this difference for the first 100 natural numbers, so the corresponding call is:     var result006 = SquareSumsLessSumSquares(Enumerable.Range(1, 100)); Now, given that the sequence we are focused on is 1, 2, 3, ..., 100, we can leverage a couple of math formulas:   y   Isn't the Wikipedia something? With this information in our hands we can re-write our solution this way:     1     public int SquareSumsLessSumSquaresFirstNumbers(int n)     2     {     3         var sum = n * (n + 1) / 2;     4         var sumSquares = n * (n + 1) * (2 * n + 1) / 6;     5         return sum * sum - sumSquares;     6     } Clearly this latter way of solving the problem uses far less memory and CPU time. My first solution follows what is called a "brute force" approach, contemption intended. It works, for sure, but there are more elegant and efficient ways of solving the problem. The moral of this story is that a little research can take us a long way towards fresh solutions, probably better than our first approach. How frequently have you seen brute force solutions in production environments?[...]

Recursive lambdas and sequence aggregations

Thu, 24 Apr 2008 05:22:45 GMT

The fifth problem at Project Euler proposes this nostalgic primary school exercise: find the smallest quantity that is evenly divisible by some numbers, the least common multiple of 1, 2, 3, ..., 20 to be precise. To begin with, let's remember the old arithmetic formula:

(image)

Where gcd is the greatest common divisor of a and b. It's also useful to remember that the lcm is associative, that is lcm(1,2,3) is the same as lcm(lcm(1,2), 3), in other words, we can calculate the lcm of 1 and 2, then the lcm of this result and 3, then the lcm of this result and 4, and so on. In functional C#, these ideas can be expressed like so:

1     Func<int, int, int> gcd = null;

2     gcd = (x, y) => x % y == 0 ? y : gcd(y, x % y);

3

4     return Enumerable.Range(1, 20).Aggregate(1, (x,y) => x * (y / gcd(x, y)));

Line 2 finds the gcd of x and y like this: if the remainder of dividing x by y is zero, then y is the gcd, if not, we must find the gcd of y and such remainder. Note that gcd is defined recursively. The only interesting point here is that in order to define a recursive lambda expression, it is mandatory to first declare the expression variable (which we do in line 1), and only after this the compiler allows us to define a lambda expression in terms of itself. Odd, granted, but easy to get used to.

Line 4 takes the sequence 1, 2, ..., 20 and accumulates the lcm as the sequence is traversed, that is: it starts calculating lcm(1, 1) (let's call this accum1), then it calculates lcm(accum1, 2) (let's call this accum2), then it calculates lcm(accum2, 3), ..., and finishes with lcm(accum19, 20) which is precisely lcm(1, 2, ..., 20). The Aggregate() function is frequently used for chores like adding each term of a sequence, or multiplying them all, in our case we are using Aggregate() to get the succesive lcm's, which answers the question of Project Euler in two and a half lines of code, cool, eh?

Nested sequences and palindrome numbers

Tue, 22 Apr 2008 06:41:44 GMT

Problem 4 of Project Euler poses and impractical albeit intriguing problem: given all three digit numbers (100, 101, 102, ..., 998, 999), find the largest product of 2 of those numbers, where the product is a palindrome. For example, 580.085 is the product of two three-digit numbers (995 x 583) but it isn't the largest of such products. One possible functional C# solution is:

1     Func<int,bool> IsPalindrome = n => { var nchar = n.ToString().ToCharArray(); return nchar.SequenceEqual(nchar.Reverse()); };

2

3     return Enumerable.Range(100, 900)

4         .SelectMany(i => Enumerable.Range(i, 900 - (i - 100)).Select(j => i * j))

5         .Where (p => IsPalindrome(p))

6         .Max();

To begin with, let's focus on the interesting part: at line 3, Enumerable.Range() generates the sequence 100, 101, ..., 998, 999; SelectMany() at line 4 does several things, first for every number i from the previous line it generates the sequence i, i + 1, i + 2, ..., 998, 999, and then the inner Select() generates the products {100 x 100, 100 x 101, ..., 100 x 999}, {101 x 101, 101 x 102, ..., 101 x 999 }, ... As you can see, there are 999 sequences generated (are all the same size?) finally SelectMany() kindly "flattens" those 999 sequences in one large sequence containing each and every product; line 5 then is easy, the Where() just keeps those products that are palindromes; the Max() in line 6 isn't worth any explanation.

Back to line 1, I took the lazy path to check whether a number is a palindrome: I just converted it to a string and then to a char array, finally I checked whether that array is equal, item by item, to its reversed version (and all that work just to leverage IEnumerable.Reverse() ;-)

Finding the largest prime factor of a number

Sat, 19 Apr 2008 05:40:00 GMT

This is another classic problem at Project Euler that can be solved with the old trick of top down programming, like so:      PrimeFactors(number).DefaultIfEmpty(number).Max(); It's a nice solution, supposing PrimeFactors() actually returns all prime factors of any given number. But before getting there, it's a good idea to discuss what DefaultIfEmpty() is doing there. The thing is that somebody could make this innocent call: PrimeFactors(1), which of course returns an empty collection, which in turn makes PrimeFactors(1).Max() throw an exception (trying to get the maximum out of nothing, eh?) DefaultIfEmpty(x) to the rescue: when DefaultIfEmpty(x) is applied to a "reasonable" collection it returns it untouched, but when it's applied to an empty collection it returns a new collection with just un item: x. So, in our case, PrimeFactors(1).DefaultIfEmpty(1).Max() is just a looooong alias for 1. DefaultIfEmpty() is very useful for those special cases with empty collections. With that behind, let's see how we get all the prime factors of a number:     1     IEnumerable PrimeFactors(ulong number)     2     {     3         Func FindDivisor = n => n == 1UL ? 1UL : CandidateFactors(n).First(c => n % c == 0);     4      5         var factors = new HashSet();     6         while (number > 1UL)     7         {     8             ulong divisor = FindDivisor(number);     9             factors.Add(divisor);    10             number /= divisor;    11         }    12     13         return factors;    14     } At line 3 we define a function (we are using lambdas just for fun) that finds a divisor for a number, for example FindDivisor(45) returns 3 and FindDivisor(49) returns 7. The workhorse is the while loop starting on line 6, it starts with a number, let's say 45, find the divisor 3, saves it in factors and goes on with 15 (45 / 3), now it finds a divisor for 15, in this case 3 again, saves it in factors and goes on with the 5 (15 / 3), and so on and so on until all is left is a 1. Meanwhile factors has been accumulating 3, 5, etc.: the prime factors of the original number. An interesting detail is that factors is a set, so it doesn't have any duplicates. Finally let's check the CandidateFactors() definition:     1     IEnumerable CandidateFactors(ulong n)     2     {     3         yield return 2UL;     4         for (ulong candidate = 3UL; candidate <= n; candidate += 2UL)     5             yield return candidate;     6     } As you can see, this function simply produces the sequence 2, 3, 5, 7, 9, ..., n which ar[...]

Project Euler and infinite sequences in C#

Thu, 17 Apr 2008 08:10:25 GMT

The second problem at Project Euler proposes:

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.

One way of solving this problem is by defining an endless sequence in C#. Something along these lines:

IEnumerable<int> FibonacciSequence()

{

int n1 = 0;

int n2 = 1;

while (true)

{

int n3 = n1 + n2;

yield return n3;

n1 = n2;

n2 = n3;

}

}

The FibonacciSequence() function returns the next value in the sequence everytime its execution hits the yield statement, and conveniently enough, n3 gets the values 1, 2, 3, 5, 8, ... in each next round of the loop. It's notable that the loop never finishes by itself, this responsability actually belongs to the code invoking FibonacciSequence(). So in fact we are seeing a way of representing an infinite set (all Fibonacci numbers) in C#. In our case we need all elements no bigger than 4'000.000, so we can write something like this:

FibonacciSequence().TakeWhile(n => n <= 4000000).Where(n => n % 2 == 0).Sum()

The TakeWhile() method stops asking for more terms as soon as an item bigger than four millions is produced, afterwards the Where() method leaves us with a sequence containing only the even terms, and these terms are finally added up by Sum().