magic_lobster_party @ magic_lobster_party @kbin.run

Posts

1

Comments

624

Joined

1 yr. ago

My implementation: https://pastebin.com/3PskMZqz

Results at bottom of file.

I’m taking into account that when I update a hash, all the hashes to the right of it should also be updated.

Number of hashes is about 2.71828 x n! as predicted. The time seems to be proportional to n! as well (n = 12 is about 12 times slower than n = 11, which in turn is about 11 times slower than n = 10).

Interestingly this program turned out to be a fun and inefficient way of calculating the digits of e.

One grain of rice in A1

Normie numbers (aka natural numbers)

Only thing I can find is that it has 128-bit graphics-oriented floating-point unit delivering 1.4 GFLOPS.

Probably only for marketing reasons. Everyone was desperate not to be worse than N64.

My interpretation is that Jon starts talking about how division by 0 is not possible. Garfield then goes on about how we can use limits to assign values to such expressions, which we can use to calculate derivatives. I guess Garfield starts to question whether dy/dx really exists after all this.

Jon then changes the subject to be about integrals, which Garfield is immediately annoyed about the missing +C.

It’s super funny.

It’s a poorly worded article. YouTube premium “limits ads” as in being completely ad free (besides in-video sponsorships). YouTube hasn’t gone down that route yet.

Does the meme making fun of all memes make fun of itself?

I don’t think it’s an unpopular opinion, but I’m not sure how YouTube can deal with it best. There’s sponsor block, but it’s relying on crowdsourced data.

Probably not in consumer grade products in any foreseeable future.

More complexity with barely any (practical) benefits for consumers.

Where are you getting that from? YouTube premium is ad free (so far).

Not true 128 bit. It has 128 bit SIMD capabilities, but that’s about it. Probably mostly because of marketing reasons to show how much better it is than N64 (which also is “64 bit” for marketing reasons).

In that case, we’re having 512 bit computers now: https://en.wikipedia.org/wiki/AVX-512

So in your code you do the following for each permutation:

for (int i = 0; i<n;i++) {

You’re iterating through the entire list for each permutation, which yields an O(n x n!) time complexity. My idea was an attempt to avoid that extra factor n.

I’m not sure how std implements permutations, but the way I want them is:

1 2 3 4 5

1 2 3 5 4

1 2 4 3 5

1 2 4 5 3

1 2 5 3 4

1 2 5 4 3

1 3 2 4 5

etc.

Note that the last 2 numbers change every iteration, third last number change every 2 iterations, fourth last iteration change every 2 x 3 iterations. The first number in this example change every 2 x 3 x 4 iterations.

This gives us an idea how often we need to calculate how often each hash need to be updated. We don’t need to calculate the hash for 1 2 3 between the first and second iteration for example.

The first hash will be updated 5 times. Second hash 5 x 4 times. Third 5 x 4 x 3 times. Fourth 5 x 4 x 3 x 2 times. Fifth 5 x 4 x 3 x 2 x 1 times.

So the time complexity should be the number of times we need to calculate the hash function, which is O(n + n (n - 1) + n (n - 1) (n - 2) + … + n!) = O(n!) times.

EDIT: on a second afterthought, I’m not sure this is a legal simplification. It might be the case that it’s actually O(n x n!), as there are n growing number of terms. But in that case shouldn’t all permutation algorithms be O(n x n!)?

EDIT 2: found this link https://stackoverflow.com/a/39126141

The time complexity can be simplified as O(2.71828 x n!), which makes it O(n!), so it’s a legal simplification! (Although I thought wrong, but I arrived to the correct conclusion)

END EDIT.

We do the same for the second list (for each permission), which makes it O(n!^2).

Finally we do the hamming distance, but this is done between constant length hashes, so it’s going to be constant time O(1) in this context.

Maybe I can try my own implementation once I have access to a proper computer.

Time complexity is mostly useful in theoretical computer science. In practice it’s rare you need to accurately estimate time complexity. If it’s fast, then it’s fast. If it’s slow, then you should try to make it faster. Often it’s not about optimizing the time complexity to make the code faster.

All you really need to know is:

• Array lookup: O(1)
• Single for loop: O(n)
• Double nested for loop: O(n^2)
• Triple nested for loop: O(n^3)
• Sorting: O(n log n)

There are exceptions, so don’t always follow these rules blindly.

It’s hard to just “accidentally” write code that’s O(n!), so don’t worry about it too much.

Good effort of actually implementing it. I was pretty confident my solution is correct, but I’m not as confident anymore. I will think about it for a bit more.

Frieza wants to know Earth’s location

By “certain distance function”, I mean a specific function that forces the problem to be O(n!^2).

But fear not! I have an idea of such function.

So the idea of such function is the hamming distance of a hash (like sha256). The hash is computed iterably by h[n] = hash(concat(h[n - 1], l[n])).

This ensures:

• We can save partial results of the hashing, so we don’t need to iterate through the entire lists for each permutation. Otherwise we would get another factor n in time complexity.
• The cost of computing the hamming distance is O(1).
• Order matters. We can’t cheat and come up with a way to exclude some permutations.

No idea of the practical use of such algorithm. Probably completely useless.

A new hope started with blood line. It was established out of the gate that Luke’s father was a Jedi knight and a good friend of Obi Wan.

Force Awakens and Last Jedi seemed to go in the direction that Rey and Snoke are unrelated to previous blood lines, but nope, it’s all Palpatine.

I don’t understand why a company like Sony wouldn’t provide you a way to play ps1-3 games on your ps5. I would even be ready to pay for it.

They want you to buy new games. Not to play your old games.

PS5 doesn’t support CD, so popping in PS1 games (and a few early PS2 games) won’t work even if PS5 had a proper PS1 emulator. It’s only a matter of time until DVD support will be dropped for future consoles as well.

Re-releasing old games digitally is also difficult. More from a legal aspect. They need the permission of the holder of the IP. If they want to release Crash Bandicoot again, they need permission from Microsoft, who’s the current IP holder.

It’s also extra problematic if the game uses licensed music, which became common in the PS1 era. Then they need permission from all the involved artists. The Tony Hawk games are problematic in this regard for example.

New releases of Sonic 3 doesn’t include some of the original tracks. Possibly due to the potential involvement of Michael Jackson.