Comments 14
Ну от этого:
к этому:
без особых усилий можно было перейти. Точность наверное меньше, чем в окончательном варианте, но больше чем у исходной реализации.
private int getMillis(int ticks) {
return (ticks >> 5) - 3*(ticks >> 12);
}к этому:
private int getMillis(int ticks) {
return (ticks - (ticks >> 7) - (ticks >> 6)) >> 5;
}без особых усилий можно было перейти. Точность наверное меньше, чем в окончательном варианте, но больше чем у исходной реализации.
А чем плохо такое решение?
Проверил до 10^9 — ошибок по сравнению с (x*1000+0x4000)>>15 (вычисленному в 64-битных числах) нет.
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-битных числах) нет.
Не проверял, но выглядит круто!
Не подскажете, откуда берутся магические числа 125 и 0x800?
Не подскажете, откуда берутся магические числа 125 и 0x800?
Мне тоже интересно откуда!
1<<12 = 4096
4096*125=32.768=32768/1000
0x800 = 4096/2
4096*125=32.768=32768/1000
0x800 = 4096/2
Точнее, 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 переполнения не возникает, поэтому мы можем воспользоваться целочисленной арифметикой. Осталось заменить деление и взятие остатка на сдвиг и логическое «и» соответственно — просто для красоты.
Теперь более полно.
Нам нужно вычислить
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 переполнения не возникает, поэтому мы можем воспользоваться целочисленной арифметикой. Осталось заменить деление и взятие остатка на сдвиг и логическое «и» соответственно — просто для красоты.
Кстати, проверил. Решение отличное. Максимальная погрешность — 0.5, то есть просто не хватает округления.
Спасибо!
Спасибо!
Ещё один вариант — слепить маленькую длинную арифметику с базой 2^16 и 3 разрядами. Тогда умножение и бинарный сдвиг легко реализуются в 32битных числах.
Оригинально! Спасибо.
Дайте я попробую вспомнить как это было…
В таких случаях используется математика с числами с фиксированной запятой. Смотрите, наша задача разделить 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 можно представить и с большей точностью — захватить побольше знаков после запятой, соответственно число будет в другом масштабе.
В таких случаях используется математика с числами с фиксированной запятой. Смотрите, наша задача разделить 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 можно представить и с большей точностью — захватить побольше знаков после запятой, соответственно число будет в другом масштабе.
Sign up to leave a comment.
Задача с погрешностью и переполнением