Power of 3 in mod 1000000007

Question

Let k be a positive integer. Is it possible to find out the value of 3^k in mod 1000000007?

I have written a C program code to do this but it gives a message on the screen (signal: segmentation fault(core dumped)) if k>=1000000. My code:

#include <stdio.h>
#include <math.h>
#include<stdlib.h>

unsigned long long int fun(unsigned long long int x, unsigned long long 
int L) {

  if(x==0) return 1;
  unsigned long long int y=(3*(fun(x-1,L)%L)%L + 1)%L;

  return y;
}
int main()
{
  unsigned long long int ans,B;
  unsigned long long int L=pow(10,9)+7;

  scanf("%llu",&B);


  B=B%500000003;
  if(B==0) {
     ans=1;
   } else {
      ans=(2*fun(B-1,L)%L +1)%L;
     }
   printf("%llu\n",(ans)%L);


}

In this code, I have used a recursive function "fun(k-1,1000000007)" that gives the value of the sum y = 1+3+9+....+3^(k-1) in mod 1000000007. So the answer will be 2*y+1 (mod 1000000007) = 3^k(mod 1000000007).

Answer 1

A better recurrence relation to use for computing (integer) pow(b, k) is:

if k is even:
    pow(b*b, k/2)
if k is odd:
    b * pow(b*b, k/2)

(here / is integer division, truncating). This requires only log₂k steps, rather than k steps.

Answer 2

When I executed your code for the K = 10^7, I got SIGSEGV.

This error occurs when the program tries to write/read outside the memory allocated for it.

Your case is the classic case of process running out of memory allocated to it by the OS.

The value of B >= 10^6, means that there will be more than 10^6 recursive calls to the function fun and the stack will keep piling up until the stack overflows (the memory allocated for stack is consumed) by the thread/process (instance of your code).

To avoid this, you should avoid using recursion with such large numbers.

You can solve this question by following techniques:

1. Dynamic programming.
2. Using loop.
3. Come up with some formula to get answer in single iteration.