How hard is to invert the function that computes the middle-bits of (x^2)? I'm designing a function f that should be moderately hard to invert and very fast to evaluate in a modern CPU. The function will be used in a proof-of-work function.

I've read that the middle-bits of multiplication are the harder bits to obtain, so I suspect that they are the hardest to invert.

Let $f(x) = ((x^2) &gt;&gt; 16)$ where $x$ is 32-bits and $f(x)$ is truncated to 32-bts, and the multiplication is carried on a 64-bit architecture.

(alternatively one could use $f(x) = ((2^{32}-x-1)*x) &gt;&gt; 16 )$

Suppose that, since $f$ may not be bijective, any pre-image (if exists) is accepted.
Suppose also that there is no enough memory or time to precompute $f^{-1}$ for all possible $f(x)$ values (although there might be some memory/time to precompute a much smaller table)

Again, this is not a strict crypto question. In this context "hard" does not mean cryptographically hard. I'm asking approximately how hard it is, measured in number of instructions of a standard computer (with a standard instruction set). A bound on the number of any operation would be great.

I'm posting here because the question does not fit well in theoretical computer science not in programming stack-exchanges.

Maybe there is a paper that describes this?
This is probably not secure enough for a proof of work.  I'll outline some attacks, of increasing sophistication/complexity and increasing effectiveness (decreasing runtime).

Brute force

The obvious attack is brute force: enumerate all $2^{32}$ possible inputs and check to find the first that produces the desired output.  This takes $2^{32}$ time.  I'm sure you already knew about this attack, and based on your question, it sounds like this is acceptable in your application.

Time-space tradeoff

You can use Hellman's time-space tradeoffs (or rainbow tables, the hyped-up version of that) to solve preimages.  You have to do a $2^{32}$-step precomputation to build up the table.  The table is of size about $2^{22}$.  After you've built up the table, you can find a preimage of $f(x)$ in about $2^{22}$ steps of computation.

Thus, after a one-time precomputation that probably takes a few minutes or at most hours, you can invert the function in a few seconds, using a few tens of megabytes of storage.

Guess the high bits and take a square root in the integers

There's a cleverer attack, which will find the preimage using at most $2^{16}$ simple steps of arithmetic (often quite a bit faster).  This will probably run in much less than a second, maybe at little as milliseconds to find a preimage.

We can write any 64-bit integer in the form $\alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma$, where $\alpha$ is a 16-bit integer, $\beta$ a 32-bit integer, and $\gamma$ a 16-bit integer (i.e., $0 \le \alpha,\gamma &lt; 2^{16}$ and $0 \le \beta &lt; 2^{32}$).  Now we don't know the value of $x^2$, but $x^2$ is a 64-bit integer and we know its middle bits, so we can write it in the form

$$x^2 = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma$$

where we know $\beta$ ($\beta$ is just the output of your hash function) but we don't know $\alpha,\gamma$.

Now iterate over all possible values of $\alpha$.  For each guess at $\alpha$, form the value

$$y = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + 2^{16}-1,$$

take the square root of $y$ in the integers, and round down to an integer.  Let $x'$ denote the result, i.e., $x' = \lfloor \sqrt{y} \rfloor$.  Then check whether $x'$ is the desired preimage, i.e., whether $f(x') = \beta$.

I claim that this attack requires at most $2^{16}$ steps.  There are only $2^{16}$ possible values of $\alpha$, so we do at most $2^{16}$ iterations.  Moreover, in the iteration where we've guessed the value of $\alpha$ correctly, I claim we will successfully recover the preimage $x$.  Let me explain why.  First, the 64-bit integer $y$ will be very close to the 64-bit integer $x^2$: $y - x^2 &lt; 2^{16}$.  Therefore, when you take the square-root, $\sqrt{y}$ will be very close to $\sqrt{x^2}=x$.  How close?  Well, notice that $(x+1)^2 \approx x^2 + 2x + 1$, so for 32-bit values of $x$, consecutive squares will be about $2^{32}$ apart from each other.  That's much larger than the gap between $y$ and $x^2$, so $y$ will be much closer to $x^2$ than to $(x-1)^2$ or $(x+1)^2$.  Thus, taking the square root of $y$ and rounding to the nearest integer will return $x$, not $x-1$ or $x+1$ or anything else (unless $x$ is extremely small, say $x &lt; 2^{14}$, which has very low probability and thus can be ignored).

This means that this attack is guaranteed to succeed after at most $2^{16}$ iterations.

It turns out that not all values of $\alpha$ are equally likely; when $x$ is uniformly distributed, the upper 16 bits of $x^2$ are biased towards small values.  Therefore, if you iterate over all values of $\alpha$ in the sequence $0,1,2,3,\dots,2^{16}-1$, you are unusually likely to succeed early.  The average number of iterations until success is $2^{16}/3$, so the attack is about $3\times$ faster than you might expect based upon a worst-case analysis.