2

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.

gibarian
  • 145
  • 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? – Bram28 May 29 '17 at 00:07
  • Yes, that's right. We consider that digit you spell and the functions you seem to need. – gibarian May 29 '17 at 00:11
  • Did you already show multiplication to be primitive recursive? And any constant functions? – Bram28 May 29 '17 at 00:12

1 Answers1

3

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118