1

Using the function $$f(x) = \begin{cases}\frac{x}{4} &\text{if }|x|\le 2\\[0.3em] \frac{|x| - 1}{x} & \text{otherwise}\end{cases}$$ one can map $\mathbf Q$ into the interval $[-1, 1]$ in a way amenable to binary search.

Suppose $x$ is the real number we want to represent as a binary search sequence. For the first term of the sequence, record 1 if $x$ is positive, $-1$ if $x$ is negative, 0 if $x$ is exactly 0: i.e., start in the middle of $[-1, 1]$, and figure out whether you need to move left or right. Then ask if $|x| > 2$: if so, then is $|x| > 4$? what about $|x| > 8$? keep doubling until the number is bounded above, and then subtract: is $|x| > 6$? keep narrowing the search down until it terminates... or doesn't.

This is in no way a standard way to record real numbers, so I prepared some examples.

$0 = (0)$

$1 = (1, -1, 0)$

$-1 = (-1, 1, 0)$

$2 = (1, 0)$

$27 = (1, 1, 1, 1, 1, -1, 1, -1, 1, 0)$

$40 = (1, 1, 1, 1, 1, 1, -1, -1, 0)$

$67 = (1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 0)$

$\pi = (1, 1, -1, 1, -1, -1, 1,\dots)$

Question: how do I add and multiply these sequences in a term-wise manner?

  • add and multiply by identifying the corresponding real number and then adding or multiplying as appropriate. – pancini Mar 30 '24 at 06:28
  • Perhaps you should try looking for a function that converts a given sequence to the corresponding real number – Soham Saha Mar 30 '24 at 06:30
  • I don't follow your method constructing such sequences. I understand that your first term determines sign, then a sequence of $1$s follow depending on how large the base $2$ logarithm of the number happens to be, followed by a $-1$ essentially to terminate this sequence. You then say "and then subtract". Subtract what? Does what you subtract depend on the number of $1$s that appeared previously? Could you talk us through precisely what calculations lead you to get the sequence for, say, $40$? – Theo Bendit Mar 30 '24 at 06:32
  • Sure: to get 40, 40 is positive (1), greater than 2 (1), greater than 4 (1), greater than 8 (1), greater than 16 (1), greater than 32 (1), less than 64 (-1), less than 48 (-1), but exactly 40 (0). Basically I'm taking successive midpoints on the interval [-1, 1], just as one does in ordinary binary search. – node196884 Mar 30 '24 at 06:35
  • Balanced ternary is not quite what you have, but seems closely related. 2. Advance warning: I am considering removing the constructive-mathematics tag, as the question doesn't seem to have much to do with constructive math specifically. Is there a reason you chose this tag, or some other reason to keep it around?
  • – Z. A. K. Mar 30 '24 at 06:58
  • i had no idea whether the tag was appropriate, but figured it was vaguely relevant. – node196884 Mar 30 '24 at 07:00