Convert really large decimal string to hex?

Question

I've got a really large decimal number in an NSString, which is too large to fit into any variable including NSDecimal. I was doing the math manually, but if I can't fit the number into a variable then I can't be dividing it. So what would be a good way to convert the string?

Example Input: 423723487924398723478243789243879243978234

Output: 4DD361F5A772159224CE9EB0C215D2915FA

I was looking at the first answer here, but it's in C# and I don't know it's objective C equivalent.

Does anyone have any ideas that don't involve using an external library?

Answer 1

If this is all you need, it's not too hard to implement, especially if you're willing to use Objective-C++. By using Objective-C++, you can use a vector to manage memory, which simplifies the code.

Here's the interface we'll implement:

// NSString+BigDecimalToHex.h
@interface NSString (BigDecimalToHex)
- (NSString *)hexStringFromDecimalString;
@end

To implement it, we'll represent an arbitrary-precision non-negative integer as a vector of base-65536 digits:

// NSString+BigDecimalToHex.mm
#import "NSString+BigDecimalToHex.h"
#import <vector>

// index 0 is the least significant digit
typedef std::vector<uint16_t> BigInt;

The "hard" part is to multiply a BigInt by 10 and add a single decimal digit to it. We can very easily implement this as long multiplication with a preloaded carry:

static void insertDecimalDigit(BigInt &b, uint16_t decimalDigit) {
    uint32_t carry = decimalDigit;
    for (size_t i = 0; i < b.size(); ++i) {
        uint32_t product = b[i] * (uint32_t)10 + carry;
        b[i] = (uint16_t)product;
        carry = product >> 16;
    }
    if (carry > 0) {
        b.push_back(carry);
    }
}

With that helper method, we're ready to implement the interface. First, we need to convert the decimal digit string to a BigInt by calling the helper method once for each decimal digit:

- (NSString *)hexStringFromDecimalString {
    NSUInteger length = self.length;
    unichar decimalCharacters[length];
    [self getCharacters:decimalCharacters range:NSMakeRange(0, length)];
    BigInt b;
    for (NSUInteger i = 0; i < length; ++i) {
        insertDecimalDigit(b, decimalCharacters[i] - '0');
    }

If the input string is empty, or all zeros, then b is empty. We need to check for that:

    if (b.size() == 0) {
        return @"0";
    }

Now we need to convert b to a hex digit string. The most significant digit of b is at the highest index. To avoid leading zeros, we'll handle that digit specially:

    NSMutableString *hexString = [NSMutableString stringWithFormat:@"%X", b.back()];

Then we convert each remaining base-65536 digit to four hex digits, in order from most significant to least significant:

    for (ssize_t i = b.size() - 2; i >= 0; --i) {
        [hexString appendFormat:@"%04X", b[i]];
    }

And then we're done:

    return hexString;
}

You can find my full test program (to run as a Mac command-line program) in this gist.