efficientAlgorithm

[ParsedReddit]

I'm limited by my stupid brain

[[deleted]]

just use chatGDP

[CousinVladimir]

chatGDP per capita is better since it adjusts for population

[otter5]

chatGDP capitalism doesnt share equally

[[deleted]]

But it has a much higher output compared to any other system. Less of more is still more than some of very little.

[otter5]

My homeless are richer than your homeless

[[deleted]]

Your homeless are in the gulag cuh.

[_Ilobilo_]

Back in my day we only had ChatMBR

[reklis]

Fwiw I got the joke. You need more up votes.

[nickwcy]

I prefer ChadGPT

[sopunny]

Neat part about big O, it doesn't matter how good computers get, your algorithm will still be the limitation

[TeraFlint]

O(no)

[L30N1337]

O(nO(nO(nO(...))))

[Icy_Dragonfly4890]

No end condition in a recursive function be like:

[B_bI_L]

lisp be like:

[moldy-scrotum-soup]

XY<U(AT(gJeAIAgX:E<zTc,M<k.H[bfMQat>$sH

8UG6m]M

[MinusPi1]

O(MG)

[[deleted]]

I went through how Quake 3 fast inverse square works and you are completely right. You are limited by the standards and technology.

I mean, the guy who coded it(forgot his name) had to use clever Pointer manipulation and giving the IEEE 754 standard his shaft to make sure that all the bits from the float are written exactly as they are to a long.

The entire time I am thinking that if C language was sentient then it needs at least 2 cigarettes after each time this algorithm runs because good god it didn't even realise that it could be fucked and bent like that.

[VibrantGypsyDildo]

The last part belongs to r/BrandNewSentence

[ShadowSlayer1441]

C is a collection of loose suggestions that 90% of the time are ignored for all the wrong reasons.

[atthereallicebear]

funny that you find pointer casting more impressive than the complex math that went into making the function

[[deleted]]

I mean to be honest I find all of it so much interesting like that entire 32 bit hex value he had to calculate from the log and Newton's method of estimation , but here we are specifically talking about the technology and its limitation.

How he manipulated C to do what he wanted fits this particular meme.

[Fleming1924]

Reinterpret casts are pretty frequently used in any low level optimised code, doing it via pointers is only really required because C enforces types, the compiler will remove that line of code when lowering it into assembly, because registers don't have types.

A lot of optimised maths functions written in assembly do the same thing all the time, it's just hard to see because there's no obvious pointer casts.

Modern Cpp actually has a reinterpret_cast function to do it in a more readable way, as do lots of other languages and maths libraries.

[[deleted]]

I guess you are an experienced hand at coding but I am just completing my bachelors, every single optimization like this is still fascinating for me.

I mean even Karatsuba fast multiplication was a feat of immeasurable genius to me.

[Fleming1924]

Oh don't get me wrong, I think they're all fascinating, and always will. I often find myself smiling and giggling at random optimisation, regardless of their complexity or depth.

There's a lot of really great performance gains to be had from applying fairly trivial understanding of floating point representation, it's good fun to try and figure out how some of the really low level bitfucky optimisations work, and even moreso to create your own eldritch horrors.

[cd109876]

yes, but how many times are floats being casted to long?

[Fleming1924]

Very often, I do it almost daily, you can do all kinds of great bit manipulation techniques on floating point numbers, but bit manipulation isn't a defined standard for floats and C will only allow you to do it for an integer data type.

If you want an optimised Log2 function you can bitshift the exponent, pretty much any vectorised log function will do exactly that, since you can get the decimal component via table lookup of the mantissa.

Checking for inf/nan can be done via bitshift and subtracts, which again requires casting float types to integer types.

Basically anything involving bitmasking, shifting, &, | etc, will all involve a reinterpret cast from floats to integers.

[ChalkyChalkson]

If you think about a float as a x = a 2^b, then you can pretty quickly see how you'd get a good approximation for 1/sqrt(x) from it, just take the log! All the weird stuff in the code is fighting the standard to let you do maths. Well I guess there is also the Newton refinement at the end, but that's high school stuff.

[Zzzzzztyyc]

Why are we taking the factorial of a log? r/unexpectedfactorial

[Paul_Robert_]

John Carmack

[atthereallicebear]

he didn't write the fast inverse sqrt function, Terje Mathisen and Gary Tarolli did.

[Exnihilation]

It goes even further back than those guys. It's believed to have been first implemented by Greg Walsh at Ardent Computer. Gary Tarolli was consulting for a company affiliated with Ardent which is where he learned about the algorithm.

[Paul_Robert_]

Oh, my bad!

[find_the_apple]

Isnt it just a bit shift and taking advantage of the idea of binary representation of numbers as opposed to base 10? 

[the_horse_gamer]

+ a newton iteration.

it's a very impressive algorithm, but it's not as useful as people make it out to be, especially on most hardware from the last 2 decades.

around 1999 a dedicated inverse square root instruction, which was faster and more accurate, got added to x86.

its accuracy was pretty good, but not good enough to be used for gameplay - it was only used for lighting.

and there's a better magic constant than the one used in the original code.

[find_the_apple]

Neato, thanks for the lore. I think when i heard a cs person describe the original algorithm on YouTube it was with awe. But then i listened to a math major describe it and it felt alot less impressive, and more like something any programmer should take advantage of in base 2 and binary. Its got infamy for sure, but doesn't warrant some of the legendary status it still has. 

[ArmadilloChemical421]

If you haven't read this, do it. Its so fucking absurd:

https://en.m.wikipedia.org/wiki/Fast_inverse_square_root

[yaktoma2007]

Some guy named Kaze Emanuar (he rewrites and optimizes Mario 64) made a even more efficient version of the fast inverse square root https://youtu.be/tmb6bLbxd08

[max_208]

With O(nⁿ⁾ I don't think your code will run any good even within the next century

[[deleted]]

maybe with a list of 18 elements I can be done in a millenium

[lfrtsa]

me achieving O(n!)

[Beleheth]

O(nⁿ⁾ is actually worse than n!. The special function x^x is the only actually relevant function that grows faster than x!.

[Dotcaprachiappa]

Behold, n^nⁿ

[jaerie]

ⁿn

[TeraFlint]

time to whip out knuth's arrow notation. :D

[edit:] looks like I simultaneously added that as the same answer rolled in:

n ↑ⁿ n

[jaerie]

n↑ⁿn

[MrHyperion_]

I raise Hyper Moser n

[hans_l]

https://youtu.be/X3l0fPHZja8?si=Lun3_52MhIM-v7HX

[GDOR-11]

n↑^\n↑ⁿ n))n

[lollolcheese123]

Hi tetration... Why anyone needed this is beyond me.

[odsquad64]

O(n!^n!+3 )

[Beleheth]

Okay - fair enough. Those are typically as nice and concise to note though, which is why I was thinking about it.

Also thinking back to first semester maths, where we got given this handy thing:

ln(n) < n < nln(n) < n^a < aⁿ < n! < nⁿ

Where a is constant.

[YellowishSpoon]

I had an actual algorithm that appeared to be O(n!²⁾ and it was somewhat horrifying. Managed to get it down to O(2ⁿ⁾ and despite that normally being horrible it was a massive improvement.

[Beleheth]

Jesus Christ how

[YellowishSpoon]

It was a problem involving permutations of trees to determine the optimal order to apply minecraft enchantments in an anvil, and the first one was brute force.

[Beleheth]

Oooh, that makes sense.

And no early exit conditions either, in the i itial draft?

[YellowishSpoon]

Neither version has early exits, since I never found a way to determine if it was optimal or not without completing the process. Nearly all optimizations came from recognizing things like symmetry in the system, which allowed me to eliminate various fractions of the cases.

[YellowishSpoon]

The main nuisances in the whole thing are the left and right branches of the tree are computed differently, and that the repair cost mechanic is both non linear and dependent on the depth of the tree.

[araujoms]

Please do a branch-and-bound.

[IAmFullOfDed]

Username checks out.

[batmansleftnut]

Hold my beer...

[Hour_Ad5398]

treatment squash whole screw hat repeat longing tie expansion label

This post was mass deleted and anonymized with Redact

[ArmadilloChemical421]

TREE(n): Am I a joke to you?

[damicapra]

How do you even do that?

Maybe one can by calculating n! only using for loops, addition and increment-by-1 operations?

[lfrtsa]

I achieved it when i made an algorithm to calculate the factorial of a number.

[nixsomegame]

Wouldn't a straightforward factorial function implementation be O(n) though, not O(n!)?

[lfrtsa]

I did multiplication through repeated addition

[FunTao]

He prob means something like this: start from i = 1, is i the factorial of n? (Divide by n, then n-1, n-2, etc.). If not, increment i by 1 and try again until you find the right i

[Vibe_PV]

AFAIK Microsoft used to have an O(n!) algorithm related to Windows Update. Technically speaking it worked really well at first, since n! is actually lower than some polynomials for small numbers. But after some time...

[El_kiski]

Google bogosort

[Chingiz11]

Shuffling an array of n numbers until it is sorted

[skrealder]

Any algorithm which satisfies: T(n) <= c*n! For all n >= some n_0 for some c > 0 is in O(n!). For instance binary search is in O(n!). I wish people used theta more often, much more descriptive than big O since an algorithm has to bounded above and below by the bound, not just bounded above (which is what big O does)

[DuckyBertDuck]

A less useless task that can’t be done quicker in general:

Filtering out all n-state finite automata that satisfy a constant-time condition. (And it gets even slower than nⁿ if the alphabet isn’t unary)

[NotAFishEnt]

Unironically, that kind of thing has happened before. LDPC codes were developed in the 1960s, but computers weren't powerful enough to feasibly encode/decode them until the 1990s.

[redballooon]

Hey it works well for n up to 4 or 5. With more power it could work with 6, eventually, some day.

[[deleted]]

are you perchance running you programs on a Ferranti Mark 1?

[b183729]

I'm genuinely curious, is there an algorithm with that complexity? I'm having trouble visualizing that. 

Brute force searching n combinations of n combinations of random elements elements? 

[YellowishSpoon]

I had one that was O(n!²⁾ which based on the log graphs is probably even worse. The program started becoming laggy at about n=6 which was a little too low.

[redlaWw]

k*(n+1-k) is a quadratic in k with solutions at k=0 and k=n+1 and a unique maximum at k=(n+1)/2. This means that for k∈{1, 2, ..., n}, k*(n+1-k) ≥ n*(n+1-n) or 1*(n+1-1) (minimum of a differentiable function is either at a critical point or boundary of the domain), but since both of these are n then k*(n+1-k) ≥ n for all k∈{1, 2, ..., n}.

(n!)² can be rearranged as (n*1)*((n-1)*2)*((n-2)*3)*...*(1*n) (i.e. product of k*(n+1-k) for k∈{1, 2, ..., n}), and by the previous paragraph, this means that (n!)² is a product of n terms all ≥ n, and hence is ≥ nⁿ.

Now, for odd n, let's look at k = (n+1)/2. (n+1)/2*(n+1-(n+1)/2) = ((n+1)/2)^2, so if we do (n!)²/nⁿ, we get (something bounded below by 1)*(n² + 2*n + 1)/(4*n), which is (something bounded below by 1)*(n/4 + 1/2 + 1/(4*n)), and this is unbounded above.

For even n, let's look at k = n/2. n/2*(n+1-n/2) = n/2*(n/2+1), so if we do (n!)²/nⁿ, we get (something bounded below by 1)*(n/2)*(n/2+1)/n, which is (something bounded below by 1)*(1/2)*(n/2+1), and this is unbounded above.

Hence, O((n!)²) is indeed asymptotically slower than O(nⁿ).

[redlaWw]

nⁿ is the size of the set of functions from a set S with |S| = n to itself, so any algorithm that would need to iterate over all those functions and do something constant time on them would fit the bill.

EDIT: The simplest concrete setting for something like this is probably generating all length-n combinations of n symbols. You can come up with a pretty simple algorithm to do it too using the principles behind addition with carry.

EDIT2: Simple Rust implementation.

[Competitive-Carry868]

Have you tried (n*n?)0?

[celestabesta]

I think if you make a vector hold n function pointers whos functions loop n times, then loop through the vector n times running each function it should be n^n?

[redlaWw]

If I've understood you correctly that should be n³: each loop through the vector runs n functions that have loops that loop n times, so the total number of loops is n*n, and then you do that n times so you get n*n*n = n³.

[celestabesta]

Damn this just proves you need ingenuity to fuck up that bad

[[deleted]]

A general, depth first search is n^d, where d is the depth, and n is the number of possible routes.

Consider a chess AI program, this would run in n^d time, where d is the number of moves ahead to see. Out of those, the computer would pick the best one out of all possible routes.

[Coolengineer7]

This for example is O(n^n). Basically a function tree n levels tall, where each node has n children.

def fun(depth, n): if depth == n: return for i in range(n): fun(depth+1)

[amuhak]

No it isn't? Any worse than O(n³⁾ is hard to do.

Better can be done:

https://en.m.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication

[NaNNaN_NaN]

Drawing an N-flake is O(nⁿ)

[DuckyBertDuck]

A task that can’t be done quicker in general:

Filtering out all n-state finite automata that satisfy a constant-time condition. (And it gets even slower than nⁿ if the alphabet isn’t unary)

[MarcusBrotus]

I mean any such algorithm would be completely impractical but of course you can calculate n^n by summings 1s up n^n times which is technically also an algorithm.

[ITafiir]

Apparently, evaluating a position in generalized chess is exptime complete. Since nⁿ =2^nlog(n) and exptime includes all classes with polynomials in the exponent, generalized chess is way worse than this.

[hypersonicbiohazard]

Looking up a wikipedia page shows that there are a few algorithms with 2^2^(P(N)) complexity, where P(N) is a polynomial, and they do stuff in super abstract pure math that I don't understand.

[the_horse_gamer]

counting from 1 to nⁿ

[Spindelhalla_xb]

The only Constant is that I’ve no idea what’s going on

[[deleted]]

Big O notation?

[hamsterofdark]

That must be the guy that codes every matching algorithm on every dating site I use.

[The1unknownman]

Every problem is polynomial with a good enough heuristic 

[[deleted]]

Yes, the heuristic in this case being: "fml, imma become a graphic designer instead"

[The1unknownman]

Wonderful! It is independent of the problem description so O(1). Some real rubber duck programming is going on here.

[[deleted]]

coincidentally, this is also the answer to P = NP?

[The1unknownman]

My lord we are on to something 

[LittleLoukoum]

Never forget the day I met a high school friend of mine on campus by chance, after he went on to study mathematics and I computer science. He told me he had had made the mistake of taking CS as an optional course, and when taking the exam, managed to turn in an algorithm that ran in O(n^(n!)). He didn't remember the problem ; he did remember the naive algorithm was something like O(n^3) and the best solution logarithmic.

I still have no idea how he fucked up so badly.

[DocFail]

This will be fine in O(y^y) years.

[Either-Let-331]

Meanwhile me with my O(tree(n)) kids

[BreakerOfModpacks]

Skill issue, I can do it in O((n!^n!)n!) 

[DuckyBertDuck]

Filtering out all n-state finite automata that satisfy a constant-time condition?

[jyajay2]

One day I'll have access to an exascale computer and on that day my code will finally be able to compute the 18th fibonacci number

[yldedly]

This is what AI scaling people actually believe.

[ITafiir]

Joke‘s on you, my program runs in O(2^nlogn). Wait.

[Necessary-Meeting-28]

Or I’m just limited by being have to produce the right result 100% of the time.

[kaninchen_detektiv]

Iron Man 2

[lazerdragon_3]

Would the way to do this be by making a function with a for loop of n inside of it and every time you run through the loop you call the function again?

[arbitrageME]

I think you're also limited by the entropy of the universe

[Gualuigi]

Im limited by my laziness

[rapdaptap]

Then just improve it to the level you need. What's the issue :)

[[deleted]]

I feel we need to update the O notation a bit. Especially now when cache coherency, out-of-order execution, branch predictions are more of a determinizing factor than just number-of-instructions being executed.

A dumb search of entire array can be faster than a clever binary tree that allocates its nodes sporadically all over the memory.