nancygold's Journal

Conveting integers to BCD
As part of the b4 project, I researched if binary numbers can be efficiently converted to BCD.
BCDs were a big thing at the dawn of computing, where everything was on perfocards, but people had to input decimals.

In fact, they did computing directly in BCDs and invented encodings allowing for efficient subtraction.
https://en.wikipedia.org/wiki/Excess-3#Motivation

My own attempt resulted in using a precomputed exp10 table

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>


uint32_t e10[] = {
/* 0*/ 0,
/* 1*/ 10,
/* 2*/ 100,
/* 3*/ 1000,
/* 4*/ 10000,
/* 5*/ 100000,
/* 6*/ 1000000,
/* 7*/ 10000000,
/* 8*/ 100000000,
/* 9*/ 1000000000
};

void p10(uint32_t r) {
  uint32_t q;
  int i = 9;
  for (; e10[i]>r; i--); //skip leading 0s
  for (; i; i--) {
    uint32_t e = e10[i];
    for (q = 0; r >= e; ++q) r -= e;
    putchar('0'+q);
  }
  putchar('0'+r);
  putchar('\n');
}

While looking for a smarter solution, I stumbled upon Arduino people brainstorming a divmod10 routine:
https://forum.arduino.cc/t/divmod10-a-fast-replacement-for-10-and-10-unsigned/163586/55

Which they use solely for printing numbers (i.e. timers for bomb detonators).

Good compilers generating code for the targets without fast division, usually supply a custom inline routine div_by(N) for every N encounter.
It can be made even more efficient if the input range is known.
I think there was an algorithm for generate these div_by(N) closures.
Akin to a perfect hash generation.
But GCC apparently doesn't do. So much for 40 years of open source!

Current Mood: amused