Problem 930

[ThePirate42]

What does it mean exactly to "give your answer in scientific format"?

[DJohn]

I haven't solved this problem yet, but I can at least answer this question. "Scientific format" means writing the number as <optional minus sign><single digit>.<multiple digits>e<optional minus sign><digits>. The example value given for G(6,6) is in this format: 1.681521567954e4.

That just means $1.681521567954\times10^4 = 16815.21567954$. It's common to use "e" in plain text where we can't write exponents.

The important bits: exactly one digit (which cannot be zero) before the decimal point, and for this problem exactly twelve digits after it.

[groooog]

Without giving anything away with specific details, I implemented two solutions for 930 - once which has exact precision and one that has float64 precision.

Both of them work for all example values given in the problem in a relatively short amount of time.

As n and m become large, however, the solution with exact precision (as is typical) begins to take too long, so I only run the float64 solution for values past F(8, 8).

However, the float64 solution loses precision past 9 or so significant digits past the decimal point. I use golang as my language of choice and the way go works, I'm quite sure that my answer can't really become any more precise (at least in go due to some golang internals; e.g. it only supports up to float64 and not float128 and based on how some of it's libraries work).

This is severely frustrating, because I'm confident my solution works and would get the proper solution had golang and some of it's internal libraries supported float128+.

I was wondering if the precision requirement could be relaxed by a few digits as I'm sure others may run into a similar issue.

[thedoctar]

I have the same issue. I thought PE problems are supposed to be designed to be solvable without external libraries and on old machines. (It's harder but always doable).

I have a fast approximate solution that could go well above the limits of the problem as well.

[heteroing]

I have a solution using only 64 bit floats which gives the right answer in under a second. If yours loses precision then you might have to rethink how you're doing it so that less accuracy is lost.

I don't disagree that the precision issue is really annoying. I only got my float solution to work a day after I solved it with Decimals. At the same time though I am not sure if lowering the number of required digits would be good. In any case it is possible without extra precision libraries.

[groooog]

I agree I don't have the optimal solution, but in most PE problems the norm is that there are range of solutions that vary from one second to a couple of minutes. I feel like the strict precision required by this problem is atypical of the usual PE format--it forces solvers to think only like the problem creator intended (perhaps), but prevents potentially other creative and unexpected solutions from working (specifically ones that are limited by machine/language constraints)

[groooog]

The more so frustrating part is that my solution would be perfectly acceptable had I written it in some flavor of C or a more math oriented language (which allows for higher degrees of precision with built-in libraries).

So I guess the root cause of my frustration is that I'm being penalized for choosing Go but I'd be totally fine if I implemented the same exact solution and algorithm in another language.

[thedoctar]

@grooooog

I solved it, but I kind of cheated as my algorithm used Python's Decimals and took 39 minutes (using PyPy).

The proper way to solve it uses a topic that I knew had to be used before hand, and the formula in the forums has an equivalent form I saw in some textbooks, but because it was in a field I've literally never studied, I wasn't able to use it

I agree though that users with float128 have an unfair advantage though. But I guess that's just life.

UPDATE: actually there's ways around the precision issue pointed out in the thread, now my solution only takes 63s

[groooog]

Thanks for the input @thedoctar !

However, I do feel the problem still persists

Admins, any thoughts on updating the precision?

[byhill]

I think another reason that they made the precision so high is to encourage solutions that differ from the most obvious techniques used to solve these types of problems. There are tons of really interesting and vastly different solutions displayed in the problem forum, all with really interesting maths. But if the precision was lower, you probably wouldn't see the large number of interesting, differing solutions you see now in the forum.

I was stuck in the same boat you were for a while, trying to overcome speed and precision issues. It's frustrating when trying to solve it, but I still agree with their decision to make the precision as it is.

[thedoctar]

I solved a much earlier problem which is actually related to this problem. Now I kind of understand why the problem is not too difficult, and also leads minor credence to the "inductive learning" model of Project Euler.

Although I would have never guessed the two problems were connected and I would not seek to know they were, even through the tag system (I never turned it on), as I think allowing internet search is a big enough hint (I'm not a big enough maths genius to know all the theory before solving problems).

The related problem is PE3XY where X, Y are unknown digits! If it's not in the current tag system, I can PM an admin the problem number to add it.

Also regarding possible cheating, I doubt it. Likely the #1 solver had possibly recently solved the related problem (or on the same topic elsewhere) so immediately knew the best method.