I made some code about "integer interpolation" for running approximate alpha blending at FPGA which have low quantities of logic gate. Let's refer to "II" as integer interpolation.

"II" made applying Russian peasant algorithm.

The different point of Russian peasant between "II", Russian peasant is algorithm for multiply but
"II" is algorithm for calculate interpolated 8bit integer using another 8bit integer ratio.

There is two 8 bit integer. "Source" what I want to interpolation and "Ratio" which work like 0 ~ 1 floating point range.

If Source is 200 and Ratio is 127(a.k.a 0.5), result is 100.
If Source is 200 and Ratio is 191(a.k.a 0.75), result is 150.

Let's explain "II" algorithm step by step.

enter image description here

Each step Source shifting to right direction, Ratio shifting to left direction.
if Ratio MSB is HIGH, Source add to result with Correction.
Correction is LSB bit which underflowed of Source by shifting right direction.
These task keep going until Ratio is 0.

And we can implement interpolate A between B like this.

result = II(A, ratio) + II(B, 255 - ratio)

The result of using II is like this.
enter image description here
You can see something stripe on image.
And you may guess reason from this graph.
enter image description here

I think this algorithm can implement in one tick of clock.
but if somewhere more better ways exist?
Even if not, I want you debate this topic.

Thank you.

  • $\begingroup$ What exactly is your question? What counts as 'better'? Better by what metric? What is the best algorithm you know so far? I don't understand what the sentence ""II" made applying Russian peasant algorithm." means. $\endgroup$
    – D.W.
    Commented Nov 26, 2023 at 6:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.