crntaylor

It wasn't meant to be a criticism of your implementation - just a comparison of the two languages for this particular task. Haskell happens to be very concise for writing mathematical code. I love Python too, but for different reasons (easy to prototype, great libraries, flexible).

I've noticed that people with a mathematical background tend to be very attracted to Haskell. There's a great blog post by Dan Piponi enumerating eleven reasons to use Haskell as a mathematician:

http://blog.sigfpe.com/2006/01/eleven-reasons-to-use-haskell...

Ture, but notice how easy and natural it is in Haskell. You can do the same thing in Python, as noted in the comment by jordigh -- but it takes ~40 lines, as opposed to ~8 lines in Haskell. I'm willing to bet that it's even more verbose in C++, and I don't even want to think about doing it in Java.

Yes -- see the source here: http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...

Fair point! It's interesting to figure out what the complexity must be.

There are certainly n additions to perform, and the numbers being added on the k'th step are of size O(phi^k) which will take O(log(phi^k)) = O(k log(phi)) to add. Therefore the total running time is

   1 + 2 + ... + n = O(n^2)

so the theory predicts quadratic, not linear time. I wonder if this is borne out by numerical experiments.

Indeed! In fact, it occurs to me that you can get something of a 'best of both worlds' solution between the elegant mathematical solution and the exactness of the recursive solution very easily in Haskell, by defining the field extension* Q(√5), i.e. the rational numbers extended with the square root of 5

  import Data.Ratio
  
  -- The number (a :+ b) represents (a + b √5)
  data Q5 = Rational :+ Rational deriving (Show) 

  instance Num Q5 where
    (a :+ b) + (c :+ d) = (a + c) :+ (b + d)
    (a :+ b) * (c :+ d) = (a * c + 5 * b * d) :+ (a * d + b * c)

  phi = (1 % 2) :+ (1 % 2)

It's now enough to notice that the coefficient of √5 in phi^n is half the n'th fibonacci number, so define

  fib n = let a :+ b = phi^n in round (2 * b)

to get

  >> fib 10
  55
  >> fib 20
  6765
  >> fib 80
  23416728348467685 -- exact result in O(log n)!

* http://en.wikipedia.org/wiki/Field_extension

The Fibonacci example is flawed, in that the given definition, in terms of phi = (1 + sqrt 5) / 2.0, is inaccurate even for moderately-sized inputs. A standard, O(n) definition for computing fibonacci numbers is

  >> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
  >> let fib n = fibs !! fromIntegral n

The constant-time approximation is

  >> let fib' n = let phi (1 + sqrt 5) / 2.0 in round (phi^n / sqrt 5)

Around n = 80 the constant-time solution starts giving incorrect results

  >> fib 80          -- exact O(n)
  23416728348467685
  >> fib' 80         -- approximate O(1)
  23416728348467676

Don't get too excited. The actual quotation is

  "Assuming Bitcoin becomes a major player in both e-commerce 
   and money transfer *and* a significant store of value with 
   a reputation close to silver, our fair value analysis 
   implies a *maximum market capitalization* of Botcoin of 
   $15bn (1 BTC = 1300 USD).

   This suggests that the 100 fold increase in Bitcoin prices   
   this year is at risk of running ahead of its fundamentals."

So if two questionably likely events both occur, BAML think that Bitcoin might have a maximum value of 1300 USD.

I like the article. I think it's well written, an important subject, and the world would be better if more people read it and digested its message.

I still wish it didn't repeat the myth that Coca-Cola invented the modern image of Santa Clause, though.

http://www.snopes.com/holidays/christmas/santa/cocacola.asp

I expect that you will learn a lot, and much of it will be interesting. Some of it will even be applicable outside of finance. Almost certainly you will lose money (through fees and buying data, if nothing else). If you're okay with that, then go ahead.

There's an interesting guide with some suggested reading at

http://quantivity.wordpress.com/2010/01/10/how-to-learn-algo...

That is not trading - that is investing.

It sounds like previously you were losing money because your frequent trading generated a lot of transaction costs. Now you trade less frequently, you have removed a lot of drag on your returns.

Essentially, all I am saying is that if your trading were completely random (and buying based on "broad stroke feeling" and "gut" and "feel to your bone" is essentially random) you would expect to do better the less you trade.

Which is exactly what you are seeing.

There are, broadly speaking, three kinds of quant funds that trade equities -

1. High frequency trading firms with sub-millisecond latency, who make their money from the bid-offer spread. You can't compete here.

2. Medium term traders who will hold a position for somewhere between hours and weeks. They tend to be looking for statistical regularities to exploit. If they find one, they don't expect it to persist for long - the typical 'half life' of a strategy is around six months. It's not impossible for an amateur to compete here, but be aware that there are thousands (tens of thousands?) of people for whom this is a full time job. Many (most?) of them have backgrounds in quantitative finance, have worked at funds and large investment banks, have PhDs in physics, mathematics, computer science etc. So you should ask yourself why you think you will be able to compete.

3. Long-term traders who are either stock picking, or actively managing a portfolio that might include stocks, bonds, commodities, currencies etc. Some of them are just trying to beat the market, and some are looking for absolute return. All the points in the OP article apply to this case.

A commodity is only worth what someone will pay for it. It would be impossible to offload 1M BTC at the market mid (currently $962) so it seems ridiculous to value Satoshi's bitcoin wallet at $1B.

The market isn't sufficiently well developed and doesn't have sufficient depth to support transactions of that size. Combine a lack of liquidity with the fact that BTC have no intrinsic value, and that the market has shown itself to be vulnerable to price shocks in the past, and I would value 1M BTC at significantly less than $1B (probably not even 10% of that).

I can understand that you were excited to be the one to create the poll, but I think you did a very poor job of it.

By the time you added the most recent names to the poll (22 minutes after creating it) at least one name already had 100+ votes.

You've also inexplicably put Narendra Modi on there (misspelled) even though he's not in tech.

> Imagine mathematicians or computer scientists re-proving real analysis theorems using floating point arithmetic...

Mathematicians and computer scientists do prove theorems about floating point arithmetic! For example, the most widely-cited floating point reference contains no fewer than fifteen theorems about floating point:

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.ht...

Or here's a presentation about representing functions with their Taylor expansions using floating point arithmetic, providing strong error bounds on the result of adding or multiplying two functions represented in this way:

http://perso.ens-lyon.fr/nathalie.revol/talks/ICIAM07.pdf

I agree that many proofs in computer science are harder than proofs in mathematics, because you can't deal with idealizations - you always have to think about the machine. But unlike empirical sciences, we have access to the design of the machine. We know what many of the axioms are. Formal reasoning is valid for a far larger part of computer science than for the natural sciences.

I'm not going to argue that proofs are a panacea for every situation. But I also don't categorically reject them in the domains where they can be usefully applied.

I don't agree with this statement

  "It is not sufficient merely to prove a program correct;
   you have to test it too."

It is sufficient to prove a program correct - as long as your proof is not faulty! The problem in this case was not that the program had a bug despite being proved correct. The problem was that the 'proof' was not a proof at all.

Machine ints are not mathematical integers. Floats are not real numbers. You can't prove things about programs that use ints/floats without taking these things into account.

Of course, the question of how one knows that a proof is correct is still left open - but that's a metatheoretical argument that it might be best to leave aside. I suspect that most faulty proofs are faulty for pedestrian reasons (incorrect type assumptions, failing to deal with null/NaN etc) rather than high-falutin' concerns about the validity of first-order logic.

It's not trying to recommend similar artists - it's recommending artists that you will like!

I think Mogwai and Aphex Twin are pretty good recommendations for someone who likes the math rock/post rock that Don Cab play.

Bar graph, for ease of comparison:

http://imgur.com/J21Oi7Z

I really enjoyed it. It's an odd experience, listening to an album that old and that well known for the first time, because almost inevitably you will have heard some of the songs before without realising where they were from. A couple of times I recognized intros or riffs but couldn't quite place them - probably from movies, advertisements, or just hearing them on the radio.

You also have to try and shed yourself of the intervening 40 years of musical and social development, to try and get a sense of why this album created such a buzz when it was released for the first time (context - I'm about 30 years old, so I wasn't even born until 10 years after this was released, and wasn't socially/musically aware until about 25 years after it came out.)

Today I listened to the album The Rise and Fall of Ziggy Stardust for the first time. It was released in 1972. Is it really that bewildering to you that not everyone has seen everything that exists already?

That's the joke -

http://en.wikipedia.org/wiki/Millenium_Falcon#Depiction

A reference to the Millenium Falcon completing the Kessel Run in "less than twelve parsecs"

Valid point - you eventually want your revenue to be larger than your expenses (unless you plan to get acqui-hired...)

Invalid point - you need Excel to figure that out. I think a good hacker is more likely to use some combination of R, Python + Pandas, databases and CSV files to do most of their financial modelling. Then those all-important month-end reports can just be automated away...

Yes, that's more or less it. The system you implement still knows about linearity of differentiation, the product rule, chain rule etc but it's not a full blown CAS. It can't give you the symbolic derivative of a function (although I guess you can technically apply AD to any numeric type, including a symbolic type..) but it can compute the numerical value of the derivatives at arbitrary points.

This is interesting. I am generally very skeptical about taking derivatives of functions computed from real-world data for exactly this reason. What I normally end up doing is applying some form of kernel smoothing (e.g. nearest K points with a Gaussian kernel) to approximate the function, and then compute derivatives of that instead.

Would you recommend another way?

The typical approach is to provide overloaded versions of primitive functions (generally addition, multiplication, subtraction, division, powers, trig and hyperbolic trig functions, exponential and logarithm) for which you explicitly tell the program what the first N terms in the Taylor series are.

The magic is that you also tell it how to compute Taylor series of function compositions, if the Taylor series of the functions being composed are already known - then any arbitrary function composed out the primitive functions can have its Taylor series computed automatically!

For your example, the function 1/(1-x) is the composition of

    x -> -x
    x -> 1+x
    x -> 1/x

and so its Taylor series is already known as long as you have already defined negation, addition and reciprocation.

True, but I don't think Strassen and other efficient algorithms are much used in practice. If you go poke around in the source code for BLAS or LAPACK you'll see that the matrix multiplication algorithm used is an O(N^3) algorithm.

It's not the naive O(N^3) algorithm though - it's a block multiplication algorithm which generally gives faster results than the naive algorithm, because it's able to exploit locality so that you don't need to shift data into and out of the CPU cache all the time.

The point is that when you're considering the Taylor series for a dual number argument, you don't lose any precision, because higher powers of the "imaginary" part of the dual number vanish. The example he gives is

    f(a + be) = f(a) + f'(a)be + 0.5 * f''(a) b^2 e^2 + O(e^3)
              = f(a) + f'(a)be

because e^n=0 for all n>1. This isn't an approximation - it's an exact relationship for dual numbers!

You will lose some precision by using floating point numbers instead of an arbitrary-precision real number type, but this is a limitation of the machine you're working on. The method is exact.

Very neat. Presumably there is a more efficient method for implementing Nth order automatic differentiation than encoding the dual numbers as NxN matrices, though? To multiply the matrices takes O(N^3) time, whereas by exploiting their known structure I think you should be able to do it in O(N^2) time. Am I wrong?

On your first point; I was matching the behaviour of the C++ program in the blog post, which allows any number of command line arguments but only uses the first two.

On your second point, I actually thought about writing the whole thing as

  getArgs >>= \a -> readFile (a!!0) >>= writeFile (a!!1) . unlines . sort . lines

but decided that that's exactly the kind of thing that gets Haskell programmers a bad reputation.

Haskell:

  import System.Environment
  import Data.List

  main = do
    infile:outfile:_ <- getArgs
    input <- readFile infile
    writeFile outfile . unlines . sort . lines $ input