Walking Randomly

I know it’s a day late but someone just sent me this and I simply had to share so please indulge me.  Solve this inequality to find the love

9x-7i>3(3x-7u)

I am having a friendly argument with a colleague over how you calculate the peak number of floating operations per second (flops) for devices that support Fused Multiply Add (FMA).  The FMA operation is d=a+b*c, an operation that can be done in one cycle on devices that support it.

I say that an FMA operation is two flops, he says it’s one.  So, when I calculate the theoretical peak of a device I get twice the value he does.  So, what do you think..is FMA one flop or two?

I like the StackOverflow range of question and answer sites and have hopped on and off them almost since the very beginning.  When I logged in recently I was informed that one of my questions had been awarded the ‘Famous Question’ badge..i.e. it had been viewed over 10,000 times.  The relevant question was Python blogs that you regularly follow? which was asked by me in the very early days of the site. Not only has it received 63 community up-votes and over 10,000 views but it’s also been closed as ‘Not constructive’ by senior members of the Stack Overflow community.

I find this contrast amusing!

xkcd is a popular webcomic that sometimes includes hand drawn graphs in a distinctive style.  Here’s a typical example

In a recent Mathematica StackExchange question, someone asked how such graphs could be automatically produced in Mathematica and code was quickly whipped up by the community.  Since then, various individuals and communities have developed code to do the same thing in a range of languages.  Here’s the list of examples I’ve found so far

• xkcd style graphs in Mathematica. There is also a Wolfram blog post on this subject.
• xkcd style graphs in R. A follow up blog post at vistat.
• xkcd style graphs in LaTeX
• xkcd style graphs in Python using matplotlib
• xkcd style graphs in MATLAB. There is now some code on the File Exchange that does this with your own plots.
• xkcd style graphs in javascript using D3
• xkcd style graphs in Euler
• xkcd style graphs in Fortran

Any I’ve missed?

I felt like playing with Julia and MATLAB this Sunday morning.  I found some code that prices European Options in MATLAB using Monte Carlo simulations over at computeraidedfinance.com and thought that I’d port this over to Julia.  Here’s the original MATLAB code

function V = bench_CPU_European(numPaths)
%Simple European
steps = 250;
r = (0.05);
sigma = (0.4);
T = (1);
dt = T/(steps);
K = (100);

S = 100 * ones(numPaths,1);

for i=1:steps
 rnd = randn(numPaths,1);
 S = S .* exp((r-0.5*sigma.^2)*dt + sigma*sqrt(dt)*rnd);
end
V = mean( exp(-r*T)*max(K-S,0) )

I ran this a couple of times to see what results I should be getting and how long it would take for 1 million paths:

tic;bench_CPU_European(1000000);toc
V =
   13.1596
Elapsed time is 6.035635 seconds.
>> tic;bench_CPU_European(1000000);toc
V =
   13.1258
Elapsed time is 5.924104 seconds.
>> tic;bench_CPU_European(1000000);toc
V =
   13.1479
Elapsed time is 5.936475 seconds.

The result varies because this is a stochastic process but we can see that it should be around 13.1 or so and takes around 6 seconds on my laptop. Since it’s Sunday morning, I am feeling lazy and have no intention of considering if this code is optimal or not right now. I’m just going to copy and paste it into a julia file and hack at the syntax until it becomes valid Julia code. The following seems to work

function bench_CPU_European(numPaths)

steps = 250
r = 0.05
sigma = .4;
T = 1;
dt = T/(steps)
K = 100;

S = 100 * ones(numPaths,1);

for i=1:steps
 rnd = randn(numPaths,1)
 S = S .* exp((r-0.5*sigma.^2)*dt + sigma*sqrt(dt)*rnd)
end
V = mean( exp(-r*T)*max(K-S,0) )
end

I ran this on Julia and got the following

julia> tic();bench_CPU_European(1000000);toc()
elapsed time: 36.259000062942505 seconds
36.259000062942505

julia> bench_CPU_European(1000000)
13.114855104505445

The Julia code appears to be valid, it gives the correct result of 13.1 ish but at 36.25 seconds is around 6 times slower than the MATLAB version.  The dog needs walking so I’m going to think about this another time but comments are welcome.

Update (9pm 7th October 2012):   I’ve just tried this Julia code on the Linux partition of the same laptop and 1 million paths took 14 seconds or so:

tic();bench_CPU_European(1000000);toc()
elapsed time: 14.146281957626343 seconds

I built this version of Julia from source and so it’s at the current bleeding edge (version 0.0.0+98589672.r65a1 Commit 65a1f3dedc (2012-10-07 06:40:18). The code is still slower than the MATLAB version but better than the older Windows build

Update: 13th October 2012

Over on the Julia mailing list, someone posted a faster version of this simulation in Julia

function bench_eu(numPaths)
    steps = 250
    r = 0.05
    sigma = .4;
    T = 1;
    dt = T/(steps)
    K = 100;

    S = 100 * ones(numPaths,1);

    t1 = (r-0.5*sigma.^2)*dt
    t2 = sigma*sqrt(dt)
    for i=1:steps
        for j=1:numPaths
            S[j] .*= exp(t1 + t2*randn())
        end
    end

    V = mean( exp(-r*T)*max(K-S,0) )
end

On the Linux partition of my test machine, this got through 1000000 paths in 8.53 seconds, very close to the MATLAB speed:

julia> tic();bench_eu(1000000);toc()
elapsed time: 8.534484148025513 seconds

It seems that, when using Julia, one needs to unlearn everything you’ve ever learned about vectorisation in MATLAB.

Update: 28th October 2012

Members of the Julia team have been improving the performance of the randn() function used in the above code (see here and here for details).  Using the de-vectorised code above, execution time for 1 million paths in Julia is now down to 7.2 seconds on my machine on Linux.  Still slower than the MATLAB 2012a implementation but it’s getting there.  This was using Julia version  0.0.0+100403134.r0999 Commit 099936aec6 (2012-10-28 05:24:40)

tic();bench_eu(1000000);toc()
elapsed time: 7.223690032958984 seconds
7.223690032958984

• Laptop model: Dell XPS L702X
• CPU:Intel Core i7-2630QM @2Ghz software overclockable to 2.9Ghz. 4 physical cores but total 8 virtual cores due to Hyperthreading.
• RAM: 8 Gb
• OS: Windows 7 Home Premium 64 bit and Ubuntu 12.04
• MATLAB: 2012a
• Julia: Original windows version was Version 0.0.0+94063912.r17f5, Commit 17f50ea4e0 (2012-08-15 22:30:58).  Several versions used on Linux since, see text for details.

One of my hobbies is retro video games and tonight’s opening ceremony for the 2012 Olympics inspired me to take a look at Olympic video games over my lifetime.  Where games were released on multiple platforms I’ve simply chosen the one that was most relevant to me.

Video Olympics (Atari VCS2600, 1977)

Released in the year of my birth, the Atari VCS-2600 holds a special place in my heart.  The hardware was incredibly primitive and yet some of the games were surprisingly playable.  I must have spent weeks of my childhood playing Combat for instance.  Sadly,Video Olympics is one of the less playable games for the 2600 and should really be renamed ‘Variations on the theme of Pong.’

• Wikipedia page for Video Olympics
• Video review of Video Olympics on Youtube

Hyper Sports (Arcade, 1984)

One of my abiding memories of the early 80s was spending Sunday afternoons in the children’s room of our village’s local pub.  This particular village pub was a geek child’s paradise as the kids room included up to 3 arcade games at any one time.  My brother and I would be given 20p each to play on these games, a sum of money that would be expected to last us at least an hour, while dad enjoyed a quiet pint in the bar.

I remember Konami’s Hyper Sports very clearly and the youtube above brings back a flood of memories for me.  Hyper Sports was released in time for the 1984 Los Angeles  Olympics and was the sequel to Konami’s superb Track and Field.

Micro Olympics (BBC Micro, 1984)

If you had walked into any UK primary school in the early 80s you’d have found a BBC Micro, an 8 bit computer developed by Acorn Computers (the guys who went on to develop the ARM processor used in the vast majority of mobile devices).  My primary school had exactly one of these high powered beasts and each pupil only got a few minutes on it a month on average.  I remember that my dad had a chat with the head master though and scored me a lot of extra time on it.  As long as I didn’t make any noise whatsoever, I could use the computer just outside the headmasters office for an hour after school and I used the time to work through my collection of Marshall Cavendish Input magazines.  Happy days.

The BBC wasn’t known for its games however.  Micro Olympics was rubbish!

Daley Thompson’s Olympic Challenge (Sinclair Spectrum, 1988)

Ahhh the humble speccy— Oh how I loved thee!  The spectrum was my first ‘proper’ computer and I received it for my 8th birthday.  All I wanted to do was play games but my father insisted that I also learn how to program it and so I probably owe my career to dear old dad and Sinclair’s 48K wonder.

Released in time for the 1988 Seoul Olympics, Daley Thompson’s Olympic Challenge was a joystick waggler pure and simple.  The game included several events: 100 metres, Long Jump, Shot Putt, High Jump and 400 metres, 110 metres Hurdles, Discus, Pole Vault, Javelin and 1500 metres but gameplay consisted of nothing more than frantically waggling your joystick side to side and occasionally pressing the fire button.

• Daley Thompson’s Olympic Challenge on World of Spectrum
• Review from Your Sinclair in November 1988

Olympic Gold (Sega MegaDrive, 1992)

I remember reading articles that previewed Sega’s megadrive.  Back then its power seemed nothing short of astonishing but, sadly, I didn’t have one.  One of my friends, however, did have one and many a happy hour was spent over at his house playing Mortal Kombat and Sonic the Hedgehog.

Olympic gold was the first officially licensed Olympic video game and was released in time for the Barcelona Olympics.  Although the graphics are much better than older games, the game mechanic is essentially exactly the same, mash buttons as fast as you can.

1996 and beyond

By the time the 1996 Atlanta games came around, I had better things to do than play video games.  That summer was my last before starting my undergraduate studies in theoretical physics.  Many Olympic video games have since been released of course but I haven’t played them and neither do I want to.

So, I’ll hand over to The Complete History of Official Olympic Video Games which picks up where I left off.

A friend recently asked me how to optimally tile the shape below on the plane such that no two instances touch.

Off the top off my head I suggested considering the minimal enclosing circle and then pack hexagonally but he thinks one could do better. I thought I’d ask on here to see what others might come up with.

I work in a beautiful old building at The University of Manchester called The Sackville Street Building.  Yesterday, I took part in a very interesting historical tour of the building and was astonished at the amount of beautiful things that I had never noticed before and yet walk past every day.

For example, I was delighted to discover that one of the stained glass windows in the great hall was themed around mathematics (thanks to Samantha Bradey for the original image which I’ve heavily compressed for this blog post)

While on the tour I posted a quick snap of the above window to twitter using my mobile phone and received some nice feedback along with a  few pictures of other mathematical windows.  It turns out that Manchester’s Nick Higham has a close up of the above window for example.  Also, Kit Yates tweeted about several mathematical windows in Caius College, Cambridge, one of which is below (showing images related to Venn and Fisher).

Do you know of any other examples of mathematics in stained glass?  Feel free to contact me and tell me all about it.

These days almost all of us are carrying around seriously capable little computers in the form of our mobile phones.  Although these devices have a similar amount of horsepower to supercomputers of old, most of us only use a fraction of their potential– after all, you don’t need a supercompter to send text messages, look at pictures of cats or throw birds at pigs.  I believe that the only way to fully unlock the true potential of these devices is to program them yourself.

From fully fledged applications to little snippets of code, I think that there’s something enormously satisfying about writing your own computer programs and it doesn’t have to be difficult to do so.  The following 9 apps will allow you to write programs for your Android mobile phone in a variety of languages including C, BASIC, Lisp and MATLAB m-code using only your Android phone. Although you’ll not be able to use them to write the next 3D blockbuster game, you will be able to solve some interesting problems, learn a trick or two and have a lot of fun.

C4droid – £0.95

With c4droid you get the ability to write, compile and run C and C++ programs using only your Android device.  That’s a lot of functionality for only 95p!

Out of the box C4droid only handles C programs, making use of a modified version of the Tiny C Compiler to do the compilation work.  The standard C library is provided by uClibc which is specially designed for use on embedded systems.

In order to run C++ programs you need to additionally install the free GCC plugin for C4droid — something that I personally haven’t done yet due to its large size.  One of the most common user-complaints appears to be ‘this app doens’t allow me to use iostream.h’ which essentially demonstrates that the installation instructions were not followed.  Since iostream.h is a C++ library, you’ll need to install and configure the GCC plugin to get access to it and full instructions on how to do this are given on c4droid’s Google Play page.

You only get access to the standard C library with C4droid which means that you can’t generate graphical output or interact with the phone’s hardware in any way (bluetooth, accelerometers, that sort of thing) but that doesn’t stop this from being an impressive piece of work.  Also, for an extra 95p you can run pascal programs using the Pascal plugin for C4droid.

C4droid is a superb app that will be invaluable for anyone learning C,C++ or Pascal or for those of us that simply like to fiddle about with these languages on the go.

• C4droid on Google Play
• GCC plugin for c4droid (needed for C++ access)
• Pascal plugin for C4droid – provides the ability to compile and run Pascal programs

Mintoris Basic – £3.77

At the risk of showing my age, I’ll tell you that I first learned how to program in BASIC (Beginners All-Purpose Symbolic Instruction Code) on the Sinclair ZX Spectrum and so I will always have a fondness for the language.  Mintoris Basic is a very fully featured implementation of the BASIC programming language and is significantly more powerful than the implementation I cut my teeth on back in the day.

As well as having all of the stuff you’d expect in a BASIC implementation (loops, strings, variables, functions, decisions, graphics etc), Mintoris also allows you to interact with some of your phone’s hardware including Bluetooth, battery level, GPS, and various sensors.  Furthermore, you can attach your programs to shortcuts and launch them from your home screens.  The level of functionality is so high that you can write some rather nifty apps with relatively little effort.

• Get Mintoris Basic from Google Play
• Mintoris Basic official website
• Mintoris Basic Forum
• Mintoris Basic on Facebook

Frink – Free

Frink is a great language developed by Alan Eliasen that has been around since 2001.  Named after Professor Frink from The Simpsons, Frink runs on almost every device you can possibly imagine and has some very interesting features including interval arithmetic, tracking of units of measure throughout calculations, arbitrary precision numbers, regular expressions and graphics.

• Get Frink from Google Play
• What’s new – Frink is under very active development.  See here for the new stuff
• Many example programs in Frink
• Extensive documentation for Frink

RFO BASIC! + SQL – Free

This implementation of BASIC is completely free and is described as a labour of love by the author, Paul Laughton.  Paul is my kind of geek since he is the curator of The Dr. Richard Feynman Observatory and author of Atari Basic and Apple DOS 3.1 among other things.

The feature list of RFO BASIC is impressive and includes Graphics (with Multi-touch), SQL, GPS, Device Sensors, Camera and loads more.  There’s a great forum with lots of very engaged developers who are writing some very nice programs.

There are two ways to deploy your programs–either as scripts that require RFO BASIC to be installed or as compiled,standalone programs that can even be added to Google Play (formerly known as the Android Market’).

• RFO BASIC on Google Play
• RFO BASIC Forum
• RFO BASIC website
• De Re BASIC! – The .pdf manual for RFO BASIC

Addi and Mathmatiz – Free

These are two MATLAB clones for Android.  I’ve mentioned Addi before and they have both been covered over at Alasdair’s Musings so I won’t go into detail here other than to say that they are very cool!  Linear algebra, scripting and plotting on your phone!

• Addi at Google Play
• Mathmatiz at Google Play
• Mathmatiz on Facebook

tiny Lisp ISLisproid

Lisp is a very old programming language which first saw the light of day in 1958!  According to wikipedia, the only langauge older than Lisp that is still in common use is Fortran! With this app you can play with the language of the ancients on your super-modern smartphone.  This is a no-frills app..essentially little more than a command line shell and list interpreter but that is perhaps as it should be.

• tiny Lisp at Google Play

MathStudio – £12.99

I’ve been using MathStudio (formerly SpaceTime Mathematics) for quite a few years now on various operating systems and it’s great to finally have it on Android.  MathStudio is a fully featured computer algebra system for your mobile phone– think mini Mathematica or Maple and you are thinking along the right lines.  With this app you can write scripts that make use of advanced mathematical features,  2D and 3D graphics, animations and interactive demonstrations.

• MathStudio at GooglePlay
• MathStudio official website
• A set of MathStudio examples and demonstrations
• MathStudio Forum

SigmaScript – Free

SigmaScript is a free implementatuion of the Lua scripting language for Android devices developed by Logimath.  You get an editor, scripting engine, small console output and a few simple code examples.  No graphics or anything fancy but a very nice way to play with an interesting language.

• Get SigmaScript from Google Play
• Go to the developer’s website

I’ve seen several equations that plot a heart shape over the years but a recent google+ post by Lionel Favre introduced me to a new one.  I liked it so much that I didn’t want to wait until Valentine’s day to share it.  In Mathematica:

Plot[Sqrt[Cos[x]]*Cos[200*x] + Sqrt[Abs[x]] - 0.7*(4 - x*x)^0.01, {x, -2, 2}]

and in MATLAB:

>> x=[-2:.001:2];
>> y=(sqrt(cos(x)).*cos(200*x)+sqrt(abs(x))-0.7).*(4-x.*x).^0.01;
>> plot(x,y)
Warning: Imaginary parts of complex X and/or Y arguments ignored

The result from the MATLAB version is shown below

Update

Rene Grothmann has looked at this equation in a little more depth and plotted it using Euler.

Similar posts

• A little mathematics for Valentine’s day
• The equation that says Hi