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

21–30 of 46 posts

Re: Project Euler 001 the Hard Way

#21

Post by sorokod »

exdsq wrote: post #14
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…

It might be 'basic' but it's the starting point for most people! The fun things with these 'simple' problems is that you can solve them in so many ways. Two of my favourite posts I've recently read where they've solved beginner problems 'the Hard Way' are: 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/fiz…

"These queens can stab in eight directions. You always assumed that was a metaphor"

Excellent.

Re: Project Euler 001 the Hard Way

#22

Post by dahart »

Ragib_Zaman wrote: post #18
dahart wrote: post #15

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…

I disagree. Why would it be reasonable to assume "multiplication without a specific implementation is constant"? By definition, Big-O complexity describes what happens as a certain parameter gets arbitrarily large. If we say "ok but if we restrict that parameter to common sizes, it's actually O(1)", then everything is O(1). There is some constant C where Bubble sort will sort any array that fits into your RAM within…

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 predictable run time. When you use the built-in mults, you get to use O(1) for the purposes of your complexity analysis in return for a hard limit on the size of numbers you can multiply.

Your bubble sort example is contrived, but the answer is that it is okay to call a sort of 10 elements constant if that’s one component of a system and it doesn’t grow as the size of your input grows. The point of big-O is to understand the run time growth of your program, and if the sort inside doesn’t change as your input changes, then that piece is constant.

Re: Project Euler 001 the Hard Way

#23

Post by ubercow13 »

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?

What's the 'hard way'?

Re: Project Euler 001 the Hard Way

#24

Post by Ragib_Zaman »

dahart wrote: post #22
Ragib_Zaman wrote: post #18

Earlier quoted context omitted.

I disagree. Why would it be reasonable to assume "multiplication without a specific implementation is constant"? By definition, Big-O complexity describes what happens as a certain parameter gets arbitrarily large. If we say "ok but if we restrict that parameter to common sizes, it's actually O(1)", then everything is O(1). There is some constant C where Bubble sort will sort any array that fits into your RAM within…

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 comparison sort is at least O(n log n), regardless of algorithm or implementation). It is precisely a concept that applies to arbitrarily large inputs, that condition is at the core of its very definition.

If I designed a hardware board that runs bubble sort on any array that fits into its 16GB of memory and gave documentation printing out its (large) constant predictable run time, that still wouldn't make it correct to say Bubble sort is a constant time operation.

>Your bubble sort example is contrived, but the answer is that it is okay to call a sort of 10 elements constant if that’s one component of a system and it doesn’t grow as the size of your input grows...if the sort inside doesn’t change as your input changes, then that piece is constant.

We aren't talking about running on 10 elements and it staying at 10 elements as the size of the input grows (that would indeed be O(1)). For the original example in the link, we are talking about a piece (arithmeticSum) whose input is n, which tautologically does grow as the size of the input grows.

Re: Project Euler 001 the Hard Way

#25

Post by appleiigs »

ubercow13 wrote: post #23
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?

What's the 'hard way'?

The title of the post is the “Euler 001 the Hard Way”. The way i read it, the hard way would be “Solving all combinations with performance”.

Re: Project Euler 001 the Hard Way

#26

Post by evanpw »

Ragib_Zaman wrote: post #12

>...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.…

This argument comes up all the time, and the answer is that big-O notation is very general, and only makes sense relative to a particular computation model. For example, you may describe a sorting algorithm's complexity by counting the number of comparisons, abstracting away details like memory caching or arbitrarily-sized elements. So it's perfectly reasonable for the original author to call arithmeticSum constant time, assuming that the numbers are bounded, and it's also perfectly reasonable for other researchers to say that multiplication is O(n log n), without that assumption.

Re: Project Euler 001 the Hard Way

#27

Post by fctorial »

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.

Re: Project Euler 001 the Hard Way

#28

Post by [deleted] »

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?

[deleted]

Re: Project Euler 001 the Hard Way

#29

Post by kevinventullo »

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.

Re: Project Euler 001 the Hard Way

#30

Post by stevelosh »

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.

`n` is the position in the sequence:

    n=1 = (mod (* 1504170715041707 1) 4503599627370517) = 1504170715041707
    n=2 = (mod (* 1504170715041707 2) 4503599627370517) = 3008341430083414
    n=3 = (mod (* 1504170715041707 3) 4503599627370517) = 8912517754604
Post reply on HN