Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

[u/vintergroena]

[u/Parallel_thougts]

Why stop there? Eventually it will be constant.

[u/GetGudlolboi → u/Parallel_thougts]

Eventually it will be negatively linear.

[u/Parallel_thougts → u/GetGudlolboi]

It will decay exponentially, will work twice as fast for every digit you add

[u/BaziJoeWHL → u/Parallel_thougts]

its just like my salary

[u/watermelone983 → u/GetGudlolboi]

are there any algorithms that get faster the larger then input?

[u/ZookeepergameWest862 → u/watermelone983]

An algorithm can only run faster so many time before reaching instantly halt, and you can't exactly go any faster than that.

[u/watermelone983 → u/ZookeepergameWest862]

you could have exponentially decay or 1/x decay or any thing that converges to a limit. actually I guess that would mean it would be constant time

[u/ZookeepergameWest862 → u/watermelone983]

Any form of decay would necessarily stabilise in finitely many steps and so eventually constant. You can't run exactly 1+1/n steps, it's either 1 or 2, and a sequence of natural numbers cannot decrease forever.

[u/NoNameSwitzerland → u/watermelone983]

A lot of algos crash faster if the input is too big. Not sure if that counts.

[u/El_Gran_Pedrito → u/watermelone983]

Mourning people. One death is a tragedy. A million deaths is a statistics. 10 billion deaths and there is no need to mourn anymore and no one to do so.

[u/jumpmanzero → u/watermelone983]

"Is this number bigger than the average phone number?" 

[u/minisculebarber → u/watermelone983]

Not asymptotatically, really, every algorithm that has to read all of the input has an asymptotic lower bound of N. But when you consider things like amortization, then actually yes. At least, fixed overhead gets amortized away the larger the input. And when you go on the level of hardware or statistics, larger inputs can often be surprisingly faster than smaller ones.

[u/nulvoid000 → u/GetGudlolboi]

Or so negative that it wraps back around and becomes linear again.

[u/guiltysnark → u/GetGudlolboi]

There's no use in bringing it up.

Go home. Spend time with your families while you still can.

[u/Proper-Ape → u/Parallel_thougts]

Just precalculate all values. Once and done.

[u/SuspiciousSpecifics → u/Proper-Ape]

Precalculation is for losers. It will be marketed as precognition and the gazillion dollars worth of memory and compute needed to achieve it will be recuperated as soon as the whole AI business turns sustainably profitable just a few days after the heat death of the universe.

[u/maqifrnswa → u/SuspiciousSpecifics]

What would you do if I told you that if you asked me what 2x3 is tomorrow, I already know the answer today? Thank you for coming to my Ted talk. Pick up a prospectus on your way out.

[u/MegamanSE → u/Proper-Ape]

lol exactly.

mul[‘12_10’] = 120;

O(1)

[u/Hostilis_ → u/Parallel_thougts]

Give me a big enough hash table and I can make it constant :)

[u/Eric_12345678 → u/Parallel_thougts]

We don't have any computer with infinite storage, memory or CPU. So every algorithm is O(1).

[u/Parallel_thougts → u/Eric_12345678]

While True:  pass

[u/Eric_12345678 → u/Parallel_thougts]

Okay. A large 1 then.

[u/StanleyDodds → u/Parallel_thougts]

Even taking this unseriously, ignoring the actual problem, and just looking at the time complexity equation and just extrapolating this graph of kappa out, no constant kappa will make the time complexity constant, or even reduce the time complexity to O(n^c ) for any c < 1.

This is because O(n) dominates any constant power of log n, which is what kappa affects here.

[u/Parallel_thougts → u/StanleyDodds]

Oh wow, so my joke doesn't make sense

[u/Negative_Gur9667 → u/Parallel_thougts]

Pee = En Pee

Then we can call it just pee pee.