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 :)

*Edited
by hennelh*: n/a