Задача с погрешностью и переполнением

[firefish]

Ну от этого:

private int getMillis(int ticks) {
        return (ticks >> 5) - 3*(ticks >> 12);
}

к этому:

private int getMillis(int ticks) {
        return (ticks - (ticks >> 7) - (ticks >> 6)) >> 5;
}

без особых усилий можно было перейти. Точность наверное меньше, чем в окончательном варианте, но больше чем у исходной реализации.

[mgn]

Тоже сразу пришел в голову такой вариант. Дабы оценить точность методов посчитал среднее отклонение от Math.Round() по всему диапазону:
— первый метод — 1.09
— последний метод автора — 0.00012

А этот метод со сдвигом в конце — 0.43

[mkal]

Надо сравнивать не с Round, а с Floor.

Для Round будет формула

( triks — 3 * ( triks >> 7 ) + ( 1 << 4 ) ) >> 5

[Mrrl]

А чем плохо такое решение?

        static int div(int x) {
            int x1=x>>12,x2=x&0xFFF;
            return x1*125+((x2*125+0x800)>>12);
        }

Проверил до 10^9 — ошибок по сравнению с (x*1000+0x4000)>>15 (вычисленному в 64-битных числах) нет.

[knekrasov]

Не проверял, но выглядит круто!
Не подскажете, откуда берутся магические числа 125 и 0x800?

[Ekstazi]

Мне тоже интересно откуда!

[VolCh]

1<<12 = 4096
4096*125=32.768=32768/1000
0x800 = 4096/2

[Mrrl]

Точнее, 4096/125=32.768

Теперь более полно.
Нам нужно вычислить
m=Round(x*1000/32768)=Floor(x*125/4096+0.5)
(сократили дробь на 8).
Разделим x на 4096 с остатком:
x=4096*x1+x2.
Тогда:
m=Floor((4096*x1+x2)*125/4096+0.5)=Floor(x1*125+(x2*125)/4096+0.5)=x1*125+Floor((x2*125+2048)/4096).
При вычислении x2*125+2048 переполнения не возникает, поэтому мы можем воспользоваться целочисленной арифметикой. Осталось заменить деление и взятие остатка на сдвиг и логическое «и» соответственно — просто для красоты.

[knekrasov]

Кстати, проверил. Решение отличное. Максимальная погрешность — 0.5, то есть просто не хватает округления.
Спасибо!

[borisko]

Ещё один вариант — слепить маленькую длинную арифметику с базой 2^16 и 3 разрядами. Тогда умножение и бинарный сдвиг легко реализуются в 32битных числах.

[Ekstazi]

Оригинально! Спасибо.

[knekrasov]

На здоровье! Рад, что понравилось.

[boolivar]

Дайте я попробую вспомнить как это было…
В таких случаях используется математика с числами с фиксированной запятой. Смотрите, наша задача разделить ticks на 32,768. ticks — целое число, зафиксируем его запятую у младшего бита[0000 0000,]. Масштаб этого числа M=0. Теперь нужно выбрать масштаб для числа 32,768, более-менее точно это число можно представить с 2 знаками после запятой: 2^5 + 2^-1 + 2^-2 = [1000 00,11] = 32,75, таким образом масштаб этого числа M=2 (пусть меня поправят, возможно это масштаб -2). В двоичном виде число получится 0x83 (десятичное 131).
Таким образом перевод ticks в мс сводится к делению ticks/0x83 и выравниванию масштаба результата. Результат получается с масштабом M=-2, для получения масштаба 0 — умножим на 4 (по сути сдвигаем результат на 2 разряда влево).

Пример: ticks = 32768, ticks/131=250, 250*4=1000

Само число 32,768 можно представить и с большей точностью — захватить побольше знаков после запятой, соответственно число будет в другом масштабе.

[knekrasov]

Да, интересная и логичная мысль, не думал в эту сторону.