11–20 of 46 posts
Isn't this like... really, really basic? I would have never considered iterating over all the numbers, not even when I first entered Project Euler back in 2011; inclusion-exclusion always was the obvious way. I'm probably biased since I'm a big Project Euler fan and I probably have a much more math-oriented way of thinking than the average software developer, so take my opinion with a grain of salt. Most serious Proj…
I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))).
Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently. David Harvey proved last year that multiplication of two n bit integers can be done in O(n log n). It is still an open conjecture that this is the best possible.
Two quick remarks: > Looking at the code it’s quite obvious 3 and 5 are replaceable with any set of other numbers. What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", w…
What's not obvious to me (I'm not a mathematician) is that both solutions answer the question correctly when the set of numbers is not pairwise coprime. For example, "Find the sum of all the multiples of 3 or 6 below 1000" is clearly just the same as "Find the sum of all the multiples of 3 below 1000", while the inclusion-exclusion algorithm will probably deliver a different answer. You’re right. The solution for thi…
Nice, and it works for my example, too:
Number of multiples of either 3 or 6
= Number of multiples of 3
+ Number of multiples of 6
- Number of multiples of lcm(3,6) = 6
= Number of multiples of 3
Isn't this like... really, really basic? I would have never considered iterating over all the numbers, not even when I first entered Project Euler back in 2011; inclusion-exclusion always was the obvious way. I'm probably biased since I'm a big Project Euler fan and I probably have a much more math-oriented way of thinking than the average software developer, so take my opinion with a grain of salt. Most serious Proj…
FizzBuzz with a domain specific language [1] and the N Queens problem without declaring a value type [2]
[1] https://themonadreader.files.wordpress.com/2014/04/fizzbuzz....
[2] https://aphyr.com/posts/342-typing-the-technical-interview
>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))). Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently.…
> the author claims the arithmeticSum method is O(1)
He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on computers that support arbitrarily large numbers.
> Many people seem to assume that multiplication is a constant time operation.
Multiplication is constant time for the built-in data types, for any 64-bit ints or doubles. It’s okay to call it constant until you use huge number methods.
>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))). Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently.…
You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on comp…
Earlier quoted context omitted.
You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on comp…
But the author follows that with "It works the same way for 100 as it does 10e100."
The 10e100 comment does precede the implementation, and this particular O(1) implementation of course might not support inputs in the range of 10e100 exactly.
>...where I discover the hidden complexity of a simple programming problem. I thought it was very ironic that soon after that sentence, the author claims the arithmeticSum method is O(1) when it is actually O(log(n) log(log(n))). Many people seem to assume that multiplication is a constant time operation. There is actually immense "hidden complexity" in doing multiplication of arbitrarily large integers efficiently.…
You’re right, and it’s a good point, but I think you’re too hard on the author and other people. > the author claims the arithmeticSum method is O(1) He really claimed that Gauss’ formula is O(1), where it’s reasonable to assume multiplication without a specific implementation is constant. After that he gave an implementation in JavaScript that is O(1). It’s only a larger complexity if you use numeric methods on comp…
Would they be impressed by the math? Or would they complain about the number of lines of code, readability for code review, etc?