#thanks for the ask! <2

[gayarograce]

🌻

(Oh man, the mortifying ordeal of actually having to pick something to talk about when I have so many ideas...)

Uh, OK, I'm talking about galactic algorithms, I've decided! Also, there are some links peppered throughout this post with some extra reading, if any of my simplifications are confusing or you want to learn more. Finally, all logarithms in this post are base-2.

So, just to start from the basics, an algorithm is simply a set of instructions to follow in order to perform a larger task. For example, if you wanted to sort an array of numbers, one potential way of doing this would be to run through the entire list in order to find the largest element, swap it with the last element, and then run though again searching for the second-largest element, and swapping that with the second-to-last element, and so on until you eventually search for and find the smallest element. This is a pretty simplified explanation of the selection sort algorithm, as an example.

A common metric for measuring how well an algorithm performs is to measure how the time it takes to run changes with respect to the size of the input. This is called runtime. Runtime is reported using asymptotic notation; basically, a program's runtime is reported as the "simplest" function which is asymptotically equivalent. This usually involves taking the highest-ordered term and dropping its coefficient, and then reporting that. Again, as a basic example, suppose we have an algorithm which, for an input of size n, performs 7n³ + 9n² operations. Its runtime would be reported as Θ(n³). (Don't worry too much about the theta, anyone who's never seen this before. It has a specific meaning, but it's not important here.)

One notable flaw with asymptotic notation is that two different functions which have the same asymptotic runtime can (and do) have two different actual runtimes. For an example of this, let's look at merge sort and quick sort. Merge sort sorts an array of numbers by splitting the array into two, recursively sorting each half, and then merging the two sub-halves together. Merge sort has a runtime of Θ(nlogn). Quick sort picks a random pivot and then partitions the array such that items to the left of the pivot are smaller than it, and items to the right are greater than or equal to it. It then recursively does this same set of operations on each of the two "halves" (the sub-arrays are seldom of equal size). Quick sort has an average runtime of O(nlogn). (It also has a quadratic worst-case runtime, but don't worry about that.) On average, the two are asymptotically equivalent, but in practice, quick sort tends to sort faster than merge sort because merge sort has a higher hidden coefficient.

Lastly (before finally talking about galactic algorithms), it's also possible to have an algorithm with an asymptotically larger runtime than a second algorithm which still has a quicker actual runtime that the asymptotically faster one. Again, this comes down to the hidden coefficients. In practice, this usually means that the asymptotically greater algorithms perform better on smaller input sizes, and vice versa.

Now, ready to see this at its most extreme?

A galactic algorithm is an algorithm with a better asymptotic runtime than the commonly used algorithm, but is in practice never used because it doesn't achieve a faster actual runtime until the input size is so galactic in scale that humans have no such use for them. Here are a few examples:

Matrix multiplication. A matrix multiplication algorithm simply multiplies two matrices together and returns the result. The naive algorithm, which just follows the standard matrix multiplication formula you'd encounter in a linear algebra class, has a runtime of O(n³). In the 1960s, German mathematician Volker Strassen did some algebra (that I don't entirely understand) and found an algorithm with a runtime of O(n^(log7)), or roughly O(n^2.7). Strassen's algorithm is now the standard matrix multiplication algorithm which is used nowadays. Since then, the best discovered runtime (access to paper requires university subscription) of matrix multiplication is now down to about O(n^2.3) (which is a larger improvement than it looks! -- note that the absolute lowest possible bound is O(n²), which is theorized in the current literature to be possible), but such algorithms have such large coefficients that they're not practical.

Integer multiplication. For processors without a built-in multiplication algorithm, integer multiplication has a quadratic runtime. The best runtime which has been achieved by an algorithm for integer multiplication is O(nlogn) (I think access to this article is free for anyone, regardless of academic affiliation or lack thereof?). However, as noted in the linked paper, this algorithm is slower than the classical multiplication algorithm for input sizes less than n^(1729^12). Yeah.

Despite their impracticality, galactic algorithms are still useful within theoretical computer science, and could potentially one day have some pretty massive implications. P=NP is perhaps the largest unsolved problem in computer science, and it's one of the seven millennium problems. For reasons I won't get into right now (because it's getting late and I'm getting tired), a polynomial-time algorithm to solve the satisfiability problem, even if its power is absurdly large, would still solve P=NP by proving that the sets P and NP are equivalent.

Alright, I think that's enough for now. It has probably taken me over an hour to write this post lol.

[i23kazu]

how i feel when someone reblogs my stuff with a really really nice tag

[hellsitegenetics]

When I followed you earlier today and then realized this blog wasn't even two days old it made me feel like I invested in a startup.

Do you think if you did the lyrics for Fireflies by Owl City, your database would give us fireflies? (Will also accept owls. And there's a line about sheep too).

String identified:

t t t t a a 'Ca t' t a A a ta ' t t t ta a ta ' t a Tat at at t t' a t a tat ' at ta Aa ' a 'Ca tg a t 'Ca ' gt a ta g t ta gtg g A t t t tac t ac A tt a a A c at A c a t agg a ta ' t a Tat at at t t' a t a tat ' at ta Aa ' a 'Ca tg a t a a a t a cac (a ta aa ) 'Ca c a ac (a ta aa ) t ctg (a ta aa ) ' a t t t a a T t ' 'ca at g gt t a t a a t ' a a a gt a a 'Ca a a a t a a ' t a Tat at at t t' a t a tat ' at ta Aa ' a 'Ca tg a t a a ' t a Tat at at t t' a t a tat ' at ta Aa ' a 'Ca tg a t a a ' t a Tat at at t t' a t a tat ' at ta Aa ' a ca a a tg at t a

Closest match: Sepia lycidas genome assembly, chromosome: 36 Common name: Kisslip cuttlefish

[hinamie]

I'm always pushing you away from me / but you come back with gravity / and when I call, you come home

[me-beef]

@strangeravatar made a great point

i was gonna focus on the spike-hotboxing-celestia aspect but i got distracted somewhere along the way and i think i forgot what joke i was trying to make

but dont you think its interesting how many guards of the exact same color/body type she's managed to accrue?? i do

ooohh you want to go look at our stickers so bad

[halemerry]

In case you were wondering I'm still thinking about the composition of this shot. The absolute split down the middle between light and dark colors. The way that despite that both sides have their own lights and their own shadows because one cannot exist without the other. The fact Aziraphale's side is a warmer sort of light that compliments Crowley's colors and Crowley's is a blueish sort of dark where the windows even look like tartan. The fact Crowley's side isn't the green dark of Hell and Aziraphale's isn't the sterile white of Heaven but are both shades shifted slightly to the left into something distinct and totally their own. It's balance - even in the middle of heartbreak - and it drives me absolutely wild.

[cupcakeruth]

LETS GOOOOOOOOO

[stealingpotatoes]

Are the Merrical kids friends with Jacen? I think they would have cousin vibes honestly, since I too headcanon that Cal and Kanan/Caleb were youngling besties!

omg yes!!! BUT CAN YOU IMAGINE HOW MUCH BETTER THAT'D BE IN A KANAN LIVES AU

(commission info // tip jar!)

[arealtrashact]

Second Verse

Part 1

[800db-cloud]

PLEASE POST THE ONE MILLION DOODLES YOU ARE SHY TO POST /pos 🙏

sure thang o7 here are some i made that i think are good enough to post. can you tell who my favorite merc to draw is

re: the last comic: i have way too many spy hcs. Way Too Many. anyway here’s (BLU) spy accidentally traumadumping on his teammates. is he Alright.

[saltpepperbeard]

We're joined to one another. Intertwined. [pic source]

[benevolenterrancy]

Art prompt of Shen Qingqiu holding the aro flag (fits his color scheme)

the real reason this man doesn't realise he's tripping every romance flag in the story

[luchigeon]

I don’t think I’ve seen Hannah Annafellows in your very cute artstyle yet. I’d love to see her and Alois in a picture, please? 🥹

little brat and proud demon mom

[picspammer]

Happy Desolation Row anniversary, released on this day in 2009 ⚡

[corantus]

mitsuki & aya from "the guy she was interested in wasn't a guy at all". so obsessed w them it's not even funny love lesbians who listen to music 💚🖤

[koipalm]

this isnt spoilers i just missed him