←back to thread

Analytic Combinatorics – A Worked Example

(grossack.site)
105 points mathgenius | 2 comments | 08 Apr 25 17:29 UTC | HN request time: 3.211s | source
Show context
PollardsRho ◴[08 Apr 25 18:37 UTC] No.43625111[source]▶
Very cool!

What's meant by "it’s already too much to ask for a closed form for fibonacci numbers"? Binet's formula is usually called a closed form in my experience. Is "closed form" here supposed to mean "closed form we can evaluate without needing arbitrary-precision arithmetic"?

replies(3): >>43625353 #>>43626182 #>>43626796 #
1. aleph_minus_one ◴[08 Apr 25 20:35 UTC] No.43626182[source]▶
> Is "closed form" here supposed to mean "closed form we can evaluate without needing arbitrary-precision arithmetic"?

You don't need arbitrary-precision arithmetic to evaluate Binet's formula - big integer arithmetic suffices (simply do your calculations in the ring Z[X]/(X^2-X-1) ).

replies(1): >>43659214 #
2. PollardsRho ◴[11 Apr 25 22:09 UTC] No.43659214[source]▶
At that point, you'd be better off just using a recursive algorithm like the one in GMP. You're swapping out arbitrary-length for arbitrary-precision.