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?

  • $\begingroup$ One factorization is $(\beta-1)(\beta^2+\beta+1)$, but it is not exactly a linear combination. But if you already have up to $(.)^2$ stored maybe it would be fast. $\endgroup$ – mathreadler Mar 5 '17 at 15:21
  • $\begingroup$ The problem is that I can't implement minus so I can't implement $\beta -1$ $\endgroup$ – user137927 Mar 5 '17 at 15:22
  • $\begingroup$ Ah. How typical. Well you could just make a loop adding up $\beta-1$ times by setting the lower end of the loop to 1 higher. $\endgroup$ – mathreadler Mar 5 '17 at 15:23

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++)

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.