Opened 3 years ago

Closed 3 years ago

# Implement function that returns the balanced digit representation of an integer

Reported by: Owned by: gh-sheareralexj minor sage-8.9 number theory Alex Shearer Bruno Grenet N/A a69b952 a69b95259043fa5b5b0faa1cb12c4bf6506fea3d

### Description

This ticket adds the balanced_digits function, returning the digit representation of an integer where the digits are centered at 0. For example, this enables:

```sage: 8.balanced_digits(3)
[-1, 0, 1]
```
```sage: 33.balanced_digits(6)
[3, -1, 1]
```

### comment:1 Changed 3 years ago by gh-sheareralexj

• Branch set to u/gh-sheareralexj/implement_function_that_returns_the_balanced_digit_representation_of_an_integer

### comment:2 Changed 3 years ago by gh-sheareralexj

• Status changed from new to needs_review

New commits:

 ​1a18b2b `28387: Added balanced_digits function`

### comment:3 Changed 3 years ago by bruno

• Reviewers set to Bruno Grenet
• Status changed from needs_review to needs_work

## Incorrect algorithm?

First, it is not clear to me (so the docstring should be adapted) what is the exact specification. I would say that the balanced base `b` uses `b` digits centered around zero. Thus if `b` is odd, there is only one possibility, namely digits between `-b//2` and `b//2` (both included). For instance in base 9, one uses digits from -4 to 4. If `b` is even, one has to choose between digits from `-b//2` to `b//2-1` or `-b//2+1` to `b//2` (base 10 for instance: either -5 to 4 or -4 to 5), and this is defined by the value of `positive_shift`. Is that we you have in mind? Note that in this case, your implementation has a problem:

```sage: n = -46
sage: n.balanced_digits(10) # correct
[4, -5]
sage: n.balanced_digits(10, positive_shift=True) # should be [4, 5, -1]
[4, -5]
```

I think that a correct algorithm (if my specification in the one you have in mind) would be easier to write using a "balanced `quo_rem`" that on input `a` and `b` returns `(q, r)` such that `a = b*q + r` with `-b//2 <= r <= b//2` (with the same subtleties for even bases). This could go as follows:

```def balanced_quo_rem(self, right, positive_shift=True):
q, r = self.quo_rem(right)
if r > right//2:
return (q+1, r-right)
if right % 2 == 0 and not positive_shift and r == right//2:
return (q+1, r-right)
return (q, r)
```

Then the algorithm could be implemented as (I just put the main idea):

```def balanced_digits(self, base, positive_shift=True):
digits = []
n = self
while n > 0:
q, r = n.balanced_quo_rem(base, positive_shift)
digits.append(r)
n = q
return digits
```

## Other remarks

Below, I indicate a few general comments on your current implementation (and the docstring, tests, etc.), though it should be changed anyway.

#### In the docstring

1. There should not be a blank line as first line;
2. It should be "Return" rather than "Returns" (as mentioned in the doc);
3. Following the doc also, I would put a blank line between the first sentence ("Return ... given base") and the rest of the specification;
4. I would write "Return the list of balanced digits" rather than "Return a list of balanced digit" (since there is uniqueness);
5. You should replace `b/2` by `b//2` in the docstring to indicate a floor division (if the base is odd);
6. Your `::` alone on a line should be replaced by `TESTS::`;
7. You should write a more precise specification more generally.

#### In the code itself

1. I think that having `base = 10` as default would be a good idea, to be consistent with `n.digits()` for instance (should be then mentioned in the doc obviously);
2. You may raise an `Exception` if the base is not an integer (and add an `EXAMPLE` for this). Something like:
```if isinstance(base, Integer):
_base = base
else:
try:
_base = Integer(base)
except TypeError:
raise ValueError('base should be an integer')
```
3. You should not use `floor(b/2)`, but rather `b//2`;
4. You may compute `self_abs` and `neg` as follows: `self_abs, neg = self.abs(), self.sign()`

### comment:4 Changed 3 years ago by bruno

Actually, there is another (simpler?) algorithm:

1. First compute the classical base `b` representation of the input integer `n`;
2. Scan the digits from low to high order, and if a digit `d` is larger than `b//2`, replace `d` by `d-b` and remove one to the next digit.

You still have to manage the subtlety for even bases but that's not a big deal. Also, the two-step algorithm I mention works for nonnegative integers. For negative integers, do the same with `abs(n)` and take the opposite of all digits. For even bases, you have to do it with `not positive shift`.

### comment:5 Changed 3 years ago by gh-sheareralexj

Thanks for reviewing, and thanks for finding the error! Yeah, it seems the issue is that the code is handling negatives incorrectly. Today I'll work at fixing this as well as implementing your other suggestions and algorithms.

Thanks!

### comment:6 Changed 3 years ago by git

• Commit changed from 1a18b2b5dc0fe0f3eeb9621ec1f16adc0e4fb02b to 714b193f9e225dd396c7f52f1791bca8df768ac2

Branch pushed to git repo; I updated commit sha1. New commits:

 ​714b193 `28387: Rewrote function and documentation to reflect changes as suggested in ticket`

### comment:7 Changed 3 years ago by gh-sheareralexj

I updated the code and used the documentation you suggested. I tested the runtime on all three algorithms and went with the last one (using the standard n.digits(b) function) as it worked fastest for large bases.

### comment:8 Changed 3 years ago by gh-sheareralexj

• Status changed from needs_work to needs_review

### comment:9 Changed 3 years ago by bruno

• Status changed from needs_review to needs_work

The new version is much better indeed! I still have a two remarks:

• The case `base = 2` is problematic. Depending on `positive_shift` it can only represent nonnegative or nonpositive integers. The simplest way to deal with it is probably to impose that `base > 2`.
• I would add some details in the docstring for the parameter `positive_shift`. In the block `INPUT`, you may write something like "For even bases, the representation uses digits from `-b//2 + 1` to `b//2` if set to True, and from `-b//2` to `b//2-1` otherwise. This has no effect for odd bases."

### comment:10 Changed 3 years ago by git

• Commit changed from 714b193f9e225dd396c7f52f1791bca8df768ac2 to a69b95259043fa5b5b0faa1cb12c4bf6506fea3d

Branch pushed to git repo; I updated commit sha1. New commits:

 ​427b4d7 `Merge branch 'u/gh-sheareralexj/implement_function_that_returns_the_balanced_digit_representation_of_an_integer' of git://trac.sagemath.org/sage into test_28387` ​a69b952 `28387: Added restriction on parameter, updated documentation`

### comment:11 Changed 3 years ago by gh-sheareralexj

• Status changed from needs_work to needs_review

Awesome, made those two edits. Thank you much.

### comment:12 Changed 3 years ago by bruno

• Status changed from needs_review to positive_review

That's fine for me!

A side note: It is usually not needed (nor advised) to merge new versions in a branch. As long as the merge automatically works¹, it is fine. The history is simpler to read if there aren't several merges.

¹ This is showed by the color of the link to the branch in the description: Green is OK, red is NOT OK, orange means NOT TESTED and you just need to click the link for trac to try the merge (and change the color accordingly).

### comment:13 Changed 3 years ago by vbraun

• Branch changed from u/gh-sheareralexj/implement_function_that_returns_the_balanced_digit_representation_of_an_integer to a69b95259043fa5b5b0faa1cb12c4bf6506fea3d
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.