I can't understand the wording

[TheIdeasMan]

@ne555

Thanks for your reply.

The formula is interesting, but I am having trouble understanding how to apply it here.

If a and b are out last 2 fib numbers, then we can use the equation to calculate the answer for the next fib number. It's trivial to utilise BigInt Library so there is a limit to the values a and b can have while using unsigned 64bit int say. So how to do this by only using the fib numbers up to the limit?

you need to store all the fib sequence for each possible modulo.

I didn't understand that part, explanation of that is probably key to the solution you had in mind, I guess.

I'd rather learn to indent.

But that causes the problem, or at least makes it hard to see. With this contrived code, the indenting conveys the intention, but hides the problem:

for (int a = 0; a < 10;  ++a)
     std::cout << a << " \n";
     std::cout << a  * 2<< " \n";
     std::cout << a  * 3 << " \n";
     std::cout << a  * 4 << " \n";

So that's why I like to indent and always use braces :+)

Regards, and hopefully everything is going well at your end :+D

[ne555]

The solution of the problem was on the form fibonacci(n+1) % m
The problem was that the sequence grows quite fast and overflows an integer.

In order to avoid that, you don't compute the fibonacci sequence and then extract its module, instead you compute the sequence with the module already applied.
That way you'll never overflow.
fib_mod[K] = (fib_mod[K-1]+fib_mod[K-2]) % module

Now, you said that computing the sequence for each case was a waste and that you could memorize it. But as you need to compute it with different module, I thought that you'll need to store several sequences (by instance, for 2, 4, 32). That was a mistake on my part.

Because the modules are on the form 1<<m, so you could store only for the biggest one (m=30)

fib_m = fibonacci_module(30e3, 1<<30)
fib_m[steps]%module

By the way, http://www.cut-the-knot.org/arithmetic/algebra/FibonacciMatrix.shtml


> But that causes the problem, or at least makes it hard to see.
When you learn to indent, you learn that you are not to be trusted with it ;)
Use a program to do the indenting (by instance clang-format)

[Winsu]

Thanks!!!

I have reading the suggestions I have achieved to get always a good output from the program..but the velocity is not good enough yet....I guess storing a fibonacci serie with 1<<30 module would be a good idea if after that I'm able to operate those numbers with other modules.....for example with N rungs in my ladder I have a fibonnacci already done at its value is fibonacci[N+1] for 1<<30...but in this case I need that number for 1<<25...I don't know how I could operate to get the number with module 1<<25 and if there is a risk of overflow while I'm operating on them...

[Winsu]

This is an optimal solution...but in python

def solution(A, B):
    limit    = max(A)                 # The possible largest N rungs
    result   = [0] * len(A)           # The result for each query
    modLimit = (1 << max(B)) - 1      # To avoid big interger in fibs
 
    # Compute the Fibonacci numbers for later use
    fib    = [0] * (limit+2)
    fib[1] = 1
    for i in xrange(2, limit + 2):
        fib[i] = (fib[i - 1] + fib[i - 2]) & modLimit
 
    for i in xrange(len(A)):
        # To climb to A[i] rungs, you could either
        # come from A[i]-1 with an one-step jump
        # OR come from A[i]-2 with a two-step jump
        # So from A[i] rungs, the number of different ways of climbing
        # to the top of the ladder is the Fibonacci number at position
        # A[i] + 1
        result[i] = fib[A[i]+1] & ((1<<B[i])-1)
 
    return result

[Winsu]

I have found the code for C++, it deduces the result with and operator...but I don't know how it does...I understand that 1<<5 would be something like 100000b and then if I apply an and operation I'm going to lose information.. I'm not sure what happens when for example 1100 & 11 it's 1100 or 0000....and aswell the code apply twice the and operation...I leave it below:

const int M = (1 << 30) - 1;  
vector<int> solution(vector<int> &A, vector<int> &B) {  
    // write your code in C++98  
      
    int m = 0;  
    for (int i = 0; i < A.size(); ++i) {  
        m = max(m, A[i]);  
    }  
    vector<int> f;  
    f.resize(m + 1);  
    f[0] = f[1] = 1;  
    for (int i = 2; i <= m; ++i) {  
        f[i] = (f[i - 1] + f[i - 2]) & M;  
    }  
    vector<int> answer;  
    for (int i = 0; i < A.size(); ++i) {  
        answer.push_back(f[A[i]] & ((1 << B[i]) - 1));  
    }  
    return answer;  
}  

The source of the problem is : http://ask.idehub.cn/article/283

But it's in Chinese so unless you are or you know Chinese...

[ne555]

> .I guess storing a fibonacci serie with 1<<30 module would be a good idea if after that I'm able to operate those numbers with other modules
yes, you can.
But this is only because of the relationships between the possible modules.
Note that a=1<<(m+k) is a multiple of b=1<<m, that means that if `a' divides exactly a number, the same can be said about `b'.

So if you do (x%a) % b, that would be the same as doing x%b
So you can simply store the fibonacci sequence for module (1<<30) and then compute the module that you actually need.


That's what the codes that you have posted do. They just perform one extra "optimization".
Because the modules are powers of 2, doing x & ((1<<m)-1) is the same that x%(1<<m)
Basically, in this particular case, the & operation would discard everything except the last `m' bits.

[Winsu]

I get what you mean ne555...It's working at 100% of performance...

#include <iostream>
#include <vector>

using namespace std;


vector<int> fibonacci(int A){
	vector<int> fibo;
	
	fibo.push_back(0);
	fibo.push_back(1);
	for(int i = 2;i <= A+1;++i){
		fibo.push_back((fibo[i-1]+fibo[i-2]) % (1<<30));
	}
	return fibo;
}

vector<int> solution(vector<int> &A, vector<int> &B){
	vector<int>::iterator itA;
	int maxA = 0;
	for(itA = A.begin();itA != A.end();itA++){
		if(maxA<*itA) maxA = *itA;
	}
	vector<int> fibo = fibonacci(maxA);
	int len = A.size()-1;
	vector<int> result;
	
	for(int i = 0;i<= len;i++){
		
		result.push_back(fibo[A[i]+1] % (1<<B[i]));
	}
	
	return result;
	
	
}