Recently I was trying some problems related to XOR operation, And I found this problem somewhere(Can't find out now), there is a function defined like this,
$f(i,j)$ = $1$ if i=$0$ or j = $0$
$f(i,j)$ = $f(i-1,j)$ $XOR$ $f(i,j-1)$ else
And we have to calculate $f(i,j)$ for really big numbers which can not be solved by just iteration. Can consider $i,j$ <= $10^{15}$
My Effort:
I was trying to observe something in terms of patterns, that I formed after printing matrix by just iterating over $i$ and $j$, for $20*20$ matrix. I found that it's forming inverted triangles in kind of nested form and of size $2^n-1$, but I still don't know how could I formulate or find a better way to calculate this function in lesser complexity than $O(i*j)$. I am expecting some logarithmic complexity which I am assuming is possible because of above patterns.
Note that $a\mathbin{\sf xor}b = a+b \bmod 2$ when $a,b\in\{0,1\}$. So your matrix is Pascal's triangle modulo 2: $$ f(i,j) = \binom{i+j}{i} \bmod 2 $$
So in order to calculate it, you just need to be able to find out whether $\binom{m}{n} = \frac{m!}{(m-n)!n!} $ is even or odd. You can do that by computing how many factors of $2$ there are in each of the factorials and checking if there are as many in the denominator as in the numerator.
For counting factors of $2$ in a factorial, see Highest power of a prime $p$ dividing $n!$.