The Nineteenth Byte

9:09 PM

is there a general method for solving recurrence relations of the form x[i+1]=A*x[i]+B*y[i]; y[i+1]=C*x[i]+D*y[i]? (x[0] and y[0] are given)

caird coinheringaahing

@ngn Are C and D both reals?

ngn

@cairdcoinheringaahing yes

caird coinheringaahing

Then can't you simplify it to y[i+1]=C*y[i], and use that (where C := C + D)?

rak1507

I guess it was a typo, maybe D*x[i]?

ngn

@cairdcoinheringaahing that would help take only one step, i need a direct formula for the i-th

rak1507

9:18 PM

raise to the power n

ngn

for A,B,C,D = 1,0,1,1 this is fibonacci and there's binet's formula (something involving powers of the golden ratio), so i thought there might be a general method

hyper-neutrino

if this is linear just use a matrix

if it's diagonalizable you have an easy O(1) closed form

ngn

@rak1507 argh.. sorry, it should be C*x[i], too late to edit

caird coinheringaahing

y[i+1] = C*y[i] can just be written as y[n] = y[0]*C^n

Oh, then ignore me

hyper-neutrino

want me to retroactively edit it to avoid confusion?

ngn

9:20 PM

@hyper-neutrino that would be nice, thanks

caird coinheringaahing

Pretty sure you can still express it as [x'; y'] = [A B; C D][x; y] and you can use various methods from there

ngn

@cairdcoinheringaahing yes, and the matrix is raised to the i-th power

caird coinheringaahing

My linalg isn't great, but don't the eigenvectors then produce the solution?

hyper-neutrino

you should be able to diagonalize this

idk a general solution if [A B ; C D] can't be diagonalized ¯\_(ツ)_/¯

ngn

@hyper-neutrino to diagonalize means to represent it as P^-1 M P where M has nonzero elements only along the diagonal?

i see. and when we raise this to a power most Ps and P^-1s will cancel out.

(P^-1 M P)^n = P^-1 M^n P

hyper-neutrino

9:30 PM

uh. yes, precisely (hoping my memory of linalg hasn't deterioriated that fast :p)

yes that is correct

ngn

and since M is a diagonal matrix, ^n is just elementwise ^n

hyper-neutrino

the elements along Ms diagonal will be its eigenvalues (k is an eigenvalue if Mx=kx for some non-zero vector x)

yes exactly

ngn

@cairdcoinheringaahing ^ now that makes sense :)

hyper-neutrino

iirc you can get the eigenvalues by taking the determinant of M-xI and solving the polynomial for x

or just plug it into sympy / whatever math thing your language has, lol

ngn

i'm using just primitive tools: paper, pencil, and a c compiler :)

hyper-neutrino

9:32 PM

well, at least it's a 2x2, so it shouldn't be too bad :P

your eigenvalues will be the roots of the polynomial (A - x)(D - x) - BC

i think

rak1507

you can use my handy APL implementation ;) codegolf.stackexchange.com/questions/44926/…

caird coinheringaahing

@hyper-neutrino Yeah, that's correct

hyper-neutrino

i just finished my linalg course like two weeks ago so i hope i'd still remember this stuff. :P

ngn

i finished mine 20y ago and i've fogotten a lot of stuff

New Sandboxed Posts

0

A: Sandbox for Proposed Challenges

CGCC sings a song together This is a code-shuffleboard answer-chaining challenge, where the answers will aim to, together, output the lyrics to this beloved 80s song. This is the full lyrics of the song, line by line. The first answer will contain a program that will output the first line of the...

caird coinheringaahing

9:36 PM

Q: What do downvotes here mean? That the downvoters want the tag system to stay as is?

ngn

@rak1507 thanks, but that's a formula only for the eigenvector. to solve the recurrence, i guess i'll need the matrices P and P^-1 too.

hyper-neutrino

9:52 PM

I think P is just the eigenvectors

and D is the diag(the eigenvalues)

caird coinheringaahing

> If you call me a weeb I will 11 you.

I very much want to call you a weeb now :P

hyper-neutrino

that didn't take you much time to notice

caird coinheringaahing

New Posts + I'm a quick reader :P

hyper-neutrino

oh yeah i forgot about New Posts. accidentally closed the tab sometime ago i guess, cuz i don't have it open anymore

lyxal

10:49 PM

@cairdcoinheringaahing wait people downvoted it?

caird coinheringaahing

@lyxal Yep, +32/-2

Clearly it was Jeff being mad that I criticised his regex :P

3

user

11:15 PM

I need to get TNB streamed directly to my brain, I miss too much when I'm not around

Bubbler

@ngn Is it PE related? I thought every single problem involving a (possibly mutual) recurrence was asking nth value modulo P

ngn

@Bubbler yes (PE) and yes (it's mod something, though not prime) :)

Bubbler

(and I have a piece of code that solves a recurrence from first x values mod P and quickly escalate it to large n... it's kinda half-cheating, but it works insanely well)

ngn

@Bubbler this is a bit more complicated as the elements of the sequence are pairs

@Bubbler i'm trying to get a direct formula for a and b in (1+sqrt(7))^n = a(n) + b(n)sqrt(7)

then a(n) and b(n) must match given numbers mod something

[a(n),b(n)] = [[1,7],[1,1]]^n * [1,0]

Bubbler

It can't be more complicated than PE654 which involves 5000x5000 recurrence matrix

ngn

11:27 PM

@Bubbler there must be a simpler way.. i'm gonna give it a try

Bubbler

And for accelerating a non-mutual recurrence, this paper published this year works great

ngn

@Bubbler did you manage to get to the result?

Bubbler

@ngn PE654? Yes, in ten seconds.

ngn

so, if we have a vector v for which v[i] is the number of sequences ending with i, from it we can get to such a vector for the longer sequences by a linear transformation

Bubbler

yes

ngn

11:40 PM

the transformation is a 5000x5000 matrix which can be raised to the power of 10^12 through some efficient method like repeated squaring

10^12 is approximately 2^40, so you'd need around 80=2*40 matrix multiplications

80*5000*5000*5000 seems like a lot though

hyper-neutrino

this answer to "tips for golfing in dart" is entirely non-specific; i'm going to leave a comment regarding the "please be somewhat specific to dart" and point them to the general golfing tip about whitespace, but do we have a policy on deletion for answers like these?

Bubbler

About half of the solution thread was complaining about matmul being too slow :P

hyper-neutrino

specificity isn't really too observable (even if in this case it's pretty obvious) so i'm not sure if we can declare answers as invalid on that basis

has anyone seen a deleted question on the front page before? i don't remember ever seeing this happen before lol

Redwolf Programs

Mod thing maybe?

ngn

@Bubbler did you use an algebra system (like pari/gp) or apl or something else? (sorry if i'm asking too much)

caird coinheringaahing

11:44 PM

I've seen it a few times

Redwolf Programs

I'd imagine most deleted questions are negatively voted to the point they won't appear on the home page

caird coinheringaahing

Mainly happens due to caching

hyper-neutrino

ah okay. i loaded 4 posts with new activity after coming back from dinner. i guess they just don't check if the posts still exist when display them, lol

@hyper-neutrino anyway i probably shouldn't have derailed my own conversation

caird coinheringaahing

@hyper-neutrino Leave a comment, if they don't respond (unlikely, they haven't been to the site in 2 years), delete in a couple of days

hyper-neutrino

wait hold up i didn't realize this answer was so old

i was looking at the wrong one lol. new posts must've pointed me here and i accidentally looked at the wrong answer :P

ok and now new posts randomly displayed an answer from 26 minutes ago even though i reloaded the page like 4 minutes ago

Bubbler

11:48 PM

@ngn I'm using Rust with my own math library

caird coinheringaahing

@hyper-neutrino Enzo just answered again to the same question, it's not a bug :P

Bubbler

@ngn For the sqrt(7) mutual recurrence, I get a(n) = 2a(n-1) + 6a(n-2) and the same for b. Got it by hand, confirmed with my mathlib

ngn

@Bubbler and you have fast matmul. cool :)

hyper-neutrino

@cairdcoinheringaahing it specifically said "26m ago" though

caird coinheringaahing

@hyper-neutrino Are you sure you've got the latest version?

hyper-neutrino

11:51 PM

not certain, but i should...? at least, i renistalled within the past few days after redwolf fixed the bug that was making it display no posts

Bubbler

@ngn Not matmul, but polynomial multiplication (which is used in the linked paper)

caird coinheringaahing

Wait, am I sure I have the latest version? I've got v0.7, isn't v0.8 out @RedwolfPrograms?

hyper-neutrino

i have v0.8.1

caird coinheringaahing

Ok, so it might actually be a bug introduced in the latest version

lyxal

You guys are using new versions?

Wow I'm really behind the trend

Redwolf Programs

11:53 PM

There are most likely a number of bugs with answers being posted at similar times in both versions

At some point I'll actually sit down and make an attempt to fix it

hyper-neutrino

how are you detecting new posts, via a feed/socket?

Redwolf Programs

Yes, the home page one

I might be able to extract some stuff from the HTML it sends, shouldn't take too much work I'll just need to find a good time

hyper-neutrino

smh just do while (true) and fetch the most recent activity and store a "last active post" to compare to

Redwolf Programs

That's what v0.8.1 should do I think

0.7 just "guesses" based on the creation date which obviously didn't work well

hyper-neutrino

wait i was joking

is that not really inefficient and bad for the servers

Redwolf Programs

11:56 PM

It's not exactly while (true)

It's a bit more advanced, but basically the same concept

ngn

@Bubbler hah. so my sequence of pairs is actually a pair of sequences which happen to use the same recurrence relation but have different initial values. thanks!

hyper-neutrino

oh okay

Redwolf Programs

It tries up to ten times, starting with a small delay then gradually increasing. The final check is something like a minute after it initially detects a new post.

I think I have an idea to dramatically reduce the error rate and loading times, though

Transcript for