How much does $(f \circ f)(x)=x^2 - x + 1$ determine $f$?

Here is a different construction principle that produces a continuous solution $f$ on $X:={\mathbb R}_{\geq3}$. Put $a_0:=3$, $b_0:=5$, and define recursively $$a_{k+1}:=g(a_k),\quad b_{k+1}:=g(b_k)\qquad(k\geq0)\ .$$ In this way we obtain two intertwined sequences $$(a_0,b_0,a_1,b_1,a_2,b_2,\ldots)=(3,5,7,21,43,421,1807, 176\,821,\ldots)\ .$$ Let $$I_k:=[a_k,b_k],\quad J_k:=[b_k,a_{k+1}]\qquad(k\geq0)\ .$$ These are consecutive intervals sharing only endpoints; together they form a partition of $X$. Furthermore $$g(I_k)=I_{k+1},\quad g(J_k)=J_{k+1}\qquad(k\geq0)\ .$$ The function $$f_0(x):=x+2\quad(x\in I_0)$$ maps $I_0$ bijectively onto $J_0$. We now define the function $f:\>X\to{\mathbb R}$ as follows: $$f(x):=\left\{\eqalign{&g^k\circ f_0\circ g^{-k}(x)\qquad(x\in I_k,\ k\geq0)\cr &g^{k+1}\circ f_0^{-1}\circ g^{-k}(x)\qquad(x\in J_k, \ k\geq0)\ .\cr}\right.$$ This $f$ maps each $I_k$ onto $J_k$ and each $J_k$ onto $I_{k+1}$. Furthermore it is easy to check that $f\circ f=g$ on $X$.

Choosing $f_0$ more carefully makes the resulting $f$ even continuously differentiable.