This SO Q&A provides some guru-level bit fiddles to sum two “packed” BCD values.

Extending those to use uint64_t variables, two 16 digit (decimal) values can be summed and easily output.

(That’s up to $99,999,999,999,999.99 for fixed-point currency calcs.)

With its carry-in and carry-out, stacking several BCD ‘buffers’ means the sky’s the limit for values used.

This Code Review question introduces some activities using Fibonacci numbers (integers).

Using the efficient BCD summing provided by the SO Q&A, one can generate an appreciable number of Fibonacci numbers up to 16 digits long. Using binary, a "%lld with an ordinary uint64_t and built in summing, a program can almost touch ULONGLONG_MAX before topping out. (Some with exceptional hardware might even reach higher with uint128_t.) ‘Stacking’ (or ‘concatenating’) several BCD buffers exceeds even those finite ceilings.

And, there are libraries available that efficiently deal with unbounded numbers…

But where’s the fun in that?

This afternoon, I sat down and hacked a skeletal BCD subtraction routine involving some operations and what feels like too much looping as it deals, right-to-left, with each pairs of digits.
The reference materials I could find (involving “nine’s complement”) all indicated that each digit of the result (the difference) must be examined and possibly tweaked. I chose to go the simple route of both subtracting AND tweaking in one pass as the resulting value (and “borrow out”) is assembled.

#include <stdio.h>
#include <stdint.h>

uint16_t sub( uint16_t m, uint16_t n, uint16_t *boro ) { // m - n - boro => res
    uint16_t res = 0;

    for( int i = 0; i < 16; i += 4, m >>= 4, n >>= 4 ) {
        int dif = (m&0xf) - (n&0xf) - *boro; // diff these two dgts (and boro)
        *boro = dif < 0; // negative? need to borrow?
        dif += "12"[*boro]; // +0 or +10
        res |= dif << i; // poke hex dgt into position
    }

    return res;
}

typedef union {
    uint32_t x32;
    uint16_t x16[2];
} hval;

int main( void ) {
    hval m; m.x32 = 0x37130048; // minuend
    hval n; n.x32 = 0x04540049; // subtrahend (always smaller value)
    hval r; // difference

    uint16_t boro = 0;
    r.x16[0] = sub( m.x16[0], n.x16[0], &boro ); // lo 4 digits (with borrow in/out)
    r.x16[1] = sub( m.x16[1], n.x16[1], &boro ); // hi 4 digits (with borrow in/out)

    printf( "%x - %x = %xn", m.x32, n.x32, r.x32 );
}

Output

37130048 - 4540049 = 32589999

This code works as well as it does.

The business with the union is a simple case study that I’d like to eventually expand to be arrays of ‘n’ 16 digit BCD values (currently working up to the 308th Fibonacci number with its 64 digits of length).

...
3987795824799770715342824788687062628452272409956636682999616408  #307
6452389184720949856740872794933738025334109298792472139250504213  #308

Subtraction of massive numbers is a necessary operation for finding the Zeckendorf Sequence of any single massive number, thus this developmental bit of coding BCD subtraction.

Objective

I am hoping that someone may be able provide a much more efficient way (a ‘bit hack’ solution) to subtract one smaller, multi-segment, packed BCD value from a larger value. Not concerned about differences less than zero (negative results) at this time.

PS: the literature mentions some hardware provides BCD opcodes (built into the silicon).

I’m interested in an algorithmic software solution; not buying a VAX to fulfill this hobby project.