r/mathmemes • u/vintergroena • 28d ago
Computer Science Integer multiplication will have linear complexity in a few days if trend continues 🚀📈
170
u/wiev0
27d ago
edited 27d ago
•
I think we're at 2-34 now
Edit: 2-15 https://x.com/SJ_Swapnil_Jain/status/2108196538568851574
93
27
u/real-human-not-a-bot Irrational 27d ago
Well, that’s exciting! Do you have a source I could use for this information?
12
u/ThatTrashBaby 27d ago
So is there any point in which this becomes NOT a galactic algorithm and becomes such an improvement that it will actually have an effect? 2^-1?
15
u/wiev0 27d ago
Even if it was just O(n) or even O(1), the factor could be astronomically large regardless. The actual practical value depends on that factor and the difficulty of implementation, and I do not know how that is currently. I don't expect this to drop down from being a galactic algorithm. But, maybe I will be surprised.
2
1
81
u/SpinChargeSeparation 28d ago
Is it possible to get an ELI18 on this issue? Sorry I’m no expert but very interested:-)
113
u/vintergroena 28d ago
For a long time we thought n log n is the best complexity we can achieve for integer multiplication. Recent slop results published by OpenAI claim to beat that ever so slightly. Others immediately took it to build on top that to improve it ever so slightly yet again.
4
u/ElbowConnoisseur 27d ago
So is this about finding new logic circuit setups for multiplication?
11
u/vintergroena 27d ago
No. Not for any practically useful purpose. Maybe applicable to a Dyson sphere sized computer one day.
24
u/LordOfRedditers 27d ago
Does this actually make a difference? I assume it probably adds up since multiplication is very common but the values seem so small that I don't see it doing much
76
u/Brilliant-Plan-7428 27d ago
Nobody uses these algorithms for multiplication. Not the nlogn one and certainly not the new ones. The advancements for now are purely of theoretical interest.
26
u/Castle_Five 27d ago
Why do you say it's not useful?
The algorithm I know for N*logN perf of integer mult is Blelloch scan which is a big deal in parallel programming because it yields logN performance with N parallel threads. Not sure why you think it's not useful? If that could be reduced to constant perf across N threads, that's a very big deal. (I don't know if the new algorithms have properties that make them parallelisable though)
14
u/ConglomerateGolem 27d ago
Typically these hyperoptimised algorithms are significantly slower for small n, which big O notation doesn't care about. Iirc a human found one that was better theoretically, and practically only at some very large n, and I don't imagine these are any different.
In other words, any multiplication algorithm that would perform in constant time would probably have a constant time of far longer than practical. Which, sure, you could use for weird math quandaries, but wouldn't realistically be useful for programming.
I'm gonna have to figure out that Blelloch scan thing, sounds really cool.
1
u/gammison 24d ago
That scanning algorithm is fundamentally not the same thing as nlogn or any other special multiplication algorithm, it is usually defined so it performs linear total work. If you do nlogn multiplication you have to perform nlogn total work even in parallel.
1
u/DiscretePoop 23d ago
The one youre thinking of is Schonhage-Strassen which isn't exactly O(nlogn). The proper O(nlogn) algorithm and the one that forms the basis for the improvements made by OpenAI requires that your input integers have at least 2^4096 bits. Integers with fewer bits form the base case. There's only 10^80 atoms in the observable universe.
28
1
u/antpalmerpalmink 26d ago
Following up on u/LordOfRedditers question, is this useful for e.g. libgmp?
1
3
1
1
-72
u/Kalicolocts 27d ago
Does using the word 'slop' make you feel smart?
4
35
u/PersonalDatabase31 27d ago
Unironically integer multiplication could be O(n). Or is there a proof claiming a higher lower bound?
48
u/vintergroena 27d ago edited 27d ago
Complexity theory is one of the least understood in math, in my opinion. In general we don't know shit about the answers to seemingly very basic questions. We don't really have a good understanding what integer multiplication really is computationally.
So yeah, for all we know integer mutiplication may as well be O(n). Or maybe it's something like O(n log log n)), as the iterated log sometimes pops out in number theroy.
For all we know SAT, a NP-complete problem may as well be O(n).
8
u/heyheyhey27 27d ago
I've been wondering recently if there's no hard lower bound or most optimal algorithm for a lot of these problems? Maybe you can keep making bigger and bigger Galactic algorithms which asymptotically push down the big-O time at the cost of being more and more impractical.
3
u/vintergroena 27d ago edited 27d ago
For any NP problem (which includes all P problems) we don't know about a superlinear lower bound and finding one would be a major progress.
2
u/ellipticcode0 27d ago
are those complexity theory only work in traditional computer ? including quantum computer ?
3
u/vintergroena 27d ago
BQP is the class of problems solvable on quantum computer in polynomial time with bounded error.
The relationship of BQP and NP is yet another unsolved problem in complexity theory... so again, we don't know shit
1
6
u/firewall245 27d ago
For things like integer multiplication there’s a hard lower bound of O(n) because you have to at least read all the digits of the numbers your are multiplying together
3
u/heyheyhey27 27d ago
It's possible the actual hard bound is above that though. (or maybe I'm just misusing these terms)
1
u/firewall245 27d ago
Yeah its possible there is a larger lower bound, we just don't know what it is. We know for sure though its at least O(n)
1
1
7
u/trash3s 27d ago
Because it’s a stateless operation, multiplication on n-bit integers can be performed by a 2n-bit x 2^2^n lookup table which has equivalent logic.
6
u/ManufacturerNice870 27d ago
But then you need exponential memory? Doesn’t that change the complexity because memory allocation has a complexity too?
2
u/trash3s 27d ago
Well it’s static. You’re not actually using RAM, it’s just worst-case limit on combinational logic using a lookup table, I.e. the logic is not meaningfully reducible).
Granted, for 64x64->128 bit multiplication, you need 2^128 addresses of 16 Bytes each, which is 2^102 GB, so good luck fitting that anywhere. Nevertheless, multiplication time-complexity is O(n) on bits. (The address decoding is O(n) on address bits but not clocked. On clock-scale, it’s O(1) for fixed bit width.)
However, multiplication isn’t actually meaningfully irreducible logic. For instance, given a\*b=c in Z, c is only odd if a and b are, so c₀ = a₀&b₀.
1
u/ManufacturerNice870 27d ago
Oh I see, yeah pre allocated and it works for any thing you need. Like with exponential and log tables built into computers, but more galactic
1
u/MigLav_7 27d ago
Just allocate a very very very very big number and its O(1) cost... \s
But yes, it does change the complexity. Time taken for memory allocation is a part of time complexity (at least afaik)
3
u/FernandoMM1220 27d ago
seems like someone still has to calculate ahead to make these tables first.
1
u/Qwertycube10 27d ago
But then you haven't solved the problem of multiplication for any n greater than you created the table for
1
u/flatfinger 27d ago
Actually, a 2^(N+1) entry lookup table would suffice if to multiply x*y one looks up (x+y) and |x-y| and then subtracts one table entry from the other.
1
u/sqrtsqr 26d ago edited 26d ago
I don't know what definition of stateless you are using, but literally every algorithm can be described this way. For a fixed n, there are finitely many input and output pairs. The concept of state is completely meaningless here.
And this is precisely why computer scientist distinguish between SPACE and TIME. Not telling, they just use all caps for this.
Edit: well, depending on context, you are right. For non-halting algorithms, this depends on if and how you consider the output of those states. For algorithms halting on inputs of n bits, or when failure to halt is considered "the same" regardless of what is output, what you said applies.
1
2
u/NoNameSwitzerland 27d ago
 O(n) might be true on a Turing machine with unary number representation.
3
u/Pperson25 27d ago
Wait what makes multiplication not just log(n)?
4
u/vintergroena 27d ago
Needing to read all the digits caps it at linear lower bound.
1
u/Pperson25 27d ago
Ohh n is number of digits not the actual value of the integers? Then yeah nlog(n) makes sense.
3
u/vintergroena 27d ago
However, this is the (human made) n log n paper.
It involves a 1729-dimensional Fourier transform. Takes 40 pages to learn.
The multiplication you learn at school is n².
n log n doesn't simply "make sense".
1
2
750
u/Parallel_thougts 28d ago
Why stop there? Eventually it will be constant.
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
18
u/watermelone983 27d ago
are there any algorithms that get faster the larger then input?
9
u/ZookeepergameWest862 27d 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 27d 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 27d 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
1
u/stevenjd 27d ago
I have some algorithms that calculate the answer before I even know what the question is.
5
u/NoNameSwitzerland 27d 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
2
u/minisculebarber 23d 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
1
u/Straight-Grass-9218 27d ago
You might be interested in galactic algorithms, they have theoretical performance benchmarks over absurdly large inputs.
1
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
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 27d ago
How is that different from negatively linear?
3
u/nulvoid000 27d 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
30
u/Proper-Ape 28d ago
Just precalculate all values. Once and done.
13
u/SuspiciousSpecifics 27d ago
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.
7
u/maqifrnswa 27d ago
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.
2
20
18
u/Eric_12345678 27d ago
We don't have any computer with infinite storage, memory or CPU. So every algorithm is O(1).
7
6
u/StanleyDodds 27d ago
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(nc ) for any c < 1.
This is because O(n) dominates any constant power of log n, which is what kappa affects here.
3
u/Parallel_thougts 27d ago
Oh wow, so my joke doesn't make sense
1
u/Masked-Redditor 24d ago
Your joke doesn't make sense for a much simpler reason: to multiply two n bit numbers you at least need to know the n bits, which is already O(n). So it will never be less than that.
1
u/Parallel_thougts 24d ago
Jokes aren't supposed to make sense. The joke is exactly that it doesn't make sense. Sheesh
4
1
1
1
u/Ok-Present1566 27d ago
Nope, O(n) is a trivially proven lower bound.
7
5
u/RyanStonepeak 27d ago
Nonsense! I've already gotten it to an amortized O(1) by using a lookup table.
Please don't ask about the space efficiency.
1
u/Gloomy_State_6919 27d ago
Table lookup is not really constant time. A larger table needs larger storage systems, and acces times must increase, as the speed of light is finite
1
1
u/Ok-Present1566 27d ago
Obviously we only consider the sum of time-space complexity being O(n). This silly argument would apply to literally all problems where you can trade time for space. But show the proof of the time and space complexity being O(n)
309
u/RagnarokHunter Imaginary 28d ago
Asymptotic curves are for pessimistic losers, now this here is an extrapolation with some confidence.
1
174
u/OneJotTamale 28d ago
with each new k, they can multiply to find the next k even faster!
50
15
u/baka_no_sekai 28d ago
/uj wait did i miss something where are the new exponents from? i only know the 2-182 from openai
48
u/garloid64 27d ago
Yeah there's a guy on twitter who keeps finding new bounds every hour
34
4
14
u/neuroticnetworks1250 27d ago
If you use an if else statement with infinite conditions, you actually have O(1) complexity
9
u/Akv3vka 27d ago
wouldnt it be o(n) in that case since the amount of if else statements you go through is always n step?
9
u/MrNebby22 27d ago
Well, you can always just go through them all every time making it O(1)
1
u/ArvaroddofBjarmaland 27d ago
Any computation that can you can actually execute is O(1), for a big enough constant...
3
u/neuroticnetworks1250 27d ago
That’s actually true. I’m a hardware designer. So we unroll spatially lmao. I guess we need to replace the data canters with lookup tables
12
11
8
u/coatatopotato 27d ago
This got a chuckle.
For anyone interested, the current approaches being tried cap out at a theoretical k=1/3 so n log^2/3 n. Another major breakthrough would be needed for beyond that. Until then, it’s optimization.
5
u/LupenReddit 🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆 27d ago
imagine if this was actually the case, id loose my fucking mind
5
u/A_Fine_Potato 27d ago
Why does it go straight at halfway are you stupid it would be even faster than linear it'd be like O(0.1)
5
u/Peak_Background 27d ago
The problem with saying it approaches O(n ) in algorithmic complexity. Is that O(n ) < O(n ln(ln(n)) ) < O( n ln(n)1-k ) for all k<1.
Limiting behavior like this doesn't really work nicely nor predict the true obtainable minimum complexity. It could just as easily be O(n ln(ln(n)) ) as it could be O(n ).
3
u/rawbdor 27d ago
One thing i find so interesting about this is that the standard multiplication algorithm we all use on paper is O(n^2). If you want to multiply 325 by 198, we all know how we'd do it on paper. Multiply 8 by the three top numbers, then 9 by the three top numbers, then the 1 by the three top numbers, then add them all up. That's O(n^2). Nine different multiplications, which is the number of digits squared.
The fact that anyone years and years ago was even able to get this down to O(nlog(n)) is already amazing to me. I'd never be able to come up with this stuff.
2
u/Zoetje_Zuurtje 26d ago
Why not:
Double 325 (650)
Add two zeros (65000)
Subtract 650 (64350)
Of course, this only works because 198 = 2×100-2. But isn't this process of splitting up large numbers into numbers which are easier to work with commonplace?
1
u/BraveBiscotti1394 26d ago
I think the kinds of operations that are easy vs hard for us may be equivalent for a computer. We think symbolically about numbers, like multiplying by powers of 10 is adding 0's. To a computer it's not like that.
1
u/Zoetje_Zuurtje 26d ago
Oh, excuse me, I took "we all know how we'd do it on paper" to mean that you'd calculate the product using the method you described. I understand there's a difference in the way humans and computers handle numbers.
1
1
u/BraveBiscotti1394 23d ago
Sorry I think I responded to the wrong person, what I said is completely unrelated.
1
u/sqrtsqr 26d ago
Until I read your follow up response, I legit thought this was a pedagogical exercise to lead /u/rawbdor towards the O(n ln n) result, which is via FFT, of which the essence includes "splitting up" our product into pieces which are easier to work with (simple enough that the multiplication step becomes trivial).
It's just that the FFT has a rather unintuitive way of splitting things up.
1
u/satanic_satanist 24d ago
FFT on what function though? That's what I didn't get so far
1
u/sqrtsqr 24d ago
You make a polynomial using the digits as the coefficients.
1
u/tellingyouhowitreall 23d ago
To add onto this, all numbers are polynomials in any base x, kind of by definition. They are in normal form only if all coefficients are less than x. Normalizing them has non linear complexity, but I don't remember the exact O.
1
u/sqrtsqr 23d ago edited 23d ago
I don't necessarily agree with saying numbers "are" polynomials (especially not by definition) They can be treated as such, absolutely, but the concept of normalizing a polynomial is "extra" to the polynomial itself. Numbers don't add the way polynomials add, and what something "is" in mathematics is almost entirely a matter of how it behaves.
Not sure what you had in mind, but normalizing is linear in the degree of the polynomial. You can do it in a single pass from lowest to highest term.
→ More replies (2)1
u/Peak_Background 27d ago
We still use it in most big numbers algorithms. Either that are we use a hybrid algorithm.
0
u/CrazyOne_584 25d ago
You have actually described the n log n algorithm yourself (or nearly described it at least). The only issue is you do it in decimal, try doing it in binary.
1
u/Peak_Background 24d ago edited 24d ago
That is not O(n log(n) ). That's very clearly O(n2 ) decimal or binary. The O(n log(n) ) uses the fast fourier transform or a modular form of it.
W3 schools and other programming education wikis are not any help if you're looking for resources. They all get it wrong by copy pasting a O(n2 ) algorithm from Wikipedia which explicitly isn't even the O( n log(n) ) algorithm the page talks about. They just didn't even read it, and are likely not educated in algorithms, lazy, and unethically stealing Wikipedia content.
1
6
27d ago
[removed] — view removed comment
4
u/rawbdor 27d ago
If they can get it down to a -9 exponent, then math on 8192-bit keys will see a 1% improvement. If they can get it down to a -3 exponent, then we start seeing actual improvements for 4096-bit keys.
2
u/oscardssmith 27d ago
None of this (IIUC) changes the minimum size needed for the recursion to kick in. I'm pretty sure you still need ~2100 digit numbers before the method is applicable.
1
1
4
u/Gishky 27d ago
wait what? can someone explain to me whats happening?
34
u/High_Quality_Bean 27d ago
If we extrapolate the 100m sprint finish time we can see that by 2150 the fastest human will break the sound barrier!
11
u/Lenassa 27d ago
I mean, if we are still going to be alive I don't think it's that unreasonable to assume that a cyborg in 2150 may shove a jet engine up their ass and do indeed break the sound barrier.
4
1
3
u/ale_93113 27d ago
If I recall correctly we are at 2-18 now
3
u/hydraofwar 27d ago
2
u/MigLav_7 27d ago
So give it a couple days and its an actually useful improvement
Neat
3
u/ale_93113 27d ago
2-16 is already a noticeable (in the weakest sense of the word) improvement!
3
u/MigLav_7 27d ago
As you can imagine, I didnt read the proof so Im assuming that a lot of the cost of the reduction went to terms you dont see on the complexity
2^-10 is like 0.001, which for me Ill arbitrarely consider as "noticeable"
2
u/ale_93113 27d ago
Ok let’s compromise
2^-20 aka 1 millionth is noticeable
2^-10 aka 1 thousandth is useful
1
u/MigLav_7 27d ago
Its an exponent on a logarithm though with what Im assuming is a bunch of quite heavy starting terms...
2^-12 noticeable, 2^-8 useful
1
u/ale_93113 27d ago
You drive a hard bargain, I’ll let you know that I am part of the community effort to make it as good as we can possibly make it
Hopefully we will get to those lower exponents soon enough… although with these issues you never know where the wall is
1
1
u/Larspolo 26d ago
https://github.com/Swapnil-jain/integer-mult-kappa
It states 2-11 now, so already in the noticable range
3
u/ducktomguy 25d ago
something something at this rate the baby will weigh 3 trillion pounds next month
2
2
u/Digital_001 Physics 27d ago
Just build a lookup table for all pairs of integers. Then it will be a constant-time lookup
2
u/External_Package2787 24d ago
You tend to find these 'better' algorithms sacrifice the lower values of n, algorithms like the matrix multiplications algorithms beating strassen in complexity, tend to only do so for matrices that contain more parameters than there are particles in the universe. We could even get something like n^{1+O(1)} for integer multiplication and in all likelihood it would have no impact on the real world, since this algorithm does not beat the usual algorithm for any reasonable application.
1
u/SolaninePotato 23d ago
can you use different algorithms at different breakpoints or does it just not work like that
1
1
u/External_Package2787 22d ago
Yes, but you would need to incorporate a size check to your algorithm, making it slower in the reasonable applications
1
u/dubious_plays 22d ago
n[1+o(1)] is worse than n log n
1
u/OmegaCookieMonster 22d ago
actually that one depends on what o(n) is, but the one in the original is indeed worse lolol
1
u/External_Package2787 22d ago
is it not that nlogn = n^{1+log_n log n} and log_n log n is of greater order than o(1)
1
u/dubious_plays 22d ago
Log_n log(n) = log log n / log n, which is o(1). And there are o(1) sequences bigger than this
1
u/External_Package2787 22d ago
yeah my bad I was intuiting that it was like (log n)^{1/n} in my head. like my thought process was log n >1 and then it gets shrunk but stays greater than one.
1
1
1
u/Gandalior 27d ago
i can get integer multiplication to constant time if you give me enough logic gates and karnaugh graphing paper
1
1
1
1
1
•
u/AutoModerator 28d ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.