The recently proposed o(n log n) integer multiplication algorithm [pdf]

https://web.maths.unsw.edu.au/~davidharvey/research/subnlogn.pdf

36•craigcitro•1h ago

Comments

flebron•57m ago

Note in this case the title says "O(n log n)", but the important part is this is "o(n log n)", not just "O(n log n)'. The former is a strict subset of the latter. We already knew how to multiply two n-bit integers in O(n log n) time, via the FFT.

onionisafruit•53m ago

For those of us uninformed, what’s the difference between O and o?

theokrueger•48m ago

Big O basically drops constants

O(2n+1) = O(2n) = O(n)

o(2n+1) > o(2n) > o(n)

Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____"

bobmarleybiceps•35m ago

that's not the convention I know... (from CLRS algorithms book).

Big O is sort of like <=. little o is sort of like <.

https://dl.acm.org/doi/10.1145/1008328.1008329

npinsker•27m ago

yes, GP is slightly off, but the idea of <= and < is accurate.

O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger".

o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.)

boothby•48m ago

If f is O(g) and o(h) then

  Lim f/g -> C a constant

And

  Lim f/h -> 0

appplication•44m ago

Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it.

If you were joking then maybe you got me

boothby•26m ago

I do hope you can find and reattach your ass; that does sound painful.

adgjlsfhk1•18m ago

> Lim f/g -> C a constant.

This isn't quite correct. O(g) doesn't require the limit to exist.

Ygg2•45m ago

Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound.

https://stackoverflow.com/questions/1364444/difference-betwe...

ruined•41m ago

f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant

f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink

jhanschoo•18m ago

Nitpick:

s/must shrink/must eventually shrink, after finitely many n/

Equivalently, must go to zero in the limit.

bobmarleybiceps•30m ago

Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329

craigcitro•49m ago

ty, fixed. (ahh, copy paste.)

ComplexSystems•35m ago

Roughly speaking, O(n log n) means "grows no faster than k(n log n) for some k", whereas o(n log n) means grows strictly more slowly* than k(n log n) for all* choices of k.

jdb1729•44m ago

> The new result does not directly imply new complexity bounds for polynomial multiplication over a fixed finite field, say multiplication in F2[x]. The state of the art for this problem is an algorithm that multiplies polynomials of degree n in time O(n log n 4^log*(n)) [HvdH19].

@platypii and I obtained a Lean proof of the same improvement for DFT over prime-order finite fields (yielding polynomial multiplication via the convolution theorem): https://github.com/platypii/integer-mult-bounds-lean/blob/ma...

ajkjk•30m ago

Really enjoy the writing style here.

yaoke259•17m ago

Awesome write up and intro by a fellow Sydney-sider, kept me hooked! As someone who's not a maths wizard, the technical details flew by my head but the prose allowing me to empathise deeply with those in the field was very enlightening. I never realised how big of a deal the maths dump was and how much it has shaken up the field. I guess we are all just trying to figure out this whole "intelligence on tap" thing together.

m00dy•7m ago

You don’t need to be a math wizard. Just upload the paper to an AI and ask, “Explain this like I’m five.” Then, with each follow-up prompt, increase the age and level of expertise you want it to assume.

Kapura•4m ago

> I have not actually read the paper. In fact, there are three closely related papers [TC26a], [TC26b], [TC26c], and I have not read any of them. I tried, but soon gave up. The math(s) dump does not appear to be strong on exposition. Instead, I asked Fable to explain [TC26a] to me. Fable seems to understand the argument and thinks that it is correct.

this does not feel like a healthy place to be

mitmproxy adds --emudhra option

The recently proposed o(n log n) integer multiplication algorithm [pdf]

Epic vs. Apple AU:Court Orders Alt App Stores,Sideloading and 3rd Party Payments

There isn't an easy exploit for this PHP vulnerability

Security Disclosure

Rust Style Guide

GitLab critical patch release

Compromised LiteLLM 1.107.0 on PyPI Installs a Credential Stealer and Backdoor

Using LLM for confidence scoring is a bad idea

Beyond the &

LLM Agents Play Pokemon Showdown

Chain of Thought for Humans

Meta ordered to pay $25B penalty in New Mexico Cambridge Analytica case

PingCap TiDB Leaks

Today's PHP security release, and how we're strengthening security

Tiny possum and glider thought extinct for 6000 years found in remote West Papua

Code is clay now

Show HN: Omnara – Open-source alternative to Claude Managed Agents

OpenAI models are coming to Google Cloud

No more icons in every menu by default

DuckDB 2.0.0 LTS “Cinnamon Teal”

Why Windows 11 still ships with Windows 95's memory manager hidden inside it

Patch the Planet: global response coordination as agents uncover vulnerabilities

Postgres recovery_prefetch can cause outages

I reverse engineered a board game

Show HN: AI-built browser games, collected in one place

Oregon lawmakers approve money to buy an iconic waterfall listed on Redfin

EA is shutting down BioWare

Show HN: Can you tell an AI's real 30-day memory from a fabricated one?

Launch HN: Alter (YC S25) – Access control for multi-user agents

mitmproxy adds --emudhra option

The recently proposed o(n log n) integer multiplication algorithm [pdf]

Epic vs. Apple AU:Court Orders Alt App Stores,Sideloading and 3rd Party Payments

There isn't an easy exploit for this PHP vulnerability

Security Disclosure

Rust Style Guide

GitLab critical patch release

Compromised LiteLLM 1.107.0 on PyPI Installs a Credential Stealer and Backdoor

Using LLM for confidence scoring is a bad idea

Beyond the &

LLM Agents Play Pokemon Showdown

Chain of Thought for Humans

Meta ordered to pay $25B penalty in New Mexico Cambridge Analytica case

PingCap TiDB Leaks

Today's PHP security release, and how we're strengthening security

Tiny possum and glider thought extinct for 6000 years found in remote West Papua

Code is clay now

Show HN: Omnara – Open-source alternative to Claude Managed Agents

OpenAI models are coming to Google Cloud

No more icons in every menu by default

DuckDB 2.0.0 LTS “Cinnamon Teal”

Why Windows 11 still ships with Windows 95's memory manager hidden inside it

Patch the Planet: global response coordination as agents uncover vulnerabilities

Postgres recovery_prefetch can cause outages

I reverse engineered a board game

Show HN: AI-built browser games, collected in one place

Oregon lawmakers approve money to buy an iconic waterfall listed on Redfin

EA is shutting down BioWare

Show HN: Can you tell an AI's real 30-day memory from a fabricated one?

Launch HN: Alter (YC S25) – Access control for multi-user agents

The recently proposed o(n log n) integer multiplication algorithm [pdf]

Comments