John Gietzen
Reputation
1,058
Top tag
Next privilege 2,000 Rep.
 Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? @StevenStadnicki: Cool, thanks for your help! Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? @StevenStadnicki: FYI, I'm treating the strings themselves as queues by taking a substring of all but the first character for each replacement. Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? @Steven, I don't think that I will actually have 3/4 of the full path on the stack, since the elements in the stack are stored unexpanded. Only when I encounter a replacement do I push the expanded form onto the stack. This is essentially equivalent to a recursive solution, but is easier to implement as an iterator. Aug 4 comment Is it possible to generate an $M$-order Hilbert Curve without consuming $O(M^2)$ memory? I would like to generate "the" Hilbert curve, which I would then adapt to my specific use case. My only criteria is that the interface is a sequence of relative moves (N, S, E, W) and that it consumes a linear or sub-linear amount of memory with respect to the order. May 26 comment Is there a function that grows asymptotically faster than the Busy Beaver numbers? I thought that a "super turing machine" was paradoxical? Oct 4 comment Puzzle: Generate the Highest Bounded Number Using a Limited Number of Characters @SrivatsanNarayanan, that was an excellent read. Jul 29 comment Is there a closed-form equation for $n!$? If not, why not? @ShreevatsaR: Well, because the n! is formally defined as $n!=\prod_{k=1}^n k$, which is not closed form. en.wikipedia.org/wiki/Closed-form_expression an expression is said to be a closed-form expression if, and only if, it can be expressed analytically in terms of a bounded number of certain "well-known" functions. Jul 26 comment Algorithm for calculating $A^n$ with as few multiplications as possible Isn't this a Project Euler problem? Jul 23 comment What is the most efficient way to determine if a matrix is invertible? Well, I haven't learned the proof yet... I don't think he even mentioned how it is done... Jul 23 comment What is the most efficient way to determine if a matrix is invertible? Thanks. I imagine that proving that is quite an enormous amount of work. Jul 23 comment How do you prove that a prime is the sum of two squares iff it is congruent to 1 mod 4? @Akhil: It is acceptable to answer your own question. Jul 22 comment How can you prove that the square root of two is irrational? Thanks! This is quite clear. Jul 22 comment Is there a closed-form equation for $n!$? If not, why not? This is indeed the only possible correct answer, apparently: (from Wikipedia) There is, in fact, no such simple solution for factorials; any combination of sums, products, powers, exponential functions, or logarithms with a fixed number of terms will not suffice to express $n!$. Jul 22 comment What is a real number (also rational, decimal, integer, natural, cardinal, ordinal…)? @Harry: No kidding? Read the comments. Jul 21 comment Is there a closed-form equation for $n!$? If not, why not? @Mgccl, indeed I did. I guess I was just assuming that multiplications on a modern PC is a single clock cycle. That breaks down when dealing with large enough factorials that it would matter, tho. Jul 21 comment Is there a closed-form equation for $n!$? If not, why not? Really, I'm looking for something whose complexity to calculate is better than $O\left( n\right)$ Jul 21 comment Calculating the probability of two dice getting at least a $1$ or a $5$ @Pieces: if you want the TeX formatting to light up, I have created a GreaseMonkey script: userscripts.org/scripts/show/81977 Jul 21 comment Why does the series $\sum_{n=1}^\infty\frac1n$ not converge? Is there a closed-form function for this value? Jul 20 comment Faulty logic when summing large integers? This problem is actually small enough to use a BigNum implementation, like BigInteger in .NET 4.0. Jul 20 comment Calculating an Angle from $2$ points in space There is no angle between two points... Do you mean the angle between the points at the origin? Maybe?