1
$\begingroup$

I have a very strange (arbitrary) problem that I have been trying to wrap my head around, but have been struggling to figure out how to accomplish this. I'll use Rust but in a pseudo-code fashion, these probably won't compile.

Background

The library function takes a &[u64] (a slice/array/list of unsigned, 64-bit integers) and produces a String (byte array of utf-8 data), so the contract looks something like this:

pub trait Translator {
    fn translate(numbers: &[u64]) -> String;
}

Usage would look something like this:

let a: u64 = 1;
let b: u64 = 2;
let translated: String = TranslatorImpl::translate(&[a, b]);

The translation is lossless, so the output stored in translated can be converted back into a &[u64] without any loss of data. The data representation is compact so that it uses as little output data as possible to represent the input. I'm of course aware of hash functions, but I need the output to be as compact as possible, and I do not need cryptographic levels of collision resistance.

Lacking sufficient documentation, I assumed originally that the purpose of accepting a &[u64] was in order to allow passing arbitrarily-sized integers beyond 64-bits. However, the actual implementation details are that the input forms a nested "tree" (without ever having more than one child, so perhaps a linked-list is a better description), but the library contract is that a collision is impossible such that &[x] cannot produce the same value as &[x, y]. It can essentially be thought of as a filesystem path, e.g. x/y/z.

This being the case, my original understanding was incorrect, but I'd still like to proceed to try to solve this challenge.

Problem

I'd like to be able to pass a u128 (unsigned, 128-bit integer) to the library, but to do so in a way where the sum of the values of the u64 array will equal the value of the 128-bit integer. I'd also like to be able to do this for any size of unsigned integer/any array of bytes. I can convert any integer in Rust to native/big/little-endian bytes, but I'll choose big-endian because it's typically used in networking. I'll also be using u8 and u16 (unsigned 8-bit/16-bit integers) in my example to prevent binary representations from being too long/difficult to read.

To make explaining this easier, here is a table of what binary values look like between u8 and u16:

Type Value (Base-10) Value (Binary)
u8 255 11111111
u16 255 00000000_11111111
u16 256 00000001_00000000
u16 257 00000010_00000000
u16 258 00000011_00000000

The max value, of course, that can be represented by a u8 is 11111111 in binary, 255 in base-10. If I have a u16 which is 255 + 1, i.e. just beyond what a u8 can represent, the binary pattern is 00000001_00000000, 255 + 2 is 00000010_00000000, etc.

If I were to try to split a u16 into two u8s which sum to the same value, the digit rotation clears all previous bits, as can be seen in the difference between 255u16 and 256u16. Solving this part of things is not very difficult, as I can basically do this:

let first_chunk: u8 = if value > 255 {
    255
} else {
    value as u8 // downcast because it can be represented as a u8
}

However, I have had an extremely difficult time trying to figure out how to get the remainder of this such that the second part remains accurate. I was originally trying to right bit-shift, but as per the table above, this clearly does not work, because the representation of 257 >> 8 (00000001) is not the same as a u8 of value 2 (00000010). Division/modulo also doesn't work, and I'm kind of struggling to figure out how to proceed. I do assume that achieving this is possible, but I'm at a loss to figure out exactly how.

Here are some test cases and a sample function which implements the interface described:

fn split_to_sum(value: u16) -> [u8; 2] {
    // TODO
}

#[test]
fn test_split_to_sum() {
    // NOTE the output representation should be such that if the input is
    //      greater than the chunk size, the first chunk should be a full
    //      bit pattern, and so on and so forth
    assert_eq!([255u8, 0u8], split_to_sum(255u16));
    assert_eq!([255u8, 1u8], split_to_sum(256u16));
    assert_eq!([255u8, 2u8], split_to_sum(257u16));
    assert_eq!([255u8, 3u8], split_to_sum(258u16));
}

How can I go about solving this, such that a larger unsigned integer is split into chunks of a smaller unsigned integer where the sum of the parts is equal to the original, larger-width integer?

TL;DR

Choose a size of unsigned integer, which we will call x_size. Next, choose a size of unsigned integer which is smaller than x_size and is divisible by x_size (this is always the case because of powers of two) which we will call y_size.

# size of x could be 128 bits, size of y could be 64 bits
assert x_size > y_size
# size of x must be divisible by size of y without a remainder
assert x_size % y_size = 0

Next, we will take an unsigned integer of size x_size named x. Take x and split it into parts of size y_size where the sum of each part equals the value of the original value of x.

EDIT: I have just realized that what I'm asking for is fundamentally impossible. Two unsigned 64-bit integers when summed together cannot represent the full space of an unsigned 128-bit integer. This should have been obvious to me, but I got lost in the details and just realized my mistake.

For example, let's assume we are splitting an unsigned 32-bit integer into two unsigned 16-bit integers. The max value that a unsigned 16-bit integer can fit is, of course 216. The max value of two 16-bit unsigned integers when summed together is 2 * 216, which only occupies 18 bits, so we cannot sum the split parts from two 16 bit integers into a 32 bit integer, we cannot represent a larger unsigned integer as the sum of two evenly-split parts.

I'm not sure why this didn't immediately stick out to me, because it seems pretty obvious now. The only way to split a larger integer into two parts is to simply split its actual bits.

$\endgroup$
4
  • 1
    $\begingroup$ That's a long post, and I'm lost by the details of the motivation. Can you state the problem in a self-contained way, without having to understand Rust or that particular library? A format that often works well is to list the inputs to the algorithm, and the desired output, and what properties the output must satisfy to qualify as correct (ideally, with mathematics and standard pseudocode-style notation). When you find yourself referring to "the u128 array" multiple times, it might be helpful to give it a name (e.g., $A$). $\endgroup$
    – D.W.
    Jan 13 at 7:31
  • $\begingroup$ @D.W. yes, I will update the post presently. $\endgroup$ Jan 15 at 0:06
  • $\begingroup$ Actually, in trying to summarize the problem, I have realized that what I'm looking to do is essentially not possible. I will update the question. $\endgroup$ Jan 15 at 0:11
  • $\begingroup$ The edit should not contain the answer, instead you should post your own answer. The answer is correct, you might want something like 2^64 * uint64 + uint64 instead to cover the full space of uint128. For example, to combine 999 with 999, you need 999*1000+999 = 999999. $\endgroup$ Jan 16 at 0:14

1 Answer 1

1
$\begingroup$

As requested, I am posting my edit to the question above as an answer:

I have just realized that what I'm asking for is fundamentally impossible. Two unsigned 64-bit integers when summed together cannot represent the full space of an unsigned 128-bit integer. This should have been obvious to me, but I got lost in the details and just realized my mistake.

For example, let's assume we are splitting an unsigned 32-bit integer into two unsigned 16-bit integers. The max value that a unsigned 16-bit integer can fit is, of course 216. The max value of two 16-bit unsigned integers when summed together is 2 * 216, which only occupies 18 bits, so we cannot sum the split parts from two 16 bit integers into a 32 bit integer, we cannot represent a larger unsigned integer as the sum of two evenly-split parts.

I'm not sure why this didn't immediately stick out to me, because it seems pretty obvious now. The only way to split a larger integer into two parts is to simply split its actual bits.

In essence, the only way to represent the full value of a u128 in binary is by using the full address space of 128 bits. It cannot be losslessly compressed into two u64s summed together.

For instance, we will calculate the maximum unsigned 64-bit and 128-bit integer values in Python:

# calculate the maximum value that a u128 can hold:
max_u128 = (2 ** 128) - 1
# calculate the maximum value that a u64 can hold:
max_u64 = (2 ** 64) - 1
# calculate the amount of u64s that, when summed, would equate the max
# value of a u128:
u64_count_for_u128 = max_u128 / max_u64
# display the ungodly number
print("{:f}".format(u64_count_for_u128)
# and here it is
assert 18446744073709551616.0 == u64_count_for_u128

To represent a u128 as a set of u64s which sum to the same value, you would need a set of 18,446,744,073,709,551,616.0 u64s. Thus, splitting a u128 into two u64s which sum to the same value is impossible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.