Jonathan50 wrote:

BookOwl wrote:

@Jonathan50, than why are you saying that recursion is better than looping? It can't be state because you have to maintain state in both versions, the difference is that in the recursive version you use arguments and in the looping version you use parameters.
It appeared to me that you were saying that fib(n) = fib(n - 1) + fib(n - 2) is tail recursive. Sorry for misunderstanding you.

For a while loop to end then state needs to change.

But you are still changing state (by passing different argument) in the tail-recursive one, and you end by comparing to that state, so I still do't see a difference…

BookOwl wrote:

bharvey wrote:

The iterative code for Euclid's GCD algorithm, for example, is almost identical to the iterative code for Fib

Maybe this means that they are related somehow…

I've found out that at least for n < 1000, gcd(fib(n), fib(n-1) == 1. Now to figure out why…

BookOwl wrote:

Jonathan50 wrote:

BookOwl wrote:

@Jonathan50, than why are you saying that recursion is better than looping? It can't be state because you have to maintain state in both versions, the difference is that in the recursive version you use arguments and in the looping version you use parameters.
It appeared to me that you were saying that fib(n) = fib(n - 1) + fib(n - 2) is tail recursive. Sorry for misunderstanding you.

For a while loop to end then state needs to change.

But you are still changing state (by passing different argument) in the tail-recursive one, and you end by comparing to that state, so I still do't see a difference…

I don't think that is changing state…?

Jonathan50 wrote:

BookOwl wrote:

Jonathan50 wrote:

BookOwl wrote:

@Jonathan50, than why are you saying that recursion is better than looping? It can't be state because you have to maintain state in both versions, the difference is that in the recursive version you use arguments and in the looping version you use parameters.
It appeared to me that you were saying that fib(n) = fib(n - 1) + fib(n - 2) is tail recursive. Sorry for misunderstanding you.

For a while loop to end then state needs to change.

But you are still changing state (by passing different argument) in the tail-recursive one, and you end by comparing to that state, so I still do't see a difference…

I don't think that is changing state…?

I guess that it isn't technically, but it sure feels like it.

Yeah, there isn't really any advantage to using recursion other than being a FP zealot, especially since JS isn't tail-call optimized.

bharvey wrote:

I tell them that when the class is over, they should approach each new problem with an open mind about the best programming style for that problem, but while they're in the course they're going to do it my way because I said so.

Can confirm

BookOwl wrote:

Please jens? For me and my ancient laptop?

The rhetoric is wasted for another two weeks, when Jens gets back.

Project loading really needs to be made async

But meanwhile let me see if I understand this. You don't mean that you want to be able to do stuff in Snap! while the project is loading, right? You just want it to yield once in a while so your browser can update other tabs. Will that be hard? I guess the hard part is that JS kills your stack in between running you, so the loading process has to keep a lot of state somewhere else.

Arguing is good! It's fighting that isn't.

Oh yeah? Well I think you're wrong. Fighting is good. Put up your dukes!

The codification example has several bugs in the map to Python block.

So, you gonna fix them, or tell us what they are, or just leave it at that?

Safely try is beautiful.

bharvey wrote:

Maybe this means that [fib and gcd] are related somehow…

Yes, this is a more interesting contribution! We'll ask hm; that's easier than thinking about it.

Indeed! You asked for it, Brian…

You can approximate pi as 22/7, which is about 3.143. This approximation is accurate to within 0.002, but 1/7 is 0.14. That means 22/7 seems to “accidentally” be a ridiculously good approximation given the denominator. (Of course you can get a good approximation as, say, 3141/1000, but that's a huuuuge denoniminator!).

Is this a coincidence? Let's find out.

Well, Hurwitz' theorem states that for any irrational number a, there are an infinite number of coprime integers p, q such that

| a - p/q | < 1/(q*q*√5)

That is, you can find an infinite number of fractions such that a is “very close” to the fraction, where “very close” is based on the denominator so that the larger the denominator, the closer you need to be.

It turns out that that suspicious-looking √5 term is “sharp”: any higher, and there are only a finite number of pairs (p, q) that satisfy the condition for certain irrational a. Why such a suspicious-looking term?

Well, to find a rational approximation for a number, you essentially have to do Euclidean GCD on it—each step of the algorithm gives you a better rational approximation. (The reason I know so much about this is that back when I used to blog, I wrote about rational approximation here, where I used this technique to prove that the first 8 digits of the 147453447-digit number 1337^47168026 are “31415926…”.)

Now, intuitively, it may make sense to you that consecutive Fibonacci numbers happen to be the “hardest” on which to do Euclidean GCD, because you have to do the most steps. From this, it turns out that the golden ratio is the “hardest” irrational to rationally approximate (bear with me, I know I'm handwaving a bit because I don't want to type algebra on the forums). And, as we all know, the golden ratio has a √5 in it. Hence, the √5 in Hurwitz' theorem.

EDIT: The lesson here is “say no to drugs, say yes to mathematics”.

Hardmath123 wrote:

EDIT: The lesson here is “say no to drugs, say yes to mathematics”.

What do drugs have to do with this…?

Does Snap! have inheritance yet?

Jonathan50 wrote:

Does Snap! have inheritance yet?

I tried

and after the run delete line it still said 1, and the delete block's dropdown had no options. (I got the delete block by enabling the “Inheritance support” feature. And foo is a sprite-local variable.)

Is Snap supposed to work on mobile devices?

Hardmath123 wrote:

Now, intuitively, it may make sense to you that consecutive Fibonacci numbers happen to be the “hardest” on which to do Euclidean GCD, because you have to do the most steps.

Isn't the GCD of consecutive fibs always 1?

It's a weird theorem because if it weren't for that irrational denominator I'd expect it to be a theorem of number theory. How did he prove it? (I'm not asking for the actual proof, just the equivalent of “he used elliptic curves.”)

Jonathan50 wrote:

Does Snap! have inheritance yet?

Bits of it. If you're going to experiment, use the …/snapsource/dev/snap.html version. Jens expects to finish it up pretty soon after returning from vacation.

joefarebrother wrote:

Is Snap supposed to work on mobile devices?

Yes and no. There is a very strange bug about using the software keyboard on Android devices that's Android's fault, but it works with hardware keyboards. And pinch-zoom isn't quite right on any mobile, so it's a pain in the neck. It works great, though, for playing projects developed on your computer.

bharvey wrote:

Hardmath123 wrote:

Now, intuitively, it may make sense to you that consecutive Fibonacci numbers happen to be the “hardest” on which to do Euclidean GCD, because you have to do the most steps.

Isn't the GCD of consecutive fibs always 1?

Yes, but if you naively take two Fibonacci numbers and GCD them with Euclid's algorithm, it'll take a long time to get to 1 (as compared to, say, 49 and 99, which get to 1 in just one step).

It's a weird theorem because if it weren't for that irrational denominator I'd expect it to be a theorem of number theory. How did he prove it? (I'm not asking for the actual proof, just the equivalent of “he used elliptic curves.”)

It is a theorem of number theory. There are multiple proofs that I know of—one involving continued fractions and the other involving drawings of circles. You can find some sketches (of both circles and proofs) here http://www.cimat.mx/~gil/docencia/2008/elementales/circulos_ford.pdf

Hardmath123 wrote:

You can find some sketches (of both circles and proofs) here http://www.cimat.mx/~gil/docencia/2008/elementales/circulos_ford.pdf

Man, I've really lost it. I got stuck on the “-1” in the formula for the distance between two centers. I did see the change of sign in the vertical component and so I gather the -1 makes up for that, but I just can't get the algebra to work. So I just took that as given and forged ahead, but I can't make sense of the curve L… I'm getting old. There's nothing in there that I just plain never learned about; the proof is, as he says, “elementary” in the technical sense.

So it turns out the fill block is SUPER inefficient.

It was causing my project to actually run out of memory.

Anyone know the easiest way to turn snap coords into canvas coords, so I can use .fillRect() instead?

joefarebrother wrote:

So it turns out the fill block is SUPER inefficient.

It was causing my project to actually run out of memory.

Anyone know the easiest way to turn snap coords into canvas coords, so I can use .fillRect() instead?

Use your own canvas?