4 ms·

There are related problems in computer science -- e.g. how quickly can you multiply a pair of 65536x65536 extended double precision matrices together. Note that

by pjsg 6y ago

There are related problems in computer science -- e.g. how quickly can you multiply a pair of 65536x65536 extended double precision matrices together. Note that each matrix consume ~68GB of memory, so you need (probably) at least 200GB to store the two input matrices and the output matrix. So far, so good. Now you want to see how fast it can really go if you are prepared to spend (say) $100k on the hardware (e.g. 64 times as many CPUs with some fancy interconnect fabric). How about spending $100M? It turns out that moving all this data around is also quite costly.....

goldenkey 6y ago
That's not a problem in C.S. That's a problem in engineering.
- BobbyJo 6y ago
  Until hardware can do everything free and instantly, making computations cheaper and faster will be a core problem in CS. Everyone enjoys when the hardware gives free gains though :)
  - goldenkey 6y ago
    C.S is not concerned with the fastest speed that off the shelf hardware can multiply two matrixes measured in seconds. You must be thinking of Linus Tech Tips.
    - BobbyJo 6y ago
      It is concerned with the lowest complexity method of doing so, which is directly related.
      - goldenkey 6y ago
        Tangentially, not directly. Algorithms become different beasts when implemented on real-world hardware.
        BobbyJo 6y ago
        I said they are directly related, not that they are equivalent. The entire reason programmers have the notion of time complexity is to understand how algorithm's execution scales. The reason we drop constants and constant scale factors is because they typically don't make a big difference in real world execution times. That's a little more than tangentially related. Saying time complexity has nothing to do with hardware is like saying speed limits have nothing to do with cars. Hardware constraints are the entire reason we developed the notion of time complexity. I'm honestly very confused as to how someone (I assume is) engaged in programming could think the relationship is tangential.
        goldenkey 6y ago
        You are arguing a different point, C.S. is not concerned with measuring performance in seconds. Do you agree or disagree? Now that we are on the same page, of course the asymptotic complexity of a method matters, but some of the lowest complexity methods actually have huge constants and cannot be used until you get to scales that dwarf most usages. This means that the connection is tangential. The current method of matrix multiply used in all your software is NOT the lowest asymptotic complexity method. Look it up.
- afiori 6y ago
  parallelism and data locality are also cs topics
Zenst 6y ago
>65536x65536 extended double precision matrices together For perspective, that would be akin to multiplying every MAC address with every other MAC address upon the entire IPv4 range.
- nayuki 6y ago
  MAC addresses are 48 bits and unrelated to IPv4. Multiplying two 65536×65536 matrices naively in O(n^3) time would be about the same number of operations as processing each possible MAC address.

by pjsg 6y ago

goldenkey 6y ago

That's not a problem in C.S. That's a problem in engineering.

BobbyJo 6y ago
Until hardware can do everything free and instantly, making computations cheaper and faster will be a core problem in CS. Everyone enjoys when the hardware gives free gains though :)
- goldenkey 6y ago
  C.S is not concerned with the fastest speed that off the shelf hardware can multiply two matrixes measured in seconds. You must be thinking of Linus Tech Tips.
  - BobbyJo 6y ago
    It is concerned with the lowest complexity method of doing so, which is directly related.
    - goldenkey 6y ago
      Tangentially, not directly. Algorithms become different beasts when implemented on real-world hardware.
      - BobbyJo 6y ago
        I said they are directly related, not that they are equivalent. The entire reason programmers have the notion of time complexity is to understand how algorithm's execution scales. The reason we drop constants and constant scale factors is because they typically don't make a big difference in real world execution times. That's a little more than tangentially related. Saying time complexity has nothing to do with hardware is like saying speed limits have nothing to do with cars. Hardware constraints are the entire reason we developed the notion of time complexity. I'm honestly very confused as to how someone (I assume is) engaged in programming could think the relationship is tangential.
        goldenkey 6y ago
        You are arguing a different point, C.S. is not concerned with measuring performance in seconds. Do you agree or disagree? Now that we are on the same page, of course the asymptotic complexity of a method matters, but some of the lowest complexity methods actually have huge constants and cannot be used until you get to scales that dwarf most usages. This means that the connection is tangential. The current method of matrix multiply used in all your software is NOT the lowest asymptotic complexity method. Look it up.
afiori 6y ago
parallelism and data locality are also cs topics

Zenst 6y ago

>65536x65536 extended double precision matrices together For perspective, that would be akin to multiplying every MAC address with every other MAC address upon the entire IPv4 range.

nayuki 6y ago
MAC addresses are 48 bits and unrelated to IPv4. Multiplying two 65536×65536 matrices naively in O(n^3) time would be about the same number of operations as processing each possible MAC address.