Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Project Euler 001 the Hard Way

statagroup.com

Post reply on HN
Print view View original

31–40 of 46 posts

Re: Project Euler 001 the Hard Way

#31

Post by philiplu »

fctorial wrote: post #27
gordaco wrote: post #4

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…

From the problem 700: Consider the sequence 1504170715041707n mod 4503599627370517 Could you explain what 'n mod' means? Google doesn't seem to know what that is.

The problem is a bit underspecified, perhaps. 'n' is a positive integer, so 1, 2, 3, .... So the sequence is found by multiplying 1504170715041707 by 1, 2, 3, ... sequentially, then finding the remainder when you divide each of those products by 4503599627370517.

Re: Project Euler 001 the Hard Way

#32

Post by dahart »

Ragib_Zaman wrote: post #24
dahart wrote: post #22

Earlier quoted context omitted.

By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. The reason 64 bit mults are constant is because we have a hardware implementation of multiplication that has a constant pre…

>By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. Time complexity is usually for specific algorithms, though it can also be studied for a general problem itself (e.g. any c…

> though it can also be studied for a general problem itself (e.g. any comparison sort is at least O(n log n)

Note that we call sort O(n log n) under the assumption that addition and comparison is O(1), just like the author did with multiplication. If you’re trying to make the point that arbitrarily large inputs have non-constant complexity, you should be consistent. No operations on arbitrarily large numbers are constant on the number of digits, but that is not a good model for predicting actual runtimes of actual programs that use doubles. When I use ints or longs or doubles, it is not just appropriate to use O(1) for the basic arithmetic operations, it is incorrect to assume larger complexity when that larger complexity does not apply to your program.

Re: Project Euler 001 the Hard Way

#34

Post by jarekkruk »

FabHK wrote: post #13
Someone wrote: post #10

Earlier quoted context omitted.

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…

> The solution for this is to replace “product of n and m” bij “least common multiple of n and m” 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 Cool. How to extend to more than 2 numbers?

You could do it like in article, so for every nonempty element in powerset (combinations for each length) of those numbers calculate their lcm and add or subtract amount of multiplies of lcm according to length of element.

So for A, B, C you have (M-number of multipliers) M(lcm(A)) + M(lcm(B)) + M(lcm(C)) - M(lcm(B,C)) - M(lcm(A,C)) - M(lcm(A,B)) + M(lcm(A,B,C))

Re: Project Euler 001 the Hard Way

#35

Post by dahart »

appleiigs wrote: post #19

If i was shown the fizz buzz question in a job interview, and i answered using the “hard way”, how would they respond? Would they be impressed by the math? Or would they complain about the number of lines of code, readability for code review, etc?

I think that’s a good question. I’ve interviewed and hired a lot of people, and if someone answered the question this way, I think I would enjoy the ‘hard way’ answer.

It would depend on the style and framing of the answer as much as the substance. It’s easy to enjoy as a ‘let’s explore the bounds of this problem’ or a ‘let’s do this in an unnecessarily difficult generalization, just for fun/curiosity’. It would be useful in an interview if the candidate recognizes and states that this might be a bad engineering decision, even if it’s good math.

When I’m hiring, I want to find people that can generalize and explore a problem, see the larger picture in an interesting way. This article does that. And, just as important is finding people who know when not to do that in practice, who can recognize when and why it’s important to call something good enough, and move on to other problems.

Re: Project Euler 001 the Hard Way

#37

Post by foxes »

The inclusion/ exclusion idea can actually be useful for harder project euler questions (deriving some sort of closed form sum to compute). Worthwhile to think about.

Im also reminded about the "semigroup resonance" way to solve fizzbuzz posted recently on hn [0]. Seems like another interesting method.

[0] https://blog.ploeh.dk/2019/12/30/semigroup-resonance-fizzbuz...

Re: Project Euler 001 the Hard Way

#38

Post by chupasaurus »

kevinventullo wrote: post #29
FabHK wrote: post #8

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…

The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fairly early on assuming e.g. N << 2^M.

> you can stop as soon as the lcm's of your subsets exceed N

Actually if N < 2 * lcm, because you can't use the fact that the distribution of multiples is the same on (1, lcm) and (k * lcm+1, lcm(k+1)) while you still have to count on (N - N mod lcm + 1, N).

Re: Project Euler 001 the Hard Way

#39

Post by Ragib_Zaman »

dahart wrote: post #32
Ragib_Zaman wrote: post #24

Earlier quoted context omitted.

>By definition, big-O is for predicting the run-time growth of a specific implementation. It doesn’t directly apply to formulas. And it’s not an abstract concept that applies to arbitrary inputs that the program you’re analyzing can’t process by design. You cannot assume arbitrarily large inputs. Time complexity is usually for specific algorithms, though it can also be studied for a general problem itself (e.g. any c…

> though it can also be studied for a general problem itself (e.g. any comparison sort is at least O(n log n) Note that we call sort O(n log n) under the assumption that addition and comparison is O(1), just like the author did with multiplication. If you’re trying to make the point that arbitrarily large inputs have non-constant complexity, you should be consistent. No operations on arbitrarily large numbers are con…

> Note that we call sort O(n log n) under the assumption that addition and comparison is O(1), just like the author did with multiplication. If you’re trying to make the point that arbitrarily large inputs have non-constant complexity, you should be consistent.

I have been consistent. I agreed above that is buuble sort was one part of a program that you only call on elements of size up to 10 and the input of the program, n, is something else then the bubble sort piece is O(1). But if n refers to the size of an array input into a bubble sort, then it is not O(1). Big-O considers what happens when the size of the _input_ grows. For a comparison sort we consider what happens where the _number_ of elements goes to infinity, but the elements themselves are assumed to bounded (e.g. 32 bit ints). This ensures comparison is O(1) not matter which two elements of the array you chosen from an arbitrarily large array. I don't see why you think the addition involved in a comparison sort wouldn't be O(1) as the addition addition that is required to increment pointers by 1.

> No operations on arbitrarily large numbers are constant on the number of digits, but that is not a good model for predicting actual runtimes of actual programs that use doubles. When I use ints or longs or doubles, it is not just appropriate to use O(1) for the basic arithmetic operations, it is incorrect to assume larger complexity when that larger complexity does not apply to your program.

You're describing the common situation when analysing a program is that the input of the program is some parameter (E.g. the size of an array) and all the integer arithmetic that arises during that program is on ints or doubles, so the program executes correctly _even as_ the input grows.

The key difference for this project Euler example is that there the input n is actually an integer that we do the main arithmetic on. The point of the program is to sum integers up to n. As I've explained before, if you then say "but practically we limit n to ints so it's O(1)" then _any_ function I write whose only input is an int is O(1) and the notion is meaningless.

Re: Project Euler 001 the Hard Way

#40

Post by dahart »

Ragib_Zaman wrote: post #39
dahart wrote: post #32

Earlier quoted context omitted.

> though it can also be studied for a general problem itself (e.g. any comparison sort is at least O(n log n) Note that we call sort O(n log n) under the assumption that addition and comparison is O(1), just like the author did with multiplication. If you’re trying to make the point that arbitrarily large inputs have non-constant complexity, you should be consistent. No operations on arbitrarily large numbers are con…

> Note that we call sort O(n log n) under the assumption that addition and comparison is O(1), just like the author did with multiplication. If you’re trying to make the point that arbitrarily large inputs have non-constant complexity, you should be consistent. I have been consistent. I agreed above that is buuble sort was one part of a program that you only call on elements of size up to 10 and the input of the prog…

You’re right, when a sort size depends on n, then it’s not considered O(1), I agree.

> I don’t see why you think the addition involved in a comparison sort wouldn’t be O(1)

Because you can’t have an infinite number of elements using 32-bit indices, you have to use indices that can represent up to n, and thus you must do arithmetic and comparsion operations on those indices that are not O(1). Considering that this was your original point, I’m totally confused why you’re now arguing against this point? It still seems inconsistent to me. Are you assuming that the size of the data elements to be sorted are 32 bits and that the only operations are on the data and not the indices? Bubble sort has to do both data comparisons and index comparisons, as well as index arithmetic. Adding 1 to a large n-bit number is worst case O(n).

> The key difference for this project Euler example is that there the input n is actually an integer that we do the main artithmetic on.

No, bubble sort has to do arithmetic on size n numbers too, as well as comparisons, the same as with Gauss’ formula.

> then _any_ function I write whose only input is an int is O(1) and the notion is meaningless.

No, this is both a straw-man and incorrect. A pure function on an int is only O(1) if it’s run-time doesn’t depend on the input. When the implementation is a constant number of 32-bit int operations on the input, and it doesn’t depend on what the value of the input is, then the function is O(1). Addition of two 32 bit ints on modern processors is O(1). Calculating whether an input int is prime, without having a lookup table in memory, for example, is not O(1), even though it’s a function of one 32-bit int.

Post reply on HN