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:  ghsheareralexj  Owned by:  

Priority:  minor  Milestone:  sage8.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: 
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
 Branch set to u/ghsheareralexj/implement_function_that_returns_the_balanced_digit_representation_of_an_integer
comment:2 Changed 3 years ago by
 Commit set to 1a18b2b5dc0fe0f3eeb9621ec1f16adc0e4fb02b
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 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//21
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, rright) if right % 2 == 0 and not positive_shift and r == right//2: return (q+1, rright) 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
 There should not be a blank line as first line;
 It should be "Return" rather than "Returns" (as mentioned in the doc);
 Following the doc also, I would put a blank line between the first sentence ("Return ... given base") and the rest of the specification;
 I would write "Return the list of balanced digits" rather than "Return a list of balanced digit" (since there is uniqueness);
 You should replace
b/2
byb//2
in the docstring to indicate a floor division (if the base is odd);  Your
::
alone on a line should be replaced byTESTS::
;  You should write a more precise specification more generally.
In the code itself
 I think that having
base = 10
as default would be a good idea, to be consistent withn.digits()
for instance (should be then mentioned in the doc obviously);  You may raise an
Exception
if the base is not an integer (and add anEXAMPLE
for this). Something like:if isinstance(base, Integer): _base = base else: try: _base = Integer(base) except TypeError: raise ValueError('base should be an integer')
 You should not use
floor(b/2)
, but ratherb//2
;  You may compute
self_abs
andneg
as follows:self_abs, neg = self.abs(), self.sign()
comment:4 Changed 3 years ago by
Actually, there is another (simpler?) algorithm:
 First compute the classical base
b
representation of the input integern
;  Scan the digits from low to high order, and if a digit
d
is larger thanb//2
, replaced
bydb
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 twostep 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
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
 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
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
 Status changed from needs_work to needs_review
comment:9 Changed 3 years ago by
 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 onpositive_shift
it can only represent nonnegative or nonpositive integers. The simplest way to deal with it is probably to impose thatbase > 2
.
 I would add some details in the docstring for the parameter
positive_shift
. In the blockINPUT
, you may write something like "For even bases, the representation uses digits fromb//2 + 1
tob//2
if set to True, and fromb//2
tob//21
otherwise. This has no effect for odd bases."
comment:10 Changed 3 years ago by
 Commit changed from 714b193f9e225dd396c7f52f1791bca8df768ac2 to a69b95259043fa5b5b0faa1cb12c4bf6506fea3d
Branch pushed to git repo; I updated commit sha1. New commits:
427b4d7  Merge branch 'u/ghsheareralexj/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
 Status changed from needs_work to needs_review
Awesome, made those two edits. Thank you much.
comment:12 Changed 3 years ago by
 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
 Branch changed from u/ghsheareralexj/implement_function_that_returns_the_balanced_digit_representation_of_an_integer to a69b95259043fa5b5b0faa1cb12c4bf6506fea3d
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
28387: Added balanced_digits function