Skip to content

Instantly share code, notes, and snippets.

@rwst

rwst/general_binet

Last active Jan 3, 2016
Embed
What would you like to do?
The general Binet form of the nth element of a binary recurrence over the integers is, given a(n) = c*a(n-1) + d*a(n-2). The Pari code is blinding fast, dependent on precision. It can maybe jump in when a floating point result is sufficient. The Sage function gives an expression in square roots.
(Pari/GP)
a(c,d,a0,a1,n)=my(r1,r2,s);s=sqrt(c^2+4*d);r1=2*d/(-c+s);r2=2*d/(-c-s);return(((a1-c*a0+a0*r1)*r1^n-(a1-c*a0+a0*r2)*r2^n)/s)
(Sage)
def a(c,d,a0,a1,n):
r1=2*d/(-c+sqrt(c^2+4*d))
r2=2*d/(-c-sqrt(c^2+4*d))
return ((a1-c*a0+a0*r1)*r1^n-(a1-c*a0+a0*r2)*r2^n)/sqrt(c^2+4*d)
@rwst

This comment has been minimized.

Copy link
Owner Author

@rwst rwst commented Jan 21, 2014

Proof of gist fomula

@rwst

This comment has been minimized.

Copy link
Owner Author

@rwst rwst commented Jan 21, 2014

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.