Hacker News Reader

Comment by w8rbt | Hacker News Reader

O(n^2) is polynomial and perfectly acceptable for many use cases. Basic multiplication is O(n^2), as are many other operations.

    for i = 1 -> n:
        for j = 1 -> n:
            do something

Although, if the outside n differs in size from the inside n, it should be written O(nm).

View on HN

I would argue that O(n^2) algorithms are really only acceptable if n is known to be bounded well ahead of time. In large integer libraries like GMP, O(n^2) multiplication is switched out for asymptotically better and better algorithms as n gets too large: https://gmplib.org/manual/Multiplication-Algorithms.html

In this case it doesn't seem to be. Although admittedly executables as large as in the article are rare, process creation on Windows is slow enough as it is, without extra inefficiencies.

As an aside, basic multiplication is O(n^2) only if your number type is arbitrarily wide. Standard 32-bit or 64-bit multiplication as implemented in hardware is constant time.

Right, it's a pity RSA does not use 32 or 64 bit ints.

What does that have to do with anything? The original thread was about performance guarantees of API functions.

It's tautological to state that for a fixed number of nodes, mutliplication is constant time.

Off course it is. The n is fixed.

Also as a side note, n^2 is not the lowest order algorithm for multiplication.

No, what is meant by that, is that multiplying 2 by 3 takes about the same time as multiplying 432434232 by 1213213213. Not only bounded time, about the same.

What's the runtime of 75^4096 mod 236?

That sounds like a problem that is not described by "Standard 32-bit or 64-bit multiplication as implemented in hardware".

a^n mod m requires O(log(n)) iterations in the outer loop. If m fits in one machine word, each iteration is O(1). If m is large, each iteration is O((log m)^2).

For the specific case of m = 236 and n = 4096, it requires 12 multiplication and 12 division operations. For n = 4095, I think it actually requires 22 multiplications and 22 divisions. Also, if m is a compile time constant, the divisions can be implemented as multiplications instead, which gives a constant factor speedup.

https://godbolt.org/z/KNX4pi

https://en.wikipedia.org/wiki/Modular_exponentiation#Right-t...

O(1) - constant time. The answer is 29. I just happen to know that.

I think you need an 'n' in there before it is meaningful to ask about the runtime.

Reply on news.ycombinator.com