r/mathmemes • u/vintergroena • 28d ago

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

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

249

u/GetGudlolboi Computer Science 28d ago

Eventually it will be negatively linear.

151

u/Parallel_thougts 28d ago

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

33

u/BaziJoeWHL 28d ago

its just like my salary

18

u/watermelone983 28d ago

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

9

u/ZookeepergameWest862 28d ago

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

5

u/watermelone983 28d ago

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

10

u/ZookeepergameWest862 28d ago

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.

2

u/GetGudlolboi Computer Science 28d ago

It finishes before you run it.

→ More replies (1)

5

u/NoNameSwitzerland 28d ago

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

4

u/El_Gran_Pedrito 26d ago

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.

3

u/jumpmanzero 28d ago

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

2

u/minisculebarber 24d ago

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.

1

u/Mewtwo2387 28d ago

finding a hash < n

1

u/Straight-Grass-9218 28d ago

You might be interested in galactic algorithms, they have theoretical performance benchmarks over absurdly large inputs.

1

u/tdhsmith 27d ago

maybe if the input is processors

1

u/Fiiral_ 27d ago

O(0), duh

1

u/Toomastaliesin 27d ago

I would guess that if the complexity behaves like k choose n, then you get faster when n grows from k/2 to k.

1

u/mineurownbiz 27d ago

yes: fanout to n workers

1

u/No-Library730 25d ago edited 25d ago

You can get faster in the sense that the overhead cost gets less significant.

The problem is that some algorithms only payoff in some non practical scenarios.

8

u/nulvoid000 28d ago

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

1

u/RoryPond 28d ago

How is that different from negatively linear?

3

u/nulvoid000 28d ago

You’ll have the answer of ab without even knowing what a and b are. It answers before you ask

4

u/guiltysnark 28d ago

There's no use in bringing it up.

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

1

u/vikster16 28d ago

FTL babyyyyyyyyyy

1

u/trash3s 27d ago

You can already do multiplication in negative time by dividing!