Long Long arrays

[hennelh]

A recent assignment involved using very large integer values. A formula and very large x values were given and we had to compute the value of f(x). The tutor suggested using long long values as the 0 < x < 10^18.

The function F(x) = F(x/2) - x if x even; F((x+1)/2) + x if x odd. F(1) = 3;

We were given a range of x values and a memory limit of 1mb (It was an exercise in space/time tradeoff). What we were taught was to compute all the values once, store them and then read off the ones we needed instead of recomputing them each time. Due to the nature of the function I thought it would be best to do it this way but with such large possible values I'm unsure as to its effectiveness.

My plan:
1.) Find the largest of the x values.
2.) Create

long long range[max]

3.) Compute all values up until that largest value (since F(8) relies on F(4) which relies on F(2) and so on).
4.) Read off the array for the respective F(x) values.

The problem was that I got a segmentation fault during 2.). It worked fine for values under 6 digits but failed otherwise.

Was I wrong to try and use long long array?

Note:
x values gathered from std::cin
unsigned long long didn't work either
g++ compiler (no clue to version actually, think 4.3 if there is such a thing)
ubuntu machine

Thanks in advance for any assistance :)

[mike_2000_17]

You cannot use an array that big. Your problem definition specified a limit of 1Mb, I guess it means you need to stick to that. You say that 6 digit numbers or less works fine in your range array. But more that 6 digit, i.e. 1 million, would cause the range array to be at least 8 Mb in size (each long long is at least 8 bytes), that is already way above your specified limit, and it also happens to be above your program's limit too, and that explains the error.

You need to find another strategy than holding all the values. For example, you could hold every 10 value and interpolate in-between them. It also depends on what function you have, you might be able to manipulate the math somehow to store only a subset of all the range and be able to efficient compute any other value from that subset.

[hennelh]

Thanks for the reply and insight. I will have to look at changing my stategy because looking at the question again there is no way that the memory constraint would be satisfied.