Opened 3 years ago

Closed 3 years ago

#28387 closed enhancement (fixed)

Implement function that returns the balanced digit representation of an integer

Reported by: gh-sheareralexj Owned by:
Priority: minor Milestone: sage-8.9
Component: number theory Keywords:
Cc: Merged in:
Authors: Alex Shearer Reviewers: Bruno Grenet
Report Upstream: N/A Work issues:
Branch: a69b952 (Commits, GitHub, GitLab) Commit: a69b95259043fa5b5b0faa1cb12c4bf6506fea3d
Dependencies: Stopgaps:

Status badges

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]

Change History (13)

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

  • Commit set to 1a18b2b5dc0fe0f3eeb9621ec1f16adc0e4fb02b
  • Status changed from new to needs_review

New commits:

1a18b2b28387: 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

That's a good idea to add this. I've a few comments on your implementation though.

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:

714b19328387: 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:

427b4d7Merge branch 'u/gh-sheareralexj/implement_function_that_returns_the_balanced_digit_representation_of_an_integer' of git://trac.sagemath.org/sage into test_28387
a69b95228387: 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.