Problem 192

[viv_ban]

thanks david,
Finally I get the right answer of the question. The precision involved in this particular question really screwed me. Initially I thought the problem was with my algorithm but the actual problem was with my precision which should atleast be equal to 60 decimal places.

[David F]

Pity those of us without BigNum support who had to work something else out. (I did it essentially the same as daniel.is.fischer's posted algorithm in the solution thread).

[stijn263]

Pity those of us without BigNum support who had to work something else out. (I did it essentially the same as daniel.is.fischer's posted algorithm in the solution thread).

Yup. I thought it was PE policy that having BigNum shouldn't give one this big an advantage over people who don't..

edit: And I think it's a great policy!! Maple is awfully slow, and I'm too lazy to get gmp working

[hk]

p192 can be solved with bignums, but at a considerable speed loss.
Moreover there is the follow up of p198. If one did not really understand what p192 was about and "cheated" with bignums p198 is considerably more difficult. (at least if one does not take the lessons given in the forum of p192)
Many complaints about p198 can be based on that.

[JamieCamardelle]

Can anyone confirm or deny that the sum of the denominators of the best appromations for sqrt[n] with denominator bound 10^12 as n goes from 2 to 100 and n is not a perfect square is 757577250?
I am trying something out with AffineRationalize in Mathematica.

[Tommy137]

Your result is way too low

[JamieCamardelle]

Thanks. Serves me right - I was trying a lazy way out.

[karlo]

I am trying to solve 192. I first did the examples given in the problem and got the answers. I am not sure though that the method I am using is correct. Is there anyone whom I could send my fraction for sqrt(13) and the bound 10**12, and tell me if it's right? Thanks.

[ThomasH]

You are welcome - send a PM to me.

[ThomasH]

Your denominator is wrong.

[mdean]

It seems this problem is going to haunt me. I even wrote my first program in C# to take advantage of the 128 bit decimal type with 29 digits of precision and it's still wrong. I've got to be missing something.

[thundre]

It seems this problem is going to haunt me. I even wrote my first program in C# to take advantage of the 128 bit decimal type with 29 digits of precision and it's still wrong. I've got to be missing something.

That should be enough precision to compare two prospective answers, but I don't see where you find enough time to perform the calculation 10¹⁷ times. You're probably not trying some of the correct denominators.

The intended solution is a well-known algorithm, and it can be implemented with 64-bit arithmetic.

[mdean]

That should be enough precision to compare two prospective answers, but I don't see where you find enough time to perform the calculation 10¹⁷ times. You're probably not trying some of the correct denominators.

The intended solution is a well-known algorithm, and it can be implemented with 64-bit arithmetic.

I don't know where that $10^{17}$ comes from. I've posted in the solutions thread by the way (didn't break 1 minute, but less than 10). With my original method, C# was unable to compare $\sqrt{6760}=$

82.219219164377862631971232155251

and $\dfrac{82094249361619}{998480041479}=$

82.219219164377862631971232161351

necessitating another plan of attack.

[hk]

Please read Daniel.is.Fisher's post of 4 May 2008 1.15 am on that forum.

[DeKlod]

Hi all,
I'm going slightly mad here: fairly sure my algorithm is right (gives 902212330695 for sqrt(4850) anyway), but can't seem to get the right answer. Any volunteers for a PM to validate my method and/or some other examples?
Cheers,
Claude

[FreeCaenepeel]

Shouldn't the best approximation for the square root of 4850
be 22555308267375/323875351814
instead of
62831818251916/902212330695

the distance to sqrt(4850) for the first fraction is
6.432420812874472099060302734375E-15

whereas for the second fraction it is indeed larger
6.432420816296734800060302734375E-15

I use Decimal() in Python to do the divisions.

[DJohn]

62831818251916/902212330695 is correct. The differences are very small, and the sort of error you get from floating point approximations will be much greater.