36

New useless information unlocked

Comments
  • 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 😛
Add Comment