7

what is the fastest method to calculate this, i saw some people using matrices and when i searched on the internet, they talked about eigen values and eigen vectors (no idea about this stuff)...there was a question which reduced to a recursive equation f(n) = (2*f(n-1)) + 2 , and f(1) = 1, n could be upto 10^9.... i already tried using DP, storing upto 1000000 values and using the common fast exponentiation method, it all timed out im generally weak in these modulo questions, which require computing large values

manu4rhyme
  • 83
  • 1
  • 4
  • 3
    What language/tool? In general, a PowMod or ModPow function performs this sort of calculation. See http://en.wikipedia.org/wiki/Modular_exponentiation – hatchet - done with SOverflow May 24 '14 at 15:28
  • 3
    Fastest method is pencil and paper: `140625001` – ypercubeᵀᴹ May 24 '14 at 15:46
  • 3
    This is a recurring topic, just search for this special number, http://stackoverflow.com/search?tab=relevance&q=1000000007. For instance, in http://stackoverflow.com/questions/9220416/need-help-in-mod-1000000007 or the duplicate http://stackoverflow.com/questions/11289495/what-is-the-fastest-way-to-compute-large-power-of-2-modulo-a-number – Lutz Lehmann May 24 '14 at 17:25

3 Answers3

2
f(n) = (2*f(n-1)) + 2 with f(1)=1

is equivalent to

(f(n)+2) = 2 * (f(n-1)+2)
         = ...
         = 2^(n-1) * (f(1)+2) = 3 * 2^(n-1)

so that finally

f(n) = 3 * 2^(n-1) - 2

where you can then apply fast modular power methods.

Lutz Lehmann
  • 25,219
  • 2
  • 22
  • 51
  • For the German-speaking ones interested, I vaguely remember the topic covered in the textbook "Algorithmische Zahlentheorie" by Otto Forster. – Codor May 24 '14 at 19:04
2

Modular exponentiation by the square-and-multiply method:

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x
user448810
  • 17,381
  • 4
  • 34
  • 59
0

C code for calculating 2^n

    const int mod = 1e9+7;

    //Here base is assumed to be 2
    int cal_pow(int x){
        int res;
        if (x == 0) res=1;
        else if (x == 1)    res=2;
        else {
            res = cal_pow(x/2);
            if (x % 2 == 0) 
                res = (res * res) % mod;
            else
                res = (((res*res) % mod) * 2) % mod;
        }
        return res;
    }
ssp4all
  • 371
  • 2
  • 11