Peck's Blog - All Comments

re: Solving Problems in C# and F# - Part 1

GordonBGood — Sat, 05 Mar 2011 06:41:03 GMT

RE: Solutions to Euler Problem 10...

While this study is interesting as a comparison between the languages, neither version is really efficient as to maximum speed. The choice to use the bit packed array of BitArray for both solutions for the prime sieve is one made to save space (by a factor of eight in this case), where for this problem of the primes up to two million, the use of two million bytes for modern machines is not a consideration. If space were a consideration, one would at least do the slight modifications so that one only sieves for the odd primes of three and up for a saving of half the space. BitArray operations are about 3.5 times slower than byte boolean operations.

If elegance of code is a consideration, one would likely write the F# code more in line with that of the current C# code as in;

let Solve () = GetPrimes 1999999 |> Seq.sum

Further, if speed and elegance were desired, one would only run the Sieve culls up to the square root of the maximum number tested, as there will be no culling of composite numbers done past that point, and all prime finding operations may as well be in 32-bits with only the summing taking place for 64-bits.

If general speed, space requirements, and elegance are all to to satisfied, one might use the following F# code, which solves the problem 10 using about one million bytes of memory in a small fraction of a second on a modern personal computer:

let GetOddPrimes max =

let LSTNDX = (max - 3) / 2

let LSTCULNDX = (int (sqrt (double max)) - 3) / 2

let inline prime i = i + i + 3

let inline strtndx i = ((prime i * prime i) - 3) >>> 1

let buf = Array.create (LSTNDX + 1) true

seq {0 .. LSTCULNDX}

|> Seq.filter (fun i -> buf.[i])

|> Seq.iter (fun j -> seq {strtndx j .. prime j .. LSTNDX} |> Seq.iter (fun j -> buf.[j] <- false))

seq {0 .. LSTNDX} |> Seq.filter (fun i -> buf.[i]) |> Seq.map (fun i -> i + i + 3)

let Solve () = (GetOddPrimes 1999999 |> Seq.map uint64 |> Seq.sum) + 2UL

Although small, simple and elegant, the above code is still many times slower than using a pure imperative code solution using loops rather than IEnumerable (as implied by using sequences) due to the extra overhead of calling the methods of the interfaces; this is even worse for the current CTP 2.0 version of F#, which still has a very inefficient Core run time library that implements these interface methods with multiple extra virtual method calls in order to generalize the use of the sequence objects; C#, while still slower than using loops, is considerably more optimized. While this isn't so important for a trivial problem such as this, larger problems such as calculating the number of primes in the 32 bit number range would be quite slow compared to using imperative techniques.

Peck s Blog MS UK s Solution Build Framework SBF on GotDotNet | debt solutions

Peck s Blog MS UK s Solution Build Framework SBF on GotDotNet | debt solutions — Fri, 19 Jun 2009 19:19:38 GMT

PingBack from http://debtsolutionsnow.info/story.php?id=11514

Peck s Blog Microsoft Office Live Small Business | Paid Surveys

Peck s Blog Microsoft Office Live Small Business | Paid Surveys — Fri, 29 May 2009 02:25:21 GMT

PingBack from http://paidsurveyshub.info/story.php?title=peck-s-blog-microsoft-office-live-small-business

Discoveries This Week 04/03/2009

Rick Minerich's Development Wonderland — Sun, 05 Apr 2009 04:43:23 GMT

With the start of our F# User’s Group this next Monday and New England Code Camp 11 last weekend , things

Discoveries This Week 04/03/2009

Rick Minerich's Development Wonderland — Sun, 05 Apr 2009 04:43:22 GMT

With the start of our F# User’s Group this next Monday and New England Code Camp 11 last weekend , things

Solving Problems in C# and F# - Part 2 - Peck

DotNetShoutout — Wed, 01 Apr 2009 12:55:06 GMT

Thank you for submitting this cool story - Trackback from DotNetShoutout

re: Solving Problems in C# and F# - Part 2

Martin Peck — Wed, 01 Apr 2009 10:32:30 GMT

I've put an updated version of C# solution here...

http://blogs.msdn.com/mpeck/archive/2009/04/01/update-to-solving-problems-in-c-and-f-part-2.aspx

Solving Problems in C# and F# - Part 2

Peck's Blog — Wed, 01 Apr 2009 10:31:43 GMT

UPDATE: It's been pointed out that the extension method RaiseToThePowerOf isn't required. I've updated

re: Solving Problems in C# and F# - Part 2

Martin Peck — Wed, 01 Apr 2009 10:13:57 GMT

@bistok - Thanks! I hadn't spotted it because it's a static method on BigInt and not an instance method.

re: Solving Problems in C# and F# - Part 2

bistok — Wed, 01 Apr 2009 09:06:07 GMT

You don't need to write the RaisedToThePowerOf the BigInt have the Method Pow ;)

Solving Problems in C# and F# - Part 2

Peck's Blog — Wed, 01 Apr 2009 02:20:19 GMT

This is part one of a three part post where myself and Giles Knap play around with C# and F# to see if

Let’s Wax Functional 03/06/2009

Rick Minerich's Development Wonderland — Sun, 08 Mar 2009 02:38:46 GMT

This week we have MapReduce, WebTools and yet another F# to C# language comparison. I spent yesterday

re: Solving Problems in C# and F# - Part 1

Martin Peck — Thu, 05 Mar 2009 02:08:34 GMT

@kfarmer. Thanks for the ideas.

Re your Enumerable.Range suggestion: It looks good, and I like the style of the code. I've written a version of GetPrimes that uses this code. It annoys me that Enumerable.Range only deals with int as I need to work with long here. I might create my own version of Range.

Any code that gets rid of the for loops is good for me.

Solving Problems in C# and F# - Part 1 - Peck's Blog

DotNetShoutout — Wed, 04 Mar 2009 16:31:54 GMT

Thank you for submitting this cool story - Trackback from DotNetShoutout

re: Solving Problems in C# and F# - Part 1

Keith Farmer — Wed, 04 Mar 2009 02:09:24 GMT

And maybe this for your triangle function:

Enumerable

.Range(0, int.MaxValue)

.Aggregate(0, (total, i) => total + i)

I haven't actually tested any of these (juggling), but they should work, or be close to working. Of course, it brings you closer to functional programming, which is of course F#'s realm.

re: Solving Problems in C# and F# - Part 1

Keith Farmer — Wed, 04 Mar 2009 02:01:35 GMT

I think this should be another way to cast GetDivisors, and should be able to take advantage of the Parallel Extensions (adding .AsParallel() after the call to .Range):

var max = (int)Math.Sqrt(value);

Enumerable

.Range(0, max)

//.Select(x => max - x) // not needed, since algorithm is order independent .. parallelizable with PLINQ

.Where(i => value % i == 0)

.SelectMany(i => new[] { i, value / i });

re: Solving Problems in C# and F# - Part 1

Keith Farmer — Wed, 04 Mar 2009 01:54:34 GMT

In problem 10, have you considered using the Aggregate operator? IIRC, you should be able to use it to do the equivalent of F#'s fold, passing in an object to represent the calculation state. The difficulty is in trying to get your sieve and the prime split apart, but it could be interesting seeing you can do it.

http://msdn.microsoft.com/en-us/library/system.linq.enumerable.aggregate.aspx

One (top of my head) that doesn't use Aggregate:

var nonPrimes = new bool[max + 1];

Enumerable

.Range(2, max - 1)

.Where(i => !nonPrimes[i])

.Select(i =>

{

for (var j = i * i; j <= max; j += i) { nonPrimes[j] = true; }

return i;

});

re: WCF Training

TechEditor — Tue, 06 Jan 2009 21:22:22 GMT

Another phenomenal training resource is Intertech. Andrew Troelsen delivers a WCF training course (http://www.intertech.com/Courses/Course.aspx?CourseID=99331).

Andrew is a best-selling author and has written about six different books on .NET. I've attended some of his workshops and he's a top notch presenter.

Not Writing Code is Great : EasyCoded

Not Writing Code is Great : EasyCoded — Mon, 06 Oct 2008 22:54:09 GMT

PingBack from http://www.easycoded.com/not-writing-code-is-great/

Better Basketball » Giles and Nats Have Left The Building (almost)

Better Basketball » Giles and Nats Have Left The Building (almost) — Sun, 20 Apr 2008 05:44:42 GMT

PingBack from http://www.basketballs-sports.info/better-basketball/?p=318

MSDN Blog Postings » SDC Tasks Updated on CodePlex

MSDN Blog Postings » SDC Tasks Updated on CodePlex — Thu, 28 Feb 2008 07:03:31 GMT

PingBack from http://msdnrss.thecoderblogs.com/2008/02/28/sdc-tasks-updated-on-codeplex/

BioSensorAB » SDC Tasks Updated on CodePlex

BioSensorAB » SDC Tasks Updated on CodePlex — Thu, 28 Feb 2008 05:37:55 GMT

PingBack from http://www.biosensorab.org/2008/02/27/sdc-tasks-updated-on-codeplex/

BioSensorAB » SDC Tasks Updated on CodePlex

BioSensorAB » SDC Tasks Updated on CodePlex — Thu, 28 Feb 2008 05:37:44 GMT

PingBack from http://www.biosensorab.org/2008/02/27/sdc-tasks-updated-on-codeplex/

re: Microsoft Mediaroom Developers Conference 2007

Martin Peck — Thu, 25 Oct 2007 12:32:47 GMT

Sorry. I'm afraid it wasn't recorded. I'm sure my fans are bitterly disappointed, but if you imagine the best ASP.NET presentation you've ever seen then it's was something like that - only with an British accent. ;-)

re: Microsoft Mediaroom Developers Conference 2007

cpoxon — Thu, 25 Oct 2007 12:25:31 GMT

Can it be viewed online anywhere? Would love to watch you in action! :-P