1

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).

Antor Sawon
  • 11
  • 2
  • 1
    The conditional where you determine if `x` is odd or even should be in the recursive function, not in the code that invokes it. – Sergey Kalinichenko May 06 '22 at 17:11
  • 3
    Turn your recursion into an iteration, and you shall see fewer segfaults. – j6t May 06 '22 at 17:12
  • 2
    BTW: `(unsigned long long int)pow(10, 9)` is not necessarily `1000000000` ... may very well be `999999999`. I suggest you write `unsigned long long L = 1000000007ULL;` – pmg May 06 '22 at 17:13
  • 1
    There's [exponentiation by squaring](https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int), which you can easily adapt to [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic). – M Oehm May 06 '22 at 17:55
  • Do you have to use recursion? Will loop work for you? – fukanchik May 06 '22 at 17:56
  • @Oehm: won't that be the Barrett algorithm? :) – Seva Alekseyev May 06 '22 at 19:35
  • The segfault is probably a stack overflow because your k is too large. Either make it tail recursive or itterative. And watch https://www.youtube.com/watch?v=cbGB__V8MNk for a better algorithm. – Goswin von Brederlow May 06 '22 at 20:56

2 Answers2

2

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 log2k steps, rather than k steps.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
0

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.
Deepak Tatyaji Ahire
  • 4,883
  • 2
  • 13
  • 35