Writing $\beta^3$-1 as a linear combinations of finite degrees of $\beta$

Question

I want to implement $\beta^3-1$ as hardware and I don't have negative numbers, so I need to write $\beta^3-1$ as linear combination of different degrees of $\beta$ (finite numbers of $1 \beta \beta^2 \beta^3 ...)$. Is there any way to do this?

Answer 1

You can first write $\beta^3-1 = (\beta-1)(\beta^2+\beta+1)$

Then calculate $\beta^2+\beta+1$.

The fast-to-implement uncomplicated way would now be ($O(\beta)$ complexity):

sum = beta2+beta+1;
for(int i=1;i<beta;i++)
   ack+=sum;

The -1 will switch the sign of the last bit, until it first becomes 1. So that would invite for a potential $O(\log(\beta))$ algorithm by keeping track of bits in a bit-shift loop, but that is probably over-course.

---

EDIT:

For the over-course approach with $O(\log( \beta))$ complexity you can read this question I just stumbled upon.