3 ms·
There's a story about when Gauss was a kid - a teacher asked the class to add up all the numbers between 1 and 100. Most kids licked their pencils and started w
by TheOtherHobbes 6y ago
There's a story about when Gauss was a kid - a teacher asked the class to add up all the numbers between 1 and 100. Most kids licked their pencils and started working out the sum the hard way. Gauss immediately intuited that 0 could be paired with 100, 1 could be paired with 99, 2 could be paired with 98... and the total was obvious.
That kind of Gauss-level insight doesn't seem to be about properties so much as about understanding the relationships that define a domain - and being able to view problems in a kind of conceptual relationship space which can generate insights that massively simplify simple problems, and make harder problems tractable at all.
I remember school math was mostly rote learning, but some problems required that creative insight. Academic math seems to lean more heavily on creative insights.
Software dev is similar. You can always do things the hard way, but it takes a certain kind of insight to see time-saving shortcuts and simplifications that cut right to the heart of a problem. I suspect some people have a natural talent for that insight, while others are more likely to take the long way to a solution.
- Gunax 6y agoGauss turned a O(n^2) problem into O(1)
- tshaddox 6y agoThe naive version is just O(n), right?
- firethief 6y agoAddition is O(log n), so the naive version is O(n log n). Gauss would have used a pre-[1960](https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm) multiplication algorithm, with complexity at best O((log n) ^ 2). Using an algorithm discovered in 2019 (cf. Harvey and van der Hoeven), it's possible to multiply in O(log n * log log n), if you have a lot of time. This is presumably optimal.
- tshaddox 6y agoSure, or you just define the input (the n) to be the number of digits in (the logarithm of) the number you’re summing up to. That’s generally how people talk about big O notation when it comes to basic arithmetic operations, mostly because we’re usually talking about computers with constant-time instructions for basic arithmetic operations (granted, only up to the maximum integer or float supported by the software).