4

I want to access certain parts of a big integer. In particular, I want to divide the big integer into 4 equal parts. If the bit length is not divisible by 4, I want enough leading zeros added to make the length a multiple of 4. I have the following code that works as described:

public static BigInteger[] partition(BigInteger a) { int base = (a.bitLength()+3)/4; BigInteger upper = a.shiftRight(2*base); BigInteger lower = a.subtract(upper.shiftLeft(2*base)); BigInteger a2 = lower.shiftRight(base); BigInteger a1 = lower.subtract(a2.shiftLeft(base)); BigInteger a4 = upper.shiftRight(base); BigInteger a3 = upper.subtract(a4.shiftLeft(base)); return new BigInteger[] {a1, a2, a3, a4}; }

The problem with this code is the overhead of creating many additional big integers as well as many unnecessary shifts and subtracts. Perhaps a test can be added to make sure that a has at least 4 bits, but that is not necessary in my case since I know that to be true before calling the function.

Is there a way to extend the BigInteger class and work with the int[] mag array directly? The extended class should have something similar to partition given above where it returns an array of 4 immutable BigInteger values.

Improve this question

1 Answer 1

Reset to default
3

I do not quite get your problem in fact. Wish what I am answering make sense to you :) .

In BigInteger it does provide toByteArray() which returns a byte[] containing the 2-compliment representation of the BigInteger itself. On the same time there is a constructor taking byte[].

Therefore your solution can be as easy as getting the byte array, partition the byte array by whatever dirty way you want, and create each result BigInteger accordingly. This should save you from creating lots unnecessary BigIntegers as what you are concerning.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

The problem with what you say is the same as the code I posted. The byte array is a copy of the underlying int[] mag array beause the class is immutable. Is there a way to skip this additional copy operation and directly work with the underlying int[] mag array.
I think at least it save several temp objects as in your original code. Designed as a immutable object, working against the underlying int[] of the result BigInteger may not be that preferable. I'd rather reuse the temporary byte[] during your arithmetic, which further save temp obj (temp objs involved are the byte array returned from the original BigInteger, and the temp byte array you use for arithmetic for each result BigInteger)
After thinking long and hard about it, I've decided what I really need is a mutable big integer class. Given the limitations of the standard library, I agree with you that what you propose is likely the only reasonable solution. Since the boundary may fall in the middle of a byte, the implementation is not trivial and I may post my code. For now, I accept your answer. Thank you.
imho, the not-in-byte-boundary is not something hard to solve. My biggest concern on your work is more about negative number. Are you going to have 2-complient representation for negative number? And, your splitting logic is going to cause ambiguous result, for example: 1010101 and 1111 are going to give you same result. Is that really what you want?
No, no negative numbers. There is also no ambiguity. It is true that leading zeros in the three lower partitions disappear. But that is not a problem since the base is fixed. It is implied, but fixed.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.