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=BP0000003;
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).
CodePudding user response:
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:
- Dynamic programming.
- Using loop.
- Come up with some formula to get answer in single iteration.
CodePudding user response:
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.