return very large integer from recursive function

Question

I have made a recursive function in c++ which deals with very large integers.

long long int findfirst(int level)
{
    if(level==1)
    return 1;
    else if(level%2==0)
    return (2*findfirst(--level));
    else
    return (2*findfirst(--level)-1);
}

when the input variable(level) is high,it reaches the limit of long long int and gives me wrong output. i want to print (output%mod) where mod is 10^9+7(^ is power) .

int main()
{
    long long int first = findfirst(143)%1000000007;
    cout << first;
}

It prints -194114669 .

[**MCVE please!**](http://stackoverflow.com/help/mcve) Quickly!! — πάντα ῥεῖ, Sep 07 '14 at 16:36
He's trying to say you need a Minimal, Complete, and Verifiable example. If what you say is the case, add a `main()` function, calling `findfirst` with the parameter `143LL`. — abligh, Sep 07 '14 at 16:41
@Beta Nope, it isn't! Use a decent online IDE like [coliru](http://coliru.stacked-crooked.com/) to show (proove) solutions. — πάντα ῥεῖ, Sep 07 '14 at 16:44
@Beta Probably I don't get what you mean with _"binary"_?!? If you have compilable source code, just show it. Posting a link to binary (executable) code, doesn't help very much anyone! (You're just trolling aren't you ;)?) — πάντα ῥεῖ, Sep 07 '14 at 16:50
@πάνταῥεῖ: Oh, them's fightin' words. I meant a way to print the output as a sequence of `{0,1}`. — Beta, Sep 07 '14 at 17:33

score 2 · Accepted Answer · answered Sep 07 '14 at 17:39

Normally online judges problem don't require the use of large integers (normally meaning almost always), if your solution need large integers probably is not the best solution to solve the problem.

Some notes about modular arithmetic

if a1 = b1 mod n and a2 = b2 mod n then:

a1 + a2 = b1 + b2 mod n
a1 - a2 = b1 - b2 mod n
a1 * a2 = b1 * b2 mod n

That mean that modular arithmetic is transitive (a + b * c) mod n could be calculated as (((b mod n) * (c mod n)) mod n + (a mod n)) mod n, I know there a lot of parenthesis and sub-expression but that is to avoid integer overflow as much as we can.

As long as I understand your program you don't need recursion at all:

#include <iostream>

using namespace std;

const long long int mod_value = 1000000007;

long long int findfirst(int level) {
    long long int res = 1;
    for (int lev = 1; lev <= level; lev++) {
        if (lev % 2 == 0)
            res = (2*res) % mod_value;
        else
            res = (2*res - 1) % mod_value;
    }
    return res;
}

int main() {
    for (int i = 1; i < 143; i++) {
        cout << findfirst(i) << endl;
    }
    return 0;
}

If you need to do recursion modify you solution to:

long long int findfirst(int level) {
    if (level == 1)
        return 1;
    else if (level % 2 == 0)
        return (2 * findfirst(--level)) % mod_value;
    else
        return (2 * findfirst(--level) - 1) % mod_value;
}

Where mod_value is the same as before:

Please make a good study of modular arithmetic and apply in the following online challenge (the reward of discovery the solution yourself is to high to let it go). Most of the online challenge has a mathematical background.

score 1 · Answer 2 · edited May 23 '17 at 12:29

1

If the problem is (as you say) it overflows long long int, then use an arbitrary precision Integer library. Examples are here.

edited May 23 '17 at 12:29

Community

1
1

answered Sep 07 '14 at 16:40

abligh

24,573
4
47
84

That appears to be the consensus answer :-) – abligh Sep 07 '14 at 16:43
@BasileStarynkevitch Can i use gmp library on online judges ? – Vaishal Sep 07 '14 at 16:52
@user3502857 _"Can i use gmp library on online judges ?"_ Probably not. – πάντα ῥεῖ Sep 07 '14 at 16:54
@abligh how to deal with this overflow without using external library ? – Vaishal Sep 07 '14 at 16:55
You could build your own arbitrary precision integer class with sufficient member functions to implement what is required here. You might base it on an array of bytes, for instance. – abligh Sep 07 '14 at 17:07

return very large integer from recursive function

2 Answers2