### Performance Optimization

What optimizations can be done so that this code runs much faster for the following input? This version takes > 20s, about 26s on my machine.

1
18 1999999871

 ``1234567891011121314151617181920212223242526272829303132`` ``````#include using namespace std; int main() { int t,c,p,temp,x,y,ct,flag; cin>>t; int result; for(int i=0; i>c>>p; flag = 0; ct=-1; x=0; y=1; while(++ct < p-1){ temp = x+y; if(ct && !x && y == 1 && temp == 1) break; if (x == c){ flag = 1; result = ct; break; } x = y; y = temp%p; } if(!flag) result = -1; } cout<
Last edited on
What is it and what should it do?
Its from codechef.com, I'm eager to learn different approaches. I came up with this after a lot of tries but still the performance is slow.

It is required to find the minimum n such that Fn % p = c.
Fn is the nth fibonacci term, ct is n in this code.
Range of c, 0 ≤ c ≤ p-1
p is a prime number <2000000000 and also p % 10 is guaranteed to be a perfect square. Can this property be used in any way to optimize instead of just brute-forcing?
Last edited on
Thanks.
I observed the results of mod p on Fibonacci series and noticed that they repeat themselves after a certain count (the count most of the times being p-1) and so wrote this code but it still isn't optimal, for the prime 1999999871 it loops until 1999999870.
Does p%10 being a perfect square help??
1) you are doing it all wrong.
From equation Fn % p = c → Fn = x·p + c where x ∈ N

From numbers less than p you need to check only c itself. Next one will be p+c, then 2·p+c etc.
You might want for each t = x·p + c to check if it is a fibonacci number using known formulas, calculate n of said number using other formulas and output that number.
Thanks, I will try that.
Topic archived. No new replies allowed.