Lagged Fibonacci Rng For Project Euler #149

Question

Hey guys, this is very likely a total brain fart on my part but I was hoping someone could have a look at the following statement which describes how to set up the lagged fibonacci rng:

First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator":

For 1 ≤ k ≤ 55, s(k) = [100003 − 200003k + 300007k^(3)] (modulo 1000000) − 500000.

For 56 ≤ k ≤ 4000000, s(k) = [s(k−24) + s(k−55) + 1000000] (modulo 1000000) − 500000.

Thus, s(10) = −393027 and s(100) = 86613.

So seems pretty straightforward (this is used to generate the matrix, which is then the actual problem to be solved, this link has the question). Anyways, here is my implementation and its output for s(10) and s(100):

class lagged_fib
{
private:
    typedef std::deque<int> seed_list;
    seed_list seeds;
    size_t k;

public:
    lagged_fib()
    {
     k = 1;
    }
    int operator()()
    {
     if (k<56)
     {
      seeds.push_back(((100003 - 200003*k + 300007*k*k*k)%1000000) - 500000);
      k++;
     }
     else
     {
      seeds.push_back(((seeds[31]+seeds[0]+1000000)%1000000) - 500000);
      seeds.pop_front();
     }  
     return seeds.back();  
    }
};

Which yields:

s(10) = -393027
s(100) = -422827

You'll note that s(10) is as expected (so assumably the first part of the algorithm is correct), but s(100) is not. So, hopefully someone can spot where I've gone wrong, this is driving me up the wall.

Thanks

Answer 1

My first answer was incorrect, due to hasty misreading of the C++. Corrected answer follows.

Answer 2

Looks like you're having integer overflows in your code.

Try using int64_t type instead of int.

Answer 3

Try performing the computation in long values rather than int values. The initialization is corrupted by a 32-bit integer overflow at k of 20.

Here is an excerpt of the output for int and long, following by the source code. The initialization portion prints the internal values to show where the overflow occurs.

integer arithmetic
  1:      200007  200007 -299993
  2:     2100053  100053 -399947
  3:     7600183  600183  100183
  4:    18500439  500439     439
  5:    36600863  600863  100863
  6:    63701497  701497  201497
  7:   101602383  602383  102383
  8:   152103563  103563 -396437
  9:   217005079    5079 -494921
 10:   298106973  106973 -393027
 11:   397209287  209287 -290713
 12:   516112063  112063 -387937
 13:   656615343  615343  115343
 14:   820519169  519169   19169
 15:  1009623583  623583  123583
 16:  1225728627  728627  228627
 17:  1470634343  634343  134343
 18:  1746140773  140773 -359227
 19:  2054047959   47959 -452041
 20: -1898811353 -811353 -1311353
 21: -1520702529 -702529 -1202529
 22: -1104792823 -792823 -1292823
 23:  -649282193 -282193 -782193
 24:  -152370597 -370597 -870597
 25:   387742007  742007  242007
 ...
 55: -1636843089 -843089 -1343089
 56:   94698
 ...
 99: -596227
100: -357419

long arithmetic
  1:      200007  200007 -299993
  2:     2100053  100053 -399947
  3:     7600183  600183  100183
  4:    18500439  500439     439
  5:    36600863  600863  100863
  6:    63701497  701497  201497
  7:   101602383  602383  102383
  8:   152103563  103563 -396437
  9:   217005079    5079 -494921
 10:   298106973  106973 -393027
 11:   397209287  209287 -290713
 12:   516112063  112063 -387937
 13:   656615343  615343  115343
 14:   820519169  519169   19169
 15:  1009623583  623583  123583
 16:  1225728627  728627  228627
 17:  1470634343  634343  134343
 18:  1746140773  140773 -359227
 19:  2054047959   47959 -452041
 20:  2396155943  155943 -344057
 21:  2774264767  264767 -235233
 22:  3190174473  174473 -325527
 23:  3645685103  685103  185103
 24:  4142596699  596699   96699
 25:  4682709303  709303  209303
 ...
 55: 49902764463  764463  264463
 56:   29290
 ...
 99: -119491
100:   86613

---

public class LaggedFib {

    public static void main(String[] args) {
        int[] buffer = new int[56];
        computeInt(buffer);
        computeLong(buffer);
    }

    private static void computeInt(int[] buffer) {
        System.out.println("\n    integer arithmetic");
        for (int k = 1; k < 56; ++k) {
            int partial = 100003 - 200003 * k + 300007 * k * k * k;
            int modded = partial % 1000000;
            buffer[k] = modded - 500000;
            System.out.printf("    %3d: %11d %7d %7d\n", k, partial, modded, buffer[k]);
        }
        for (int k = 56; k <= 100; ++k) {
            int p24 = (k - 24) % 56;
            int p55 = (k - 55) % 56;
            int pk  = k % 56;
            buffer[pk] = ((buffer[p24] + buffer[p55] + 1000000) % 1000000) - 500000;
            System.out.printf("    %3d: %7d\n", k, buffer[pk]);
        }
    }

    private static void computeLong(int[] buffer) {
        System.out.println("\n    long arithmetic");
        for (int k = 1; k < 56; ++k) {
            long partial = 100003L - 200003L * k + 300007L * k * k * k;
            long modded = partial % 1000000L;
            buffer[k] = (int) (modded - 500000L);
            System.out.printf("    %3d: %11d %7d %7d\n", k, partial, modded, buffer[k]);
        }
        for (int k = 56; k <= 100; ++k) {
            int p24 = (k - 24) % 56;
            int p55 = (k - 55) % 56;
            int pk  = k % 56;
            buffer[pk] = (int)(((buffer[p24] + buffer[p55] + 1000000L) % 1000000L) - 500000L);
            System.out.printf("    %3d: %7d\n", k, buffer[pk]);
        }
    }

}