Time with class! Let's Count!
June 12, 2015 11:44 AM Subscribe
I want to demonstrate how amazing combinatorial explosion is! Please don't stop me. An animation about numbers that get large. It has a happy ending and possibly even a moral.
About those "latest algorithmic techniques" mentioned at the end: Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions [PDF]
About those "latest algorithmic techniques" mentioned at the end: Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions [PDF]
On page 15 of the pdf, it shows the the number of digits in the path count has an exponential curve.
Wow.
posted by idiopath at 12:11 PM on June 12, 2015 [2 favorites]
Wow.
posted by idiopath at 12:11 PM on June 12, 2015 [2 favorites]
Keep doing the same thing, no matter how painful. Eventually, someone will automate your life's work with a better algorithm.
Actually, the moral is buried in footnotes 8 and 9 of the cited paper and it is this:
"Whatever you just thought of, no matter how clever you think it is, chances are Don Knuth thought of it first."
posted by The Bellman at 12:15 PM on June 12, 2015 [5 favorites]
Actually, the moral is buried in footnotes 8 and 9 of the cited paper and it is this:
"Whatever you just thought of, no matter how clever you think it is, chances are Don Knuth thought of it first."
posted by The Bellman at 12:15 PM on June 12, 2015 [5 favorites]
"Discrete Structure Manipulation System Project" is a great name for a manipulation system project.
posted by moonmilk at 12:24 PM on June 12, 2015 [7 favorites]
posted by moonmilk at 12:24 PM on June 12, 2015 [7 favorites]
This post came about in part because I had some 2nd grade students assembling snap cubes into larger cubes such as a 2x2x2, 3x3x3, and so on. This can actually be a little bit of a puzzle for them because each snap cube has only one post and you have to plan at least a little bit carefully in order to ensure that the whole structure is connected together. I was curious about how many different ways you can orient the snap cubes to get a 3x3x3 cube that is connected, without having any posts left sticking out (so that it will lie flat on any face).
It took some work to show that the number of ways to make a 2x2x2 cube satisfying my requirements is 5,926. A 2x2x3 brick can be put together in 111,370 ways.
I can estimate that the number of ways to make a 3x3x3 cube is 7.2x1013, that is, about 72 trillion. Finding the exact number would require the use of a specialized algorithm similar to what's being discussed in the animation.
Anecdotally, the probability of a 2nd grader finding one of those 72 trillion possibilities before getting frustrated is, I'd say, about 20%.
posted by Wolfdog at 12:27 PM on June 12, 2015 [7 favorites]
It took some work to show that the number of ways to make a 2x2x2 cube satisfying my requirements is 5,926. A 2x2x3 brick can be put together in 111,370 ways.
I can estimate that the number of ways to make a 3x3x3 cube is 7.2x1013, that is, about 72 trillion. Finding the exact number would require the use of a specialized algorithm similar to what's being discussed in the animation.
Anecdotally, the probability of a 2nd grader finding one of those 72 trillion possibilities before getting frustrated is, I'd say, about 20%.
posted by Wolfdog at 12:27 PM on June 12, 2015 [7 favorites]
math can save your life!
(also, I see what they did there with "you have the wrong number")
posted by chavenet at 12:37 PM on June 12, 2015 [2 favorites]
(also, I see what they did there with "you have the wrong number")
posted by chavenet at 12:37 PM on June 12, 2015 [2 favorites]
If Gauss's schoolteacher had had snap cubes, he could have assigned much more intractable busywork.
posted by Wolfdog at 12:38 PM on June 12, 2015 [4 favorites]
posted by Wolfdog at 12:38 PM on June 12, 2015 [4 favorites]
the number of digits in the path count has an exponential curve
Well this is true for any exponential function, right?
posted by grog at 12:58 PM on June 12, 2015
Well this is true for any exponential function, right?
posted by grog at 12:58 PM on June 12, 2015
the number of digits in the path count has an exponential curve
Well this is true for any exponential function, right?
Are you asking whether every exponential function has the property that the number of digits in its output is also an exponential function? I don't think so -- one example being the function y = 2^x.
posted by klausman at 1:18 PM on June 12, 2015
Well this is true for any exponential function, right?
Are you asking whether every exponential function has the property that the number of digits in its output is also an exponential function? I don't think so -- one example being the function y = 2^x.
posted by klausman at 1:18 PM on June 12, 2015
for an exponential function, the value would have an exponential curve
this is something geometric, where the log10 of the value has an exponential curve
posted by idiopath at 1:18 PM on June 12, 2015
this is something geometric, where the log10 of the value has an exponential curve
posted by idiopath at 1:18 PM on June 12, 2015
Strangely, the Tutte polynomial does not feature anywhere in the Virginia Standards of Learning.
posted by Wolfdog at 1:35 PM on June 12, 2015 [1 favorite]
posted by Wolfdog at 1:35 PM on June 12, 2015 [1 favorite]
Well this is true for any exponential function, right?
The number of digits in a number is approximately log10x. So, for example, the number of digits in 2x is approximately linear: log10 (2x) = x (log102). To get a function f(x) where the number of digits grows exponentially, you need a function like f(x) = 22x.
posted by Johnny Assay at 1:48 PM on June 12, 2015 [3 favorites]
The number of digits in a number is approximately log10x. So, for example, the number of digits in 2x is approximately linear: log10 (2x) = x (log102). To get a function f(x) where the number of digits grows exponentially, you need a function like f(x) = 22x.
posted by Johnny Assay at 1:48 PM on June 12, 2015 [3 favorites]
I think the moral is that if you watch long enough, you get to see a baby zebra
posted by Mchelly at 1:59 PM on June 12, 2015 [2 favorites]
posted by Mchelly at 1:59 PM on June 12, 2015 [2 favorites]
It's a hoot that the video is cited in the paper.
posted by CBrachyrhynchos at 2:01 PM on June 12, 2015
posted by CBrachyrhynchos at 2:01 PM on June 12, 2015
And a dumb question of the day, what's the origin of that computer beeping noise? It must be up there with the Wilhelm Scream and Red Hawk Screech in terms of iconic sound effects.
posted by CBrachyrhynchos at 2:26 PM on June 12, 2015 [2 favorites]
posted by CBrachyrhynchos at 2:26 PM on June 12, 2015 [2 favorites]
What is the name of the feeling of getting slightly dizzy and a little nauseous when things snap into place and your brain actually starts to truly get the concept of the difference between something small and relatable and something so completely alien to your mind that you feel it trying to recoil in horror.
It's almost like finally understanding what looking at an Elder God would actually do to your brain, only it's just numbers, yet the feeling and effect seems the same. I think my brain just halted and caught fire.
posted by daq at 3:33 PM on June 12, 2015
It's almost like finally understanding what looking at an Elder God would actually do to your brain, only it's just numbers, yet the feeling and effect seems the same. I think my brain just halted and caught fire.
posted by daq at 3:33 PM on June 12, 2015
Yeah, but Moore's Law. We could do that final calculation in an eighth the time!
Also, I want a SUPER COMPUTER.
I
It is rather sobering that all there is on the 11x11 grid are 121 points with between two and four options to choose at each, and yet the combinatorial explosion hits the limits of the lifetime of the universe if you try to brute force it. You really can't get very far unless you find patterns.
posted by Devonian at 5:18 PM on June 12, 2015
Also, I want a SUPER COMPUTER.
I
It is rather sobering that all there is on the 11x11 grid are 121 points with between two and four options to choose at each, and yet the combinatorial explosion hits the limits of the lifetime of the universe if you try to brute force it. You really can't get very far unless you find patterns.
posted by Devonian at 5:18 PM on June 12, 2015
(Oh, and CBrachyrhynchos? I don't know what the origin of that sound is, but I do know that when I was 16 and had my first computer, which was a ZX81 with a 3.25 MHz Z80 and 1K of RAM and only a one-bit port to waggle to make any sort of audio, the very first machine code program I wrote that did anything of interest made exactly that noise. And a GIRL who came round to see me was REALLY AMAZED that I'd done that. If it has an origin, I think it's the cosmic background signal of mankind and mathematics merging. That the paper mentioned "Experiments were performed on 2.67GHz Intel Xeon E7-8837 CPUs with 1.5TB memory, running 64-bit SUSE Linux Enterprise Server 11." - the 16 year old Devonian just fainted - and still links to the noise... well, case proven.)
posted by Devonian at 5:39 PM on June 12, 2015
posted by Devonian at 5:39 PM on June 12, 2015
That was really neat!
Although I'm not entirely sure what to make of that last bit, after the supercomputer has been churning away for 250,000 years and then they are all like "Oh, btw, with a better algorithm, you can actually calculate it in 20 minutes. On your mobile."
WTF?
I guess the moral of that is, before you clog all our supercomputer resources with your shoddy little program for the next 250,000 years, maybe step back for a minute and try to figure out if there is a more efficient algorithm.
posted by sour cream at 11:52 AM on June 13, 2015
Although I'm not entirely sure what to make of that last bit, after the supercomputer has been churning away for 250,000 years and then they are all like "Oh, btw, with a better algorithm, you can actually calculate it in 20 minutes. On your mobile."
WTF?
I guess the moral of that is, before you clog all our supercomputer resources with your shoddy little program for the next 250,000 years, maybe step back for a minute and try to figure out if there is a more efficient algorithm.
posted by sour cream at 11:52 AM on June 13, 2015
There are 74,571,238,440,960 ways to orient the snap cubes to build a connected, 3x3x3 cube with no posts sticking out.
posted by Wolfdog at 11:32 AM on June 22, 2015 [1 favorite]
posted by Wolfdog at 11:32 AM on June 22, 2015 [1 favorite]
« Older This is how Alt-J makes music | Occupation: Housewife Newer »
This thread has been archived and is closed to new comments
Keep doing the same thing, no matter how painful. Eventually, someone will automate your life's work with a better algorithm.
posted by klausman at 12:07 PM on June 12, 2015 [2 favorites]