The Frankfurt Workout in Computational Finance
Four different topics have been covered:
Extreme Vasicek is not Enough - Mean reverting short-rate models. What are the pros and cons of trees, finite differences / elements, Monte Carlo techniques? Lognormal or normal models? What about higher dimensions?
Model Calibration and Spurious Precision - A general framework for stable and robust parameter identification. Even with analytic inversion formulae, noise in the data can lead to results which are pure nonsense. Can we trust our parameters?
When Monte Carlo is the Only Choice - More than 3 dimensions or severe path-dependence? Monte Carlo techniques. Monte Carlo or Quasi Monte Carlo? How can the variance of the result be decreased? What about early exercise?
Risk Management Cascades - The requirements posed by regulators become more and more stringent. How can we calculate the different VaRs? Expected shortfall? In reasonable time? And how can we build a CVA system?
During the breaks (off topic: the snacks provided by Roomers are excellent) a lot of lively discussions took place. I even managed to finish my sessions (almost) on time so that our German guests were able to watch and celebrate the win of their team against the team of the USA.
I hope the attendees of the seminar enjoyed it as much as Andreas and me have done.
StartupQuants 2014 - An Intimate Workout
StartupQuants 2014 - at the UnRisk Headquarter in Linz, Austria
Germany versus USA: Arbitrage at the FIFA 2014 world cup?
The two teams leading in front after the final round will enter the stage of the final 16 teams.
From the arbitrage point of view, a draw between Germany and USA would make sure that both teams succeed in getting to the round of 16.
(There is the rumour that in the 1982 world cup, there has been an arbitrage match between Germany and Austria in Gijon with both teams coming to the next stage after a 1-0 win of Germany.)
Will similar things happen in 2014? I do not think so. Football is not only about results but also on passion.
Like UnRisk.
UnRisk FACTORY 5.1 Is Released
We call it the "Bloomberg Release"
It integrates a market data solution for owners of a Bloomberg data license. The UnRisk FACTORY market data adapter for multiple market data sources was expanded by a Bloomberg instantiation that enables an immediate set up.
This is the 11th release of the compellingly comprehensive combo - a risk management solution and development system in one - since may 2008.
Order and set it up to run in 10 days.
What Will I Be Writing in 2024
This post has been motivated by a session of the WIRED UK June-14 issue.
The UnRisk team always looks a little into the future. What about new mathematical schemes, programming techniques, computing platforms and tools for better development and project management tools …. and media and communication platforms …. socio-economic and financial systems. In short, new environments for innovation and marketing?
Look a little further ahead?
The future as it was? It's hard to believe, but back in 2014 people propagated fragile, tightly coupled complex systems for front-to-back investment and risk management and not so few developers believed in one-technology-fits-all approaches.
It was not so difficult to predict that the financial security systems did not make the system safer - regulatory bodies forced banks do "go nuke" (do as the nuclear power plants needed to do, because of the technology)
Why the atifragility argument led to re-decentralization
For some it may be surprising, but ….
Big players providing information technologies did voluntarily split themselves into independent units. Buffers, diffusion and agility will fix what did not work: hierarchies, strategic plans and industrialized work in an economy of scales - flexibility, innovation and enthusiasm drive better offerings and consequently returns - and are safer for the economies.
I finance this led to a retraction of the strict central collateral management and clearing system. Market systems are too complicated to be centrally managed.
In combination with the extreme xVA treatment it broke to a marginal cost regime. Large banks have identified collateral transformation and central clearing as lucrative service, but that created the old problems of market dominance through another doorway.
How to program the money system
A system is universal, if it is solid enough to store and liquid enough to transform. A universal system is programmable. Our money can store values and it is a media for economic transactions, consequently, the money system is programmable. We now understand that this needed an operating system and development tools.
System architects, computer scientists and quants are now indispensable in new jobs dealing with money policy and creation as well as providing the operational semantics of the programs. Symbolic, declarative programs that needed a lot of clever algorithms to implement them.
Following the decentralization logic money creation became even more decentralized and for better programming we invented new money types, like derivative money - futures, options, …
Technologies Do It Yourself investors should use
Structure me this is not longer in disrepute. There are technologies that help to make complex
financial concepts to non experts. Decision support system will use new media and dynamic visualizations techniques. Systems will adapt to a financial "aura" of a market participant describing objectives, risk appetites, ….
High level, simple, interactive, knowledge-based, domain-specific programming will allow them to simulate deals with portfolios of various deal types.
The internet of finance is reality
We all, dealing with financial applications, knew that it was a joke to worry about big data, when still struggling with getting informative small (market)data with the possibility to turn this data into something that supports decisions.
Informations like debt and profit webs came into play to let agents understand feedback loop better ….
Those data are now available and widely accessible. They allow us technology providers to intelligently combine modeling with more data driven adaptability - making data meaningful.
Reasons, why quant work is now more polarized
10 years ago quants whee so overwhelmed by the operational requirements meeting the regulatory system. If they did xVA they did the same thing (valuations) 100 million times an hour instead of 5 million times an hour when doing portfolio-across.scenario simulation. This needed a lot of plumbing, especial if their banks suffered from the was-not-invented-here syndrome.
Now, the new technologies and tools give them time to optimize their business. They can design new financial systems. How they do it will not make a big difference, but what they do will.
Adding value still means: doing the hard work.
Programming is knowledge-based
Programming is symbolic, multi-paradigm and uses algorithmic knowledge-bases. There are development environments that support high level programming in multi-languages, that are platform agnostic. We do not longer care about versions and releases and underlying programming languages. All algorithms for high performance computing are inherently parallel and support all architectures of the new computing muscles.
The most complex applications go where the users go
Write once, deploy anywhere.
Clouds went private and crunch and store all the (risk) numbers blazingly fast.
Even smart devices will have enough power and display-quality to do massive pre-processing creating insight about incoming data flows and prepare them for processing.
Financial objects and their risk spectra can be post-processed and insightfully arranged on the smart mobile devices.
Program everything
The blog posts are interactive, some stories are created by and act like programs. 70% of the news are created by computers. Ask a question and you will receive a little program that answers all questions of that type.
More quants do more meaningful things
and turned them into businesses
And
it is late June, the sky has scattered clouds, the birds are singing, …..
Basic Math - Big Impact
Quantum Physics and Options
- Eigenfunctions
- Potentials
Would I Drive An Open Source Car?
It is very natural thinking: balance the tremendous inflow of valuable in depth information that you cannot transform a fraction of into margins with a free outflow of great results we cannot transform into values alone? No doubt, open source software was one of the drivers of globalization. Open innovation is less radical, but still offer out licensing.
As a reviewer and evaluator of innovation projects of the European Commission I evaluated about 500 projects. All of them were performed by international partners and the consortium agreement controlling the exploitation and intellectual property rights were seen as important part of the project. They often complicated the project and I argued for a more liberal treatment of intellectual property rights. Technology leadership is nit defined by patents (says, Elon Musk) - I agree.
But I ask myself: Would I drive and open source car? I would definitely drive an open innovation car!
Hot Topics at ECMI 2014
Not too surprisingly, they saw future challenges for quants in xVA, and they also saw a shift of human ressources in quantitative analytics from valuation and trading to risk.
Young Quants - Experience is Overrated
We are sitting on enormous amount of cash, but business grows slowly. It seems the problem arises from the flawed assumption capital must be conserved at all cost.
Radical innovation needs talent spotting
We need more radical innovation at the Main Street and the Wall Street. And this needs talents.
Potential beats experience and competencies
Future businesses will be too volatile and complex to rely on experience and competencies (only) - we need potential, the ability to adapt to the changes swiftly.
To innovate is hard work
This is an enormous opportunity for young quants. Innovate by doing the difficult work. With motivation, curiosity, insight and engagement. Quants develop the tools that shall guide investments to the best opportunities.
To do that they use tools themselves. Quants engineer, model and program.
Tools shall help them to explore new things and verify them by doing multiple experiments. We at UnRisk provide solutions, but we also provide what we call motivational tools for quants - UnRisk-Q, providing the UnRisk Financial Language implemented in the UnRisk Engine with a broad coverage of deal types and risk scenarios.
We decided to help (young) quants leverage their work
This post has been motivated by the June 2014 issue of HBR Magazine - Experience is Overrated.
"One more thing..."
Luckily, the ubiquitous goats-lions-wolves problem that haunts us UnRisk-ers since a couple of weeks is a nice testing ground for such data containers. In his post, Sascha promised that he would write no more on this problem. I didn't give that promise :) One of the more time-consuming parts of the problem is the calculation of a set of unique "next forests". Sascha's solution solves that problem by stuffing the next forests into a vector, sorting that vector and then removing the duplicates. At first sight, it seems a bit wasteful to first generate all possible solutions, then sorting them (an order N*log(N) operation in the worst case), and then throwing away the duplicates.
An alternative solution would be to insert the next forests into a set or an unordered_set, where inserting takes care of the duplicates and is an order log(N) operation. In theory, the operation with the lower complexity should lead to faster code, at least if N is large enough. In practice, it is not all that clear how large "large enough" is.
Enough of the talking: Here are the measured timings in seconds as a function of the number of animals in a log-log plot (blue: Sascha's vector-sort version, red: version using unordered_set, yellow: version using set)
To be honest, I am a bit surprised by the horrible performance of the set-based versions (they are only a bit more than two times faster than the Fortran version!). If one takes a closer look, the unordered_set version comes closer to the vector-sort version for higher values of N (it is about a factor of 3 slower for small numbers, and only a factor of 2 slower for the larger ones). One would need to go to impractically large numbers of animals, however, to reach break-even, if break-even occurs at all. Two quick checks with the profiler reveal that:
- 82% of the consumed time really goes into the (unordered_)set.insert
- for very large sets (many millions of elements), inserting really goes with Log(N)
- However: our sets don't get that large in this problem
A success story from the publication front
As the title implies the story is all about Artificial Graphene. Artificial graphene is a recently realized man-made nanosystem that exhibits graphene-like physics in a tunable setup. The system can be created by, e.g., positioning molecules in a triangular lattice on a metal surface. For the paper, we model finite flakes of artificial graphene on a real-space grid and calculate their single-electron properties as a function of the flake size and the strength of an external magnetic field. Our calculations reveal the gradual formation of Dirac cones as well as a self-similar Hofstadter butterfly as the flake size is increased. Moreover, the density of states agrees well with the experimental data with and without the magnetic field. In essence, we are able to determine the stability of Dirac points in finite flakes of artificial grapheme.
What's up next? Electronic and transport properties of Graphene are sensitive to the presence of atoms adsorbed on its surface. An important question, however, is whether the distribution of adatoms is always genuinely random. There are hints, that that dilute adatoms on graphene may have a tendency towards a spatially correlated state with a hidden Kekulé mosaic order.
Flake potential with Kekulé mosaic ordering. |
A Program Passed the Turing Test
But is it?
The winner was a program ("Eugen Goostman"), claiming to be a 13-year-old Ukrainian boy, that convinced a third of 30 judges.
To me the value of the Turing test in actual computer science is questionable - and in concrete I think that judges might have underestimated the intelligence of a 13-year-old non-native English speaker from Ukraine.
However, I am interested in fields were computers may outsmart humans. Maybe self driving vehicles, eliminating road deaths or other trustable robots.
But I think, if robots react to things we cannot see or other events we do not understand, we call them stupid.
So, the Turing test might be seen completely different 2050?
Computational Finance at ECMI 2014
What did surpirise me: The largest minisymposium is on computational finance.It starts tody and goes for more than two days. I am quite impressed by the quality of the presentations given by Ph.D. students.
Writing in the 21st Century Needs More Programming
Science can inform all aspects of life. The process of writing itself has psychological aspects. It makes psychological a difference if you write: "A happens, because B happened" or (better) "When B happened then A happens" ….
One thing is clear to me, in writing it is not so important to use grammar correctly, but express yourself as good as possible. It's easier to write about things that matter for those who care, but you want a one to many conversation and you don't know the audience - so, it is still kind of unnatural.
What are you simulating when writing?
Expressing yourself about something you know you need to find words and constructions that grammar guardians might find wrong. Or even new languages - like the language of mathematics. A mathematical expression (symbols) can tell you a lot about a principal real behavior, but its operational semantics (its implementation) tells you more.
Simulations can explain things to people, who are not so artistic in understanding and manipulating expressions, like complex formulae.
Documents that are programs make things clearer
In language is too clumsy an instrument I have taken the example of a term sheet of a financial instrument and bring its into a form that is understandable and computational.
A symbolic expression can be a great compression of a complex i/o behavior, but it my also form the way you think about the problem. If you search for elegance, you may look for closed form solutions and simplify the problem instead of the model.
With programs you can go beyond.
Kids shall learn programming
Kids often explain that they have seen things that a friend has seen and told them and do not understand that others do not have the same knowledge. We often laugh at them, but don't we often use expressions that our readers have no way of knowing? Again, simulations tell more.
Therefore it is my strong belief that children shall learn language and programming.
Later they can learn languages of physics, mathematics, biology, … if required. And they will understand that those languages shall have freedom and knowledge.
Programs can even make fairy tales: functional goats, …, Oh sorry, the goats again.
In search of the deepest, most insightful, most informative understanding of the world and ourselves - we shall rely on writing and a lot of
programming.
Picture from sehfelder
An Antifragile System Concept
It took me a while to get my breath under control again. A page view explosion to 40.000 responding to Sascha's programming comparison. A little related to our hybrid programming concept:
Aaron Brown wrote another brilliant article in the Mar-14 Wilmott Magazine. A review of Nate Silver's book, the signal and the noise. A great book with one blind spot: tail events (when discussing the financial crisis). Not surprisingly, its is about Black Swans, and the trap of modeling uncertainty as casino game. (NN Taleb called it lucid fallacy)
Recently, I wrote about antifragilty and the problem of tightly coupled complex systems and the cage of strategic planning.
Today I read towards an antifragile IT strategy - in Kailash Awati's Eight to Late.
Take advantage from options we do not know yet
It is about the impossibility to predict the future in detail. How can you make a strategic plan without that?
The trick is to plan with options that we we do not know now (like real options relating to project size, life and timing, as well as operation). (Real) options usually increase the value of a project - they capture the value of managerial flexibility in a world of uncertainty.
Suggestions for an antifragile IT strategy
Decentralization - give structural units authority
Agility - be prepared to change regimes
Diversification - diversify system elements that may be effected by uncertainty
Creating an environment of trust - if you have multi-strategy, multi-methods and multi-skills you need trust
What is true for the process is true for the system
In a tightly coupled organization you do not plan for possibilities but industrialization.
A tightly coupled complex system, usually result of such a process, does also not increase the number of choices and the emergence of an unexpected event can become horrible.
So, diversify and decentralize your system, make it agile by increasing its adaptability. Make intelligent independent system components that are accurate and robust, but flexible. Let them co-exist and co-evolute.
This may raise the eyebrows of the system centralizers, integrators, top-downers … but it is correct.
There is no such horrible operational risk than a tightly coupled organization with tightly coupled complex systems. It never becomes stronger when stressed.
Picture from sehfelder
A Solution to a Homework Problem
Using
and defining
one ends up with
Helping Quant Startups Leverage Their Businesses
Our engagement in finance started 1997 and we were lucky to choose the right technology and found partners who set us high goals but supported us to achieve them (see a short story of being lucky)
Don't take care of that all
When you start your own business, it's just you and you ideas. You add clients and they shape you and your ideas. It is vital that you avoid a few traps - one of the most important: don't think you need to do it all your self. The foundations and technologies you us will enable you to add values much swifter.
Great opportunities for a new wave
Yes, the crisis shook things up. The regulatory "tsunami" makes simpler instruments more complex, because of their role in an interacting system of counter parties … and the complex ones become complex^2. Consequently, quant work becomes more difficult and indispensable, for the sell and the buy side.
At the other hand technologies have become better and cheaper and obstacles to access them has faded.
Entering the quant finance market, we observed that quants developed quite similar systems - bound by legacy technologies named strategic technologies at their, banks, … But banks may remember that their core business is not technology making …
In the new regulatory framework and for their own benefits even individual investors want quant validation.
This all creates new opportunities for quant startups.
UnRisk-Q for a growing quant market
Helping independent quants to leverage their businesses we have unleashed the programming power behind UnRisk - UnRisk-Q, for which we spent over 80 years developing, carefully choosing the mathematics, mapping every practical detail - for derivatives analytics and risk management.
And we are radically open about everything we do mathematically and technically.
After a great reception we go beyond
Our UnRisk FACTORY clients use UnRisk-Q to post process tons of valuation and risk data calculated by the FACTORY automatically.
And we have now the idea to add the FACTORY to UnRisk-Q for quants. The FACTORY combines a grid engine with a data base and web front-end and builds a great system for solution development and integration - perfect for an evolutionary prototyping approach. Ideal for quant development. Ideal for quant startups.
UnRisk Quants - the combination represents 150 years of development and its yearly license price will be about the cost three quant months.
We want to intensify building the quant community around UnRisk. We want to help our partners, conserving capital, leveraging technology and intensifying computational finance skills.
If you are interested send me an e-mail
Picture from sehfelder
Crowd movements
What I really liked: Marie-Therese Wolfram's (as far as I know, no family relations to Wolfram research) presentation on crowd movements that arose from her project Multiscale modelling and simulation of crowded transport in the life and social sciences.
We all know how nerve-consuming it may become to board an aeroplane (because the people with the heavy hand lugguage are always in front of you). Marie-Therese spoke on the advantage of intelligent crowds (using all information available and choose rational strategies) which may then reduce the danger of stampedes quite significantly. Guidance is necesary in such situations.
My personal experience when boarding a national flight within Japan: They flight attandants and the gate personnel were successful to board an aeroplane with 300 passengers in 8 minutes, because the passengers obeyed the rules.
Think Like a Freak?
I enjoy reading the Freakonomics Blog. And I really agree that insightful, counterintuitive, original thinking drives innovation in different form-of-expression of life, socio-cultural, socio-economic, ... and definitely business.
This is the book: Think like a Freak (Levitt & Dubner)
And there is this story that has provoked a lot of response: Steven Levitt, Professor of economics at the University of Chicago - suggested UK's prime minister David Cameron (in a meeting): UK would benefit by replacing their silly publicly funded health care with a truly free market where people have to pay for everything.
What is behind: it seems obvious that if you don't charge people for things (including health care), they will consume too much of it?
This has been commented by Noah Smith here and Cameron Murray here.
Optimal risk in life?
What is interesting to me is Levitt's emphasis on the maximization of a benefit and not the optimization of a risk. How to enjoy life, but avoid severe diseases? How much sport, how much mobility, how much interaction, how much celebrations, how much wine and dine, …. how much medication, … difficult enough.
However, as in finance, it's not only the cost of risk it is also the optimal input fraction of our potential.
Yes, it is much easier to do risk management in quantitative fields - if dangers and opportunities are not quantifiable, we have limited ability to control them. But you are lucky if you are able to make danger and opportunities a positive contribution.
So, it is my strong belief, that we think like a freak, if we want to optimize risk also in health care - and not just look what the "market" says.
Picture from sehfelder
Fast Functional Goats, Lions and Wolves
In a recent post, Andreas declared his love for the programming language FORTRAN. He concluded his post with the question “Can a functional language do this as well?”, where he was referring to the efficiency of his FORTRAN solution for the goats, wolves and lion problem. He followed it up with another post where her presented a more memory efficient solution that solves the goats, wolves and lion problem for an initial forest of about 6000 animals in 45 minutes. The purpose of this post is to give an answer to Andreas’ question.
To begin with, I promise that this is my last post that deals with the goats, wolves and lions problem. The problem is an interesting one in order to put different programming languages to the test. We’ll consider programming languages in our test that we use for the implementation of our products UnRisk-Q and UnRisk FACTORY:
The Wolfram Language
I gave a functional solution to the goats, wolves and lions problem in an earlier post, which dealt with construction of a functional solution using the Wolfram Language from a didactical point of view. Efficiency was not a concern. This time, we’ll develop a more efficient functional solution by using advanced features present in the Wolfram Language.
C++ 11 and Java 8
Functional programming language constructs are now being added to existing programming languages in the same way object-oriented features were introduced to procedural languages in the 1990s. The latest versions of both C++ and Java have been extended with Lambda functions and closures.
JavaScript
JavaScript has become one of the most popular programming languages due the ubiquitousness of the web. JavaScript had support for functional programming concepts from the very beginning through first-class functions and closures.
The Rules for the Test
- The solution must make use of functional programming constructs available in the respective language.
- The implemented solutions must be adequate to the idioms, techniques and the style of the respective language. We’ll follow the principle “when in Rome, do as the Romans do”.
- The solution must not use third-party libraries.
- All solutions must be cross-platform and run on Windows, Linux and OS X.
- We’ll evaluate the solutions based on efficiency.
The following sections show a lot of code. If you are not interested in the technical details of the implemented solutions, look at formulas instead or skip ahead to the runtime comparison section.
An Efficient Solution in the Wolfram Language
Since Andreas’ FORTRAN solution did not produce the devouring strategy that led to the stable forest, just the final stable forest itself, our efficient solution in the Wolfram Language will only compute the stable forests that result from an initial forest. We’ll use a vector to represent the state of a forest consisting of counters for the three different animal species:
{17, 55, 6}
We can use vector addition to compute the next state of a forest after a meal by adding {-1,-1,+1}
(a wolf devours a goat), {-1,+1,-1}
(a lion devours a goat) or {+1,-1,-1}
(a lion devours a wolf) to a forest state vector:
In[1]:= {17, 55, 6} + {-1, +1, -1}
Out[1]= {16, 56, 5}
In the Wolfram Language a vector addition can be performed efficiently in one step on a list of vectors:
In[2]:= {{17, 55, 6},{17, 55, 6},{17, 55, 6}} + {{-1,-1,+1},{-1,+1,-1},{+1,-1,-1}}
Out[2]= {{16, 54, 7}, {16, 56, 5}, {18, 54, 5}}
We’ll use this feature in a function Meal
that applies all possible meals to a list of forest states:
Meal[forests: {_?VectorQ ..}] :=
With[{possibleMeals = {{-1,-1,+1},{-1,+1,-1},{+1,-1,-1}}},
DeleteCases[
Apply[Union,
ConstantArray[forests, Length[possibleMeals]] +
Thread[ConstantArray[possibleMeals, Length[forests]]]
], {___,-1,___}
]
]
The functions ConstantArray and Thread generate lists of vectors of the same shape which can then be added with the Plus operator.
The Union takes care of eliminating duplicate forest vectors and flattening of the resulting list at the same time. The vector addition may produce invalid forest states (i.e., states where one of the animal counters drops below zero). The outermost DeleteCases uses pattern matching to filter these invalid forest states.
The remaining parts of the solution are similar to the solution from the original post:
DevouringPossible[forests: {}] := False
DevouringPossible[forests: {_?VectorQ ..}] :=
FreeQ[forests, {___,0,___,0,___}]
StableForests[forests: {_?VectorQ ...}] :=
Cases[forests, {___,0,___,0,___}]
FindStableForests[forest_?VectorQ] :=
StableForests[NestWhile[Meal, {forest}, DevouringPossible]]
DevouringPossible
and StableForests
have been rewritten in terms of Wolfram Language pattern expressions. Download the full Wolfram Language program here.
A Functional Solution in C++ 11
We’ll now reimplement the exact same algorithm we just gave for the Wolfram Language in C++ 11. A forest state with its three animal counters can be represented as a std::array in C++:
typedef std::array<int,3> forest_t;
Our C++ solution makes heavy use of algorithms from the C++ standard library. First we’ll add two helper functions to determine if a forest is stable or invalid:
bool forest_stable(const forest_t& forest) {
return std::count(std::begin(forest), std::end(forest), 0) >= 2;
}
bool forest_invalid(const forest_t& forest) {
return std::any_of(std::begin(forest), std::end(forest),
std::bind(std::less<int>(), std::placeholders::_1, 0));
}
In the C++ community there is little love for containers other than std::vector. So, to go with the flow, we’ll use a std::vector<forest_t>
to represent the list of forest states. The C++ meal
function that corresponds to Meal
in the Wolfram Language then looks like this:
std::vector<forest_t> meal(const std::vector<forest_t>& forests) {
static const std::array<forest_t,3> possible_meals = {{
forest_t{{-1,-1,+1}},
forest_t{{-1,+1,-1}},
forest_t{{+1,-1,-1}}
}};
// apply possible meals to all forests
std::vector<forest_t> next_forests;
next_forests.reserve(forests.size() * possible_meals.size());
for (auto meal: possible_meals) {
forest_t next_forest;
std::transform(std::begin(forests), std::end(forests),
std::back_inserter(next_forests),
[&](const forest_t& forest) {
std::transform(std::begin(forest), std::end(forest),
std::begin(meal), std::begin(next_forest),
std::plus<int>());
return next_forest;
});
}
// filter valid forests
auto valid_end = std::remove_if(std::begin(next_forests),
std::end(next_forests), forest_invalid);
// delete duplicates
std::stable_sort(std::begin(next_forests), valid_end);
next_forests.erase(
std::unique(std::begin(next_forests), valid_end),
std::end(next_forests));
return next_forests;
}
The heavy lifting in this function is done by the template algorithm std::transform and a C++ lambda function that performs the vector addition.
Because std::unique only removes consecutive duplicate elements, we have to sort the vector of forest states first in order to place identical ones next to each other. The function is an example for an application of the erase-remove idiom in C++.
Here are the C++ versions of DevouringPossible
, StableForests
and FindStableForests
:
bool devouring_possible(const std::vector<forest_t>& forests) {
return !forests.empty() && std::none_of(std::begin(forests),
std::end(forests), forest_stable);
}
std::vector<forest_t> stable_forests(const std::vector<forest_t>& forests) {
std::vector<forest_t> stable_forests;
std::copy_if(std::begin(forests), std::end(forests),
std::back_inserter(stable_forests), forest_stable);
return stable_forests;
}
std::vector<forest_t> find_stable_forests(const forest_t& forest) {
std::vector<forest_t> forests = { forest };
while (devouring_possible(forests)) {
forests = meal(forests);
}
return stable_forests(forests);
}
Please note that the C++ solution does neither use a for loop with a counter nor contain an explicit array subscript expression.
The rest of the program consists of straightforward C++ code. Download the complete C++ 11 program here.
Functional Solution in Java 8
In Java there is no built-in constant size array type or tuple class. We’ll use a value-based class to represent a forest:
final class Forest {
private final int goats;
private final int wolves;
private final int lions;
private Forest(int goats, int wolves, int lions) {
this.goats = goats;
this.wolves = wolves;
this.lions = lions;
}
static public Forest makeForest(int goats, int wolves, int lions) {
return new Forest(goats, wolves, lions);
}
@Override
public int hashCode() { ... }
@Override
public boolean equals(Object obj) { ... }
@Override
public String toString() { ... }
The private constructor and the factory method are straightforward. The hashCode
, equals
and toString
methods are required by the contract of a value-based class. Their implementations are automatically created by the IDE.
public Optional<Forest> wolfDevoursGoat() {
if (this.goats > 0 && this.wolves > 0)
return Optional.of(
makeForest(this.goats - 1, this.wolves - 1, this.lions + 1));
return Optional.empty();
}
public Optional<Forest> lionDevoursGoat() { ... }
public Optional<Forest> lionDevoursWolf() { ... }
The methods wolfDevoursGoat
, lionDevoursGoat
and lionDevoursWolf
use the new Java 8 class Optional. The type Optional
makes explicit that for a given reference we may not have a value and allows for monadic processing of the enclosed value.
public Stream<Forest> meal() {
List<Forest> nextForests = new ArrayList<>(3);
this.wolfDevoursGoat().ifPresent(forest -> nextForests.add(forest));
this.lionDevoursGoat().ifPresent(forest -> nextForests.add(forest));
this.lionDevoursWolf().ifPresent(forest -> nextForests.add(forest));
return nextForests.stream();
}
The meal
method of the Forest
class returns all possible following forest states as a Stream. Streams are another new concept introduced with Java 8. Streams can be seen as lazily constructed Collections, where the production of the elements can be postponed until client code demands it. Furthermore a stream allows for sequential aggregate operations as shown in the implementation of the static method meal
for a list of forest states:
static List<Forest> meal(List<Forest> forests) {
return forests.stream().flatMap(Forest::meal).
distinct().collect(Collectors.toList());
}
Using a monadic flatMap operation on the stream of current forest states, first the set of possible follower forest states is computed, then duplicate forests are eliminated with a distinct filter and finally the resulting forest states are collected in a new list.
The methods devouringPossible
and stableForests
and findStableForests
are also implemented in terms of Streams:
static boolean devouringPossible(List<Forest> forests) {
return !forests.isEmpty() &&
!forests.stream().anyMatch(Forest::isStable);
}
static List<Forest> stableForests(List<Forest> forests) {
return forests.stream().filter(Forest::isStable).collect(Collectors.toList());
}
static public List<Forest> findStableForests(Forest forest) {
List<Forest> initialForests = Collections.singletonList(forest);
Optional<List<Forest>> solution =
Stream.iterate(initialForests, MagicForest::meal).filter(
forests->!devouringPossible(forests)).findFirst();
return solution.isPresent()?
stableForests(solution.get()) :
Collections.emptyList();
}
Download the complete Java 8 program here.
Functional Solution in JavaScript
As we have done for the Java solution, we define a class to represent a forest in JavaScript. Here is the constructor function:
function Forest(goats, wolves, lions) {
this.goats = goats;
this.wolves = wolves;
this.lions = lions;
}
We add methods for the three different possible meals …
Forest.prototype.wolfDevoursGoat = function() {
if (this.goats > 0 && this.wolves > 0)
return new Forest(this.goats - 1, this.wolves - 1, this.lions + 1);
else
return null;
}
Forest.prototype.lionDevoursGoat = function() { ... }
Forest.prototype.lionDevoursWolf = function() { ... }
… and a meal
method by assignment to the Forest
prototype object:
Forest.prototype.meal = function() {
return [this.wolfDevoursGoat(),
this.lionDevoursGoat(),
this.lionDevoursWolf()].filter(
function(f) { return f !== null; })
}
The meal
function for a list of forests makes use of the JavaScript array methods forEach and filter:
function meal(forests) {
var nextForests = [];
forests.forEach(function(forest) {
nextForests.push.apply(nextForests, forest.meal())
});
// remove duplicates
return nextForests.sort(Forest.compare).filter(function(forest, index, array) {
return (index === 0 || Forest.compare(forest, array[index - 1]) !== 0);
});
}
Here are the JavaScript versions of DevouringPossible
, StableForests
and FindStableForests
:
function devouringPossible(forests) {
return forests.length > 0 &&
!forests.some(function(f) { return f.isStable(); });
}
function stableForests(forests) {
return forests.filter(function(f) { return f.isStable(); });
}
function findStableForests(forest) {
var forests = [forest];
while (devouringPossible(forests)) {
forests = meal(forests);
}
return stableForests(forests);
}
Download the complete JavaScript program here.
Runtime Comparison
Without further ado, we present the running times of the different programs for sample input forests ranging from 80 to 6000 animals:
Goats | Wolves | Lions | Forests processed | C++ 11 | Java 8 | JavaScript | Wolfram Language | FORTRAN |
---|---|---|---|---|---|---|---|---|
17 | 55 | 6 | 3,636 | 0.01s | 0.24s | 0.04s | 0.03s | 0.01s |
117 | 155 | 106 | 517,236 | 0.05s | 0.62s | 1.49s | 1.95s | 0.10s |
217 | 255 | 206 | 2,600,836 | 0.35s | 1.46s | 8.70s | 10.54s | 0.96s |
317 | 355 | 306 | 7,254,436 | 1.20s | 3.58s | 25.59s | 29.94s | 4.58s |
417 | 455 | 406 | 15,478,036 | 2.74s | 8.30s | 56.90s | 63.61s | 11.45s |
517 | 555 | 506 | 28,271,636 | 5.09s | 16.40s | 109.72s | 118.32s | 22.23s |
617 | 655 | 606 | 46,635,236 | 9.14s | 28.40s | 187.80s | 195.53s | 38.59s |
717 | 755 | 706 | 71,568,836 | 14.50s | 45.75s | 307.35s | 301.94s | 61.16s |
817 | 855 | 809 | 104,072,436 | 20.25s | 67.64s | 467.59s | 444.28s | 92.78s |
917 | 955 | 906 | 145,146,036 | 28.77s | 100.73s | 655.53s | 627.07s | 131.90s |
1,017 | 1,055 | 1,006 | 195,789,636 | 39.71s | 141.98s | 898.48s | 864.35s | 180.12s |
2,017 | 2,055 | 2,006 | 1,448,575,636 | 335.07s | 1,352.33s | 7,099.95s | 7,526.00s | 1,602.23s |
Thanks to Andreas for providing me with the FORTRAN source code for his two-dimensional solution. The running times of his solution have been added to the table.
The results were obtained by using the following tools:
- MacBook Pro Mid 2010, equipped with a 2.66 GHz Intel Core i7 (“Arrandale”) processor and 8 GB 1067 MHz DD3 memory.
- OS X 10.9.3.
- C++ compiler Clang 3.4 with libc++.
- Oracle Java JDK 1.8.0_05-b13.
- JavaScript engine Google V8 3.25.30.
- Mathematica 9.0.1 for Wolfram Language.
- GNU Fortran 4.8.2.
- given times are wall-clock time measured with the shell command
time
and the functionAbsoluteTiming
for Wolfram Language code.
The following plot shows the data from the table. In this plot, the running time of the largest forest with 6000 animals has been omitted to avoid outliers.
By looking at the plot and the table we can draw some immediate conclusions:
Performance-wise, C++ trounces all the other programming languages in the test. The C++ program processes around 5 million forests per second on a single core, whereas the Wolfram Language program tops out at around 250 thousand forests.
There is a huge performance gap between the group of statically typed languages (C++, FORTRAN, Java) and the group of dynamically typed languages (JavaScript, Wolfram Language). The optimizations that the compiler can derive from having type information available at compile time still gives statically typed languages an edge over dynamically typed languages.
The performance of the Wolfram Language and JavaScript are roughly on par.
From the different running times, we can compute an average speedup that can be attained by moving from a higher level language to a lower level language:
From | To | Speedup |
---|---|---|
Java | C++ | 4.0 |
JavaScript | Java | 6.1 |
Wolfram Language | Java | 6.5 |
JavaScript | C++ | 22.4 |
Wolfram Language | C++ | 24.2 |
Of course these numbers cannot be generalized, they only apply to the tested programs. Also note that FORTRAN is not included in the list, because no sane person would switch to FORTRAN from another programming language voluntarily.
Conclusion
We can give the following answer to Andreas’ question “Can a functional language do this as well?” from this post. The computation time of all developed functional solutions is below two seconds for an initial forest of (117, 155, 106) animals. So the answer has to be “yes”.