Continued Fractions

I was working on some continued fractions, and came across the fundamental recurrence formula above. It worked pretty well for some simple continued fractions (like √2) but seemed to be a bit unfriendly towards calculating π.

I'm using this definition of π:


Now, using that definition with the above equation, it was always completely wrong...

So I tried changing the equation...

So you'll notice a few specific changes... 1) A₁ has been redefined in terms of previous results. 2) A₁ reduced the index on a₁ to a₀. 3) A_n+1 changed the index on a_n+1 to a_n. 4) B_n+1 changed the index on b_n+1 to b_n.

This may seem like a lot of changes, but really #1 didn't change the outcome at all and the rest were all about reducing the index of a/b.

Net result? All the previous stuff (√2, golden mean, etc) give the same results as before... but now π works.

Subfactorial

I thought this was a good way of explaining it:
In practical terms, subfactorial is the number of ways of putting n letters into n envelopes (one in each envelope) with none in its correct envelope.

Mock Theta Functions

Sum of Series

sum of odd integers < 2n = n²

sum of all integers = n(n+1)/2

Shor's Algorithm

1. Pick a random number a < N
2. Compute gcd(a, N). This may be done using the Euclidean algorithm.
3. If gcd(a, N) ≠ 1, then there is a nontrivial factor of N, so we are done.
4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:

   ,

   i.e. the smallest integer r for which f(x + r) = f(x).
5. If r is odd, go back to step 1.
6. If a ^r/2 ≡ -1 (mod N), go back to step 1.
7. The factors of N are gcd(a^r/2 ± 1, N). We are done.

Origin of Quake3's Fast InvSqrt()