Problem 210

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

[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?

[deejinator]

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

[Svartskägg]

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

Not me. My program overflows for 10^10.

[deejinator]

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

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

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

[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

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

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

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