Алгоритм умножения с фиксированной точкой

Я ' m пытается изменить масштаб метки времени (только дробная часть секунд) с наносекунд (единицы 10 ^ -9 секунд) до нижней половины метки времени NTP (единицы 2 ^ -32 секунды). Фактически это означает умножение на 4,2949673. Но мне нужно делать это без математики с плавающей запятой и без использования целых чисел больше 32 бит (на самом деле я пишу это для 8-битного микроконтроллера, поэтому даже 32-битная математика стоит дорого, особенно деления).

Я придумал несколько алгоритмов, которые работают достаточно хорошо, но у меня нет никакого реального опыта работы с численными методами, поэтому я буду признателен за любые предложения, как их улучшить, или любые другие алгоритмы, которые могут быть более точным и / или быстрым.

Алгоритм 1

uint32_t intts = (ns >> 16) * 281474 + (ns << 16) / 15259 + ns / 67078;

Первые две константы были выбраны так, чтобы слегка недооценивать, а не выходить за рамки правильного значения, и последний множитель 67078 был определен эмпирически, чтобы исправить это. Дает результаты в пределах +/- 4 единиц NTP от правильного значения, что составляет +/- 1 нс - приемлемо, но остаточные изменения составляют нс . Думаю, я мог бы добавить еще один член.

Алгоритм 2

uint32_t ns2 = (2 * ns) + 1;
uint32_t intts = (ns2 << 1)
  + (ns2 >> 3) + (ns2 >> 6) + (ns2 >> 8) + (ns2 >> 9) + (ns2 >> 10)
  + (ns2 >> 16) + (ns2 >> 18) + (ns2 >> 19) + (ns2 >> 20) + (ns2 >> 21)
  + (ns2 >> 22) + (ns2 >> 24) + (ns2 >> 30) + 3;

На основе двоичного расширения 4,2949673 (фактически на основе двоичного расширения 2,14748365, поскольку я начинаю с удвоения и добавления единицы для округления). Возможно, быстрее, чем алгоритм 1 (я еще не прошел тесты). +3 был определен эмпирически, чтобы компенсировать недоработку из-за усечения всех этих младших битов, но это не дает наилучшего результата.