36

# New useless information unlocked

• 5
Truly useless info. I'm impressed.
• 8
@mcalis Galactic info.
• 8
@mcalis I think the described algorithms are extremely interesting though.

Like, something simple like multiplication of integers...

If you multiply 234 x 589, it obviously takes 3x3=9 steps.

The time complexity for multiplication scales exponentially with the amount of digits, it is O(n^2).

But there are methods to do multiplication *faster*, using fast Fourier transforms. Even for "small" big numbers, there are noticeable advantages, which are used widely by in-production software:

https://en.wikipedia.org/wiki/...

The conjecture was that no algorithm could beat O(n^2). Then the conjecture was that it can approach O(n log n) for very large numbers, which has since been proven for numbers above (2^1729)^12 digits ("galactically large").

What hasn't been proven however, is whether further optimizations to multiplications are (im)possible for smaller numbers.

I find those kinds of "we don't know... yet" cases very interesting.
• 0
@bittersweet When your problem size is limited, any algorithm runs in O(1) anyway ðŸ˜›