3 ms·
But that performs very poorly on all architectures.
by codewiz 7y ago
But that performs very poorly on all architectures.
- vzaliva 7y agoit does not have to. A smart compiler can narrow it down to machine size integers then possible.
- desertrider12 7y agoIn many situations yes, and C/C++ compilers miss a lot of opportunities for constant folding/propagation. But still, an infinitely smart compiler can’t prove anything about a value that comes from a file, user input or socket at runtime. If control flow depends on those (which is true of every useful real-life program) then you’re out of luck. GMP arbitrary-size integers are amazingly fast but still much slower than native instructions, can’t be vectorized, require heap allocation, etc.
- klyrs 7y ago> A smart compiler can narrow it down to machine size integers then possible. A smart compiler will be able to narrow it down in a limited set of scenarios, but all we need to do is put an accumulator into a loop to see that bounding an integer is equivalent to the halting problem. Or for another example, should we expect our "smart" compiler to bound y in the following? The bound on x is a freebie. bigint n(uint64_t x) { bigint i = 0; bigint y = x; while (y != 1) { i++; if (y%2) y = y//2; else y = 3*y-1; } return i; }