tag:blogger.com,1999:blog-6655746112052720933.post5437633252415184155..comments2015-03-27T22:59:16.733-05:00Comments on Notes on Haskell: Taxicab NumbersAdam Turoffhttp://www.blogger.com/profile/11941071792943377879noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6655746112052720933.post-37888943926845888242007-12-30T03:32:00.000-05:002007-12-30T03:32:00.000-05:00Taxicab numbers is a really interesting and non-tr...Taxicab numbers is a really interesting and non-trivial problem, and this is a good chance for demonstrating the power of Haskell.<BR/><BR/>But your code isn't the best way to do it, because any language even assembly can do the same thing, which is essentially nested for-loops. Writing this in C is also fun and quite throwaway.<BR/><BR/>#include <stdio.h><BR/>#include <stdlib.h><BR/><BR/>int cubesum (int x, int y)<BR/>{<BR/> return x*x*x + y*y*y;<BR/>}<BR/><BR/>int main(int ac, char **av)<BR/>{<BR/> int n = 20;<BR/> if (ac > 0) n = atoi(av[1]);<BR/><BR/> for (int a = 1; a <= n; a++)<BR/> for (int b = a+1; b <= n; b++)<BR/> for (int c = a+1; c <= n; c++)<BR/> for (int d = c+1; d <= n; d++) {<BR/> int ab = cubesum(a,b);<BR/> if (ab == cubesum(c,d))<BR/> printf("(%d,(%d,%d),(%d,%d))\n", ab, a, b, c, d);<BR/> }<BR/>}<BR/><BR/>$ ./a.out 20<BR/>(1729,(1,12),(9,10))<BR/>(4104,(2,16),(9,15))<BR/><BR/>Trivial things are also trivial in C or any other language.<BR/><BR/>The point here is that: don't let our emotions be against other languages and restrict the ways of thinking.<BR/><BR/>Haskell is much higher level than C, and it lets us use much more abstraction, but it hides so much about complexity, as if everything is for free. But there is no free lunch, especially when we stop to reason about it! Thinking about how you could write the program in C would help you know the complexity and clarify your ideas. You don't need to actually write it down, but you will be much happier when you have proved that the few lines of Haskell code actually achieves the same complexity with the best C code you could write for the same problem.<BR/><BR/>I doubt you can get the third taxicab number(87539319) in reasonable time, because with for-loops you will have O(n^6) complexity.<BR/><BR/>The point here is that: thinking in a restricted way of patterns, list comprehensions, generics will prevent us from discovering some natural solution that could be discovered if we were using a low level language such as C. To see how this works, after thinking in C (or matlab) for some time you will find that we don't actually need to compare every possible pairs of numbers. The cube sums x^3+y^3 actually form such a matrix:<BR/><BR/>2 9 28 65 126 217 ...<BR/>9 16 35 72 133 224 ...<BR/>28 35 54 91 152 243 ...<BR/>65 72 91 128 189 280 ...<BR/>126 133 152 189 250 341 ...<BR/>217 224 243 280 341 432 ...<BR/>... ... ... ... ... ... ...<BR/><BR/><BR/>If we do a contour plot with some tool like Matlab or Mathematica, we will see that the numbers are ascending from north-west to south-east like parabolic waves. We just need to use some data structure to keep the wavefront in a sorted manner and enumerate the pairs in the direction the wave propagates, and try to find two-in-a-rows (or three-in-a-rows) with the same cube sum. This will reduce time complexity to O(n^2*log(n)). This is still pretty bad and it will fail to find the fourth taxicab number, but it can find the third one in seconds. It will really take some effort to find the fifth one or prove that taxicab(n) exists for every n!<BR/><BR/>To program this accelerated algorithm with a conventional language isn't too hard, but it could take quite some time for me to fiddle with my home-made heaps or balanced trees. Only in this case will Haskell help.Yinhttp://www.blogger.com/profile/09057963026824934993noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-30995684206864826722007-12-28T10:23:00.000-05:002007-12-28T10:23:00.000-05:00In this case with a little care you can avoid boun...In this case with a little care you can avoid bounding the search.<BR/><BR/>Suppose we want a≤b and c≤d.<BR/>If we also choose a<c it is easy to see that we must have b>d and this means that a<b (equality isn't possible).<BR/><BR/>This is enough to write out the solution:<BR/><BR/>taxi = [(cube a + cube b, (a, b), (c, d))<BR/> | b <- [1..],<BR/> a <- [1..b-1],<BR/> c <- [a+1..b-1],<BR/> d <- [c..b-1],<BR/> cube a + cube b == cube c + cube d]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-53842306965989302022007-12-27T20:21:00.000-05:002007-12-27T20:21:00.000-05:00in Python:def cube(x): return x * x * x def ta...in Python:<BR/><BR/>def cube(x): <BR/> return x * x * x <BR/><BR/>def taxicab(n): <BR/> return [(cube(a) + cube(b), (a, b), (c, d)) <BR/> for a in range(1, n + 1) <BR/> for b in range(a + 1, n + 1) <BR/> for c in range(a + 1, n + 1) <BR/> for d in range(c + 1, n + 1) <BR/> if cube(a) + cube(b) == cube(c) + cube(d)]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-4274399793827586662007-12-26T16:43:00.000-05:002007-12-26T16:43:00.000-05:00Python based its list comprehensions on Haskell so...Python based its list comprehensions on Haskell so the implementation there is very similar:<BR/><BR/>def taxicab(n):<BR/> return [(a**3+b**3, (a,b),(c,d))<BR/> for a in range(n)<BR/> for b in range(a+1,n)<BR/> for c in range(a+1,n)<BR/> for d in range(c+1, n)<BR/> if a**3+b**3==c**3+d**3]<BR/><BR/>>>> taxicab(11)<BR/>[]<BR/>>>> taxicab(13)<BR/>[(1729, (1, 12), (9, 10))]<BR/>>>> taxicab(21)<BR/>[(1729, (1, 12), (9, 10)), (4104, (2, 16), (9, 15))]<BR/>>>>Andrew Dalkehttp://www.blogger.com/profile/17091314849699854287noreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-25979410434418575392007-12-26T14:29:00.000-05:002007-12-26T14:29:00.000-05:00Could not agree more and I wish more people especi...Could not agree more and I wish more people especially from the computer science and math fields read your article. Too many people ignore what they are trying to do and focus on the how - or - get into "religious" wars on which language/editor/compiler/tool to use.Satynoreply@blogger.comtag:blogger.com,1999:blog-6655746112052720933.post-63864742161602291992007-12-26T13:19:00.000-05:002007-12-26T13:19:00.000-05:00For Pythonistas:def taxicab(n): for a in xrange(1,...For Pythonistas:<BR/><BR/>def taxicab(n):<BR/> for a in xrange(1, n):<BR/> for b in xrange(a+1, n):<BR/> for c in xrange(a+1, n):<BR/> for d in xrange(c+1, n):<BR/> if a**3 + b**3 == c**3 + d**3:<BR/> yield a**3 + b**3, (a, b), (c, d)<BR/><BR/>That builds a generator.<BR/><BR/>Of course, that also can be done with list comprehensions, borrowed from Haskell:<BR/><BR/>def taxicab(n):<BR/> return [(a**3 + b**3, (a, b), (c, d)) for a in xrange(1, n) for b in xrange(a+ 1, n) for c in xrange(a+1, n) for d in xrange(c+1, n) if a**3 + b**3 == c**3 + d**3]Joseph Javier Perlahttp://www.jperla.com/noreply@blogger.com