Problem 210

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
User avatar
hk
Administrator
Posts: 10660
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 210

Post by hk »

I suspect that Python converts the integer x to a double before calculating x**0.5. In that case the accuracy is not enough if you don't take measures.
Image

coreyjkelly
Posts: 7
Joined: Fri Dec 28, 2012 5:54 am
Location: Canada

Re: Problem 210

Post by coreyjkelly »

I'm fairly confident that my algorithm is correct, and that I'm having issues with the accuracy problems others have mentioned. I thought I had dealt with them, but I'm still getting the wrong answer. Four days dealing with precision problems is enough for me.
Is there anybody I can PM with some code/results for a nudge in the right direction?
Image

deejinator
Posts: 9
Joined: Tue Feb 25, 2014 5:41 pm

Re: Problem 210

Post by deejinator »

Anybody want to verify my answer for 10^10 in the solution forum?

Svartskägg
Posts: 55
Joined: Thu Mar 29, 2012 11:55 am
Location: Sweden

Re: Problem 210

Post by Svartskägg »

deejinator wrote:Anybody want to verify my answer for 10^10 in the solution forum?
Not me. My program overflows for 10^10.
Image
320641_5486fc18ea1dcc4e9a8f29c7677a5c19 <-- my friend key

deejinator
Posts: 9
Joined: Tue Feb 25, 2014 5:41 pm

Re: Problem 210

Post by deejinator »

Never mind, somebody already did it on page 3. My answer was short by exactly 2^32 :)

Steve N
Posts: 12
Joined: Tue May 29, 2012 10:22 pm
Location: Cheshire, England

Re: Problem 210

Post by Steve N »

I've just got the correct answer but I have a concern that I'd be grateful for some help with. I will hasten to add that I am a very amateurish programmer which my question is likely to expose:

My program to generate the answer uses integer arithmetic only (no sqrts) and coding in VB I defined all of my variables to be long. It gave correct answers for all the intermediate values posted in this thread, but when I used r=1000000000 (for the full problem) my answer was very slightly wrong. Suspecting some sort of accuracy issue, I changed all of my longs to bigintegers (which dramatically increased runtime) and then got the right answer.

Why would long have given me the wrong answer when the program ran ok? I thought I'd get some sort of overflow error if my integers were too big.

PS Hope it is ok to post here. The solution forum isn't very active.
Image

User avatar
hk
Administrator
Posts: 10660
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 210

Post by hk »

Unfortunately VB is not a very accurate description of the language you're using because there are many versions of that language.
You should look for a datatype with more precision than "long".
Does it have something like "long long" ,"int64", "ULong" or "Decimal"?
Anyhow you should look for a datatype with at least 8 bytes= 64 bits of precision.
Inspect your manual about that.
Image

Steve N
Posts: 12
Joined: Tue May 29, 2012 10:22 pm
Location: Cheshire, England

Re: Problem 210

Post by Steve N »

Thanks, hk. Sorry its taken me a few days to get back to you.

I am using VB.net where the 8-byte datatype is simply denoted 'long'. See the reference at this link.

https://msdn.microsoft.com/en-gb/library/47zceaw7.aspx
Image

v6ph1
Posts: 119
Joined: Mon Aug 25, 2014 6:14 pm

Re: Problem 210

Post by v6ph1 »

If the BigInteger result is correct and your Long result not, there must be an overflow in it:
Long is approx -9E18 to 9E18, so within some operation, your calculation must exceed this range.

N^2 = (1E9)^2=1E18 is not soo far below, If you have some other factors in your square compare code, then it may overflows.
Calculations which have an overflow during their evaluation, also overflows. If so, you may rewrite this line so that it not overflows or force (only for this piece of code) an other integer type.

If you have no clue, you might provide me your code for finding the line.
Image

User avatar
rayfil
Administrator
Posts: 1403
Joined: Sun Mar 26, 2006 4:30 am
Location: Ontario, Canada
Contact:

Re: Problem 210

Post by rayfil »

Steve N
If your 'long' is a 64-bit float, have a look at this previous post on page 2 of this thread (viewtopic.php?f=50&t=1111&start=15#p10571) and also at japp's post at the very top of the same page.
I know it's a long thread (5 pages) but you would most probably have found an answer to your problem by reading it first.
When you assume something, you risk being wrong half the time.

User avatar
bole79
Posts: 2
Joined: Fri Nov 29, 2019 10:53 am

Re: Problem 210

Post by bole79 »

I was also a bit dumbfounded at an invalid answer at the problem size, but I'm familiar with invalid rounding in Java in extreme cases. I feel such precision sub-problem is a charming feature of a PE problem. In this case however, changing the analysis and moving from square root to integers only seems more elegant.
Image

Post Reply