-1

I need some help to resolv this formula:

V[i] = ([ V[i-1] * V[i-1] / (i + 2)] + V[ i-1] * i + i + 1) % 666013 where v[0] = 3 and example: v[10000000] = 22230

My solution is:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>

using namespace std;

ifstream fin ("smen.in");
ofstream fout ("smen.out");

unsigned long long int n, k;
int mod = 666013;

int numereus(int n)
{
    if (n > 0)
    {
        k = numereus(n-1) % mod;
        return ((((((((k*k)% mod)/((n%mod+2) % mod))%mod)+(k*(n%mod))% mod)% mod) + (n % mod)) % mod + 1) % mod;
    }
    else
    {
        return 3;
    }
}

int main()
{
    cin >> n;
    cout << numereus(n);
    return 0 ;
}

My C++ solution is no working for numbers > 25000

4
  • 2
    Possible integer overflow?
    – Levi
    May 11, 2015 at 5:59
  • 5
    i guess it is more likely a stack overflow causes by too many recursions
    – bazz-dee
    May 11, 2015 at 6:01
  • 1
    ...and get rid of your global variables.
    – deviantfan
    May 11, 2015 at 6:04
  • 1
    You can't just mod everything in sight when a division is involved. E.g., 4 choose 2 = 6, but 4 choose 2 mod 4 = 2 which has basically no relation to (4 mod 4) choose (2 mod 4) = 0 choose 2 = 0. Your case is probably simpler but there still may be issues. Is 666013 prime, for example? Are the v[i] always integers, or might they be rational numbers? May 11, 2015 at 6:20

2 Answers 2

2

Recursive solutions are best in those situations that move quickly towards the base case.

For example, a binary search gets rid of half the solution space for every recurrence so that you could search four billion items in about thirty-two levels of recursion.

Your algorithm to process 25,000 items requires 25,000 stack frames so is probably more suited for an iterative solution. The stack is not an infinite resource.

In terms of implementing an iterative solution, see the following pseudo-code which should give you an idea:

def fn(n):
    rv = 3
    i = 0
    while n > 0:
        i = i + 1
        rv = (rv * rv / (i + 2) + rv * i + i + 1) % 666013
        n = n - 1
    return rv

Here's a proof-of-concept in Python, which looks remarkably similar to the code above because, to be honest, if you ditch all that lambda/closure/list-comprehension stuff, Python makes the perfect pseudo-code language :-)

def fn(n):
    rv = 3
    i = 0
    while n > 0:
        i = i + 1
        rv = (rv * rv / (i + 2) + rv * i + i + 1) % 666013
        n = n - 1
    return rv

print fn(0)
print fn(1)
print fn(2)
print fn(10000000)

This outputs:

3
8
35
22230

the last of which appears to be the correct value for 10,000,000 as per your question.


The equivalent C++ code would be along the lines of:

#include <iostream>

int numereus (int n) {
    unsigned long long int rv = 3;
    int i = 0;
    while (n-- > 0) {
        i = i + 1;
        rv = (rv * rv / (i + 2) + rv * i + i + 1) % 666013;
    }
    return rv;
}

int main (void) {
    std::cout
        << numereus(0) << '\n'
        << numereus(1) << '\n'
        << numereus(2) << '\n'
        << numereus(10000000) << '\n';
    return 0 ;
}
4
  • Hm... But I need a solution for numbers > 10^6, and I think my algorithm is wrong,,, Any idea why? May 11, 2015 at 6:07
  • @Cristian, your algorithm (i.e., the formula you've created from the question) may well be wrong but your approach to solving the problem almost certainly is.
    – paxdiablo
    May 11, 2015 at 6:13
  • @CristianSandu With %666013 and a square in the formula, you have the integer overflow problem mentioned above too. Use 64bit variables.
    – deviantfan
    May 11, 2015 at 6:15
  • Hm... but for numbers >8*10^5? May 11, 2015 at 6:16
0

A cheap way of keeping your existing code is to use memoization. Your code is fairly easy to write in a loop, and that should probably be your preferred method in this case, but memoization is good to know about.

The idea is to store the results of expensive computations in a cache and later retrieve them to save time (or resources).

In the case of your code, each time numereus is called it stores its answer in an array. If numereus is later called with the same arguments it checks to see if it has an answer in the array and, if so, returns that answer without doing further recursion or calculation.

To answer your question, we can repeatedly call numereus with ever larger values to build up the cache. This prevents the possibility of stack overflows and still works in O(N) time because each call to numereus(i) is able to get the cached value of numereus(i-1).

Granted, you're going to burn a lot of memory building a cache this large. One way to deal with that is to cache only every xth value. For instance, you could cache only inputs from even numbers. This halves the amount of storage space you need while doubling your recursion depth.

In the case of your question, the following untested code could work:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>

#include <vector>

using namespace std;

ifstream fin ("smen.in");
ofstream fout ("smen.out");

unsigned long long int n, k;
int mod = 666013;

int numereus(std::vector<int> &memoized, int n){
    if(memoized[n]!=-1)
        return memoized[n];

    if (n > 0){
        k = numereus(memoized,n-1) % mod;
        return memoized[n]=((((((((k*k)% mod)/((n%mod+2) % mod))%mod)+(k*(n%mod))% mod)% mod) + (n % mod)) % mod + 1) % mod;
    } else {
        return 3;
    }
}

int main()
{
    std::vector<int> memoized(10000000);
    //I use -1 as a place holder here. Just make sure this is a value your function can never produce
    std::fill(memoized.begin(),memoized.end(),-1);
    cin >> n;

    for(int i=0;i<n;i++) //Build table of answers
      numereus(memoized,i);

    cout << numereus(memoized,n);
    return 0 ;
}
4
  • And how is this better than the single last value, other than wasting memory? (All values other than the last one aren´t necessary anymore)
    – deviantfan
    May 11, 2015 at 7:26
  • 1
    @deviantfan, in all fairness, memoisation will be of benefit if you get rid of the pre-fill code (which sort of defeats the whole lazy nature of the method, turning into a big honkin' fully populated lookup table) and then do cout << numereus(99999); cout << numereus(100000); - the second call should return much faster because there'' be fewer levels of recursion. You still have the problem with stack depth though.
    – paxdiablo
    May 11, 2015 at 9:27
  • @deviantfan, the pre-fill is necessary to avoid stackoverflows in the general case. Note that running a memoized copy of the command would, in fact, have the same effect has pre-filling in this instance, but would expose the risk of a stack overflow. Knowledge of a safe maximum stack size allows one to reduce memory usage significantly.
    – Richard
    May 11, 2015 at 16:14
  • @deviantfan, see the commentary above. paxdiablo addresses the method you prefer. This alternative will not be useful in all cases, but does provide another way to consider the problem which may be useful to OP, especially if they have provided a MWE.
    – Richard
    May 11, 2015 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.