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
jaap wrote:It maybe should be mentioned in this thread that in most computer languages a floating point type with 64 bits (e.g. a 'double') will only have essentially 53 bits to hold an integer value. It is therefore not accurate for integers above 253, or about 9*1015.
That is why I always use extended double precision floats in assembly for any computation involving integers which may be larger than 32 bits and up to 64 bits. That float type is 80 bits long which includes a full 64 bits for the mantissa and insures full precision for long ints.
A few years ago, I prepared a tutorial for the use of floating point instructions in assembly. The first chapter gives an overview of the "hardware" (FPU or co-processor) internals which one must be familiar with to avoid pitfalls for some of the instructions. The second chapter describes the data types which can be used with the instructions, including the format details of the three sizes of floats available according to the IEEE standard.
Even though it is not an absolute necessity to know those details when programming in languages other than assembly, the actual limits of the available float types may be very useful to know when designing an algo. For those who may be interested, the following link is to the part of the tutorial where the float types are described. It may also help to clear up some of the misconceptions some people may have about floats. (You can also have access to the entire tutorial from the bottom of that link.)
I like PE very much. However, one thing that I don't like about it is that the answer is getting bigger and bigger. The earlier problems never had answer more than 15 digits. Later problems require more than 16 digits. Even if you have the correct solution, you still need to take care of the precision problem, which is very tedious. Most people knows how to do it, but just tedious. Many times I want to quit PE just because of that. I still like the idea of no more than 15 digits for the answer.
We take care that all problems are solvable using only the standard 64 bit types. Of course, sometimes you have to think about overflow prevention (but you have to do that in real life calculations, too), but we try to keep that simple.
For this problem, it seems that one of the more common problems is that the sqrt function is not accurate enough for large arguments.
However, it never is far off, so you won't lose much time doing a little integer correction afterwards - or, better, don't use floating point numbers at all, do it all with integers and without sqrt (that's also faster).
The parameters for the problems are chosen so that a naive brute force would take long, that tends to lead to large numbers, the size of the answer is not a goal per se, nor are any overflow or precision problems. If you're suffering from precision problems, there's usually a better method using only integers.
Il faut respecter la montagne -- c'est pourquoi les gypaètes sont là.
There is a simple answer for the concern for large answers: we can take the answer mod something reasonable, depending on the problem. In this case, however, I don't think this makes the precision problem any less tedious.
So how do I fix the precision problem? I know nothing about the topic. Could anyone point me in the right direction, because I didn't find anything useful after some search. I know what the floating point precision problem is, I just don't know what to do about it. Any help will be appreciated.
Suppose we want the largest integer y whose square is less than say x, as in this problem (#210).
sqrt(x) gives a reasonable approximation of y at most a few steps away from the answer you want.
Then proceed as follows:
y=floor(sqrt(x))
while (y+1)*(y+1)<=x do y:=y+1
while y*y>x do y:=y-1
The second and third line will get you the wanted result.
War ruins the life and health of untold numbers of innocent children.
I don't exactly see what the size of the numbers involved has to do with an efficient algoritm to solve #210.
And we really wanted a stab in the direction of an efficient solution.
Well, designing efficient algoritms sometimes can be tedious.
From that point of view your criticism is totally unclear.
But perhaps the discussion should be started in the problem's forum and not here.
<Edit>
PM recieved.
Apologies accepted.
Certainly one can have his likes and dislikes for certain problems.
</Edit>
War ruins the life and health of untold numbers of innocent children.
Actually, I'd prefer to just apologize and remove my previous comment, since what is tedious and what is fun and interesting is definitely a personal thing.
