2
$\begingroup$

I would like to know which is the form of the primitive recursive function that gives the i-th digit of the binary expression of a given number.

$\endgroup$
  • $\begingroup$ By $i$-th digit do you mean the i-th digit where the first digit is the least significant digit? I.e. the i-th digit from the right when we write it as a binary number? Also, can you already assume some basic functions to be primitive recursive, such as multiplication or any constant functions? $\endgroup$ – Bram28 May 29 '17 at 0:07
  • $\begingroup$ Yes, that's right. We consider that digit you spell and the functions you seem to need. $\endgroup$ – gibarian May 29 '17 at 0:11
  • $\begingroup$ Did you already show multiplication to be primitive recursive? And any constant functions? $\endgroup$ – Bram28 May 29 '17 at 0:12
3
$\begingroup$

OK, I assume you have already shown the quotient (quo) and remainder (rem) functions to be primtive recursive. Then what you want can be done as follows:

$binarydigit(n,i)=helpbinarydigit(n,i-1)$

$helpbinarydigit(n,0)= rem(n,2)$

$helpbinarydigit(n,i+1)=\begin{cases} helpbinarydigit(quo(n,2),i) & \text{if } rem(n,2)=0\\ helpbinarydigit(quo(n-1,2),i) & \text{if } rem(n,2)=1 \end{cases}$

Explanation:

You keep dividing $n$ by $2$, until you get to the right digit. As you divide by $2$, if the remainder is $1$, the first subtract $1$ before dividing by $2$. As such, you will in effect keep removing the least significant digit from the number in binary representation, until you get to the digit you want.

$\endgroup$

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.