Быстро делим на 3

Здравствуйте.

Часто читаю WE, так как интересуюсь программированием микроконтроллеров, и решил наконец-то зарегистрироваться, а заодно и запостить статеечку в личный блог.
Статья будет мало кому интересная по причине вопроса не шибко востребованного — а именно быстрого деления числа любой разрядности на 3.


Как-то понадобилось мне часто и быстро делить 16-битные числа на 3 на 8-разрядных PICах. Делить втупую методом сложения не хотелось, ибо это долго и неэффективно — ну вы меня понимаете. Посмотрел на другие методы, и мне они не понравились. В итоге очередной бессонной ночью пришла в голову идея, как все же можно реализовать деление гораздо быстрее, правда теорию я под это дело не подвел, извините. Возможно метод работает в каких-то ситуациях коряво, но мне вполне подходит — высокая точность не нужна, главное скорость.
Итак, суть метода возможно известна всем, кроме меня — на такие мысли наталкивает память о суровых студенческих буднях, наполненных экзаменами/зачетами по разного рода математикам, в которых я совершенно не блистал. А зря.

Но перейдем наконец к методу, чтобы светила сообщества получили повод обругать меня разными выражениями за недалекость или колхозанство, как вариант)
Легче всего объяснить на примере. Метод очень простой для реализации на любом языке.
Допустим, у нас есть 16-разрядное число, которое нужно поделить — 0xF24E (d62030).
Приступим к делению немедленно, и именно в 16-ричном виде — так лично для меня магии больше))):

1 итерация: Делим 0xF24E на 2 — получаем промежуточный результат 0x7927, запоминаем.
2 итерация: Делим остаток еще на 2: 0x7927/2 = 0x3C93, прибавляем его к предыдущему промежуточному результату: 0x7927 + 0x3C93 = 0xB5BA
3 итерация: Делим остаток на 2: 0x3C93/2 = 0x1E49, вычитаем его из предыдущего промежуточного результата: 0xB5BA — 0x1E49 = 0x9771
4 итерация: Делим остаток на 2: 0x1E49/2 = 0xF24, прибавляем его к предыдущему промежуточному результату: 0x9771 + 0xF24 = 0xA695
5 итерация: Делим остаток на 2: 0xF24/2 = 0x792, вычитаем его из предыдущего промежуточного результата: 0xA695 — 0x792 = 0x9F03
6 итерация: Делим остаток на 2: 0x792/2 = 0x3C9, прибавляем его к предыдущему промежуточному результату: 0x9F03 + 0x3C9 = 0xA2CC
7 итерация: Делим остаток на 2: 0x3C9/2 = 0x1E4, вычитаем его из предыдущего промежуточного результата: 0xA2CC — 0x1E4 = 0xA0E8
8 итерация: Делим остаток на 2: 0x1E4/2 = 0xF2, прибавляем его к предыдущему промежуточному результату: 0xA0E8 + 0xF2 = 0xA1DA
9 итерация: Делим остаток на 2: 0xF2/2 = 0x79, вычитаем его из предыдущего промежуточного результата: 0xA1DA — 0x79 = 0xA161
10 итерация: Делим остаток на 2: 0x79/2 = 0x3C, прибавляем его к предыдущему промежуточному результату: 0xA161 + 0x3C = 0xA19D
11 итерация: Делим остаток на 2: 0x3C/2 = 0x1E, вычитаем его из предыдущего промежуточного результата: 0xA19D — 0x1E = 0xA17F
12 итерация: Делим остаток на 2: 0x1E/2 = 0x0F, прибавляем его к предыдущему промежуточному результату: 0xA17F + 0x0F = 0xA18E
13 итерация: Делим остаток на 2: 0x0F/2 = 0x07, вычитаем его из предыдущего промежуточного результата: 0xA18E — 0x07 = 0xA187
14 итерация: Делим остаток на 2: 0x07/2 = 0x03, прибавляем его к предыдущему промежуточному результату: 0xA187 + 0x03 = 0xA18A
15 итерация: Делим остаток на 2: 0x03/2 = 0x01, вычитаем его из предыдущего промежуточного результата: 0xA18A — 0x01 = 0xA189
16 итерация: дальше делить смысла нет, будет 0x00. А тем временем промежуточный результат — это 2/3 от изначального числа, вычитаем из изначального числа наш промежуточный результат, получим 1/3 сразу с коруглением в «правильную сторону»: 0xF24E — 0xA189 = 0x50C5 (d20677).

Вот и все. Делим на 2 и чередуем — вычитать или складывать (можно, кстати, поменять знаки местами).
Этот безобразие в нашем тесном коллективе зовется «супер-метод», а далее мое имя или какой-нибудь обидный прицеп, смотря в каком настроении находится оратор)

Спасибо за внимание.

Комментарии (28)

RSS свернуть / развернуть
2 итерация: Делим остаток еще на 2: 0x7927/2 = 0x3C93, прибавляем его к предыдущему промежуточному результату: 0x7927 + 0x3C93 = 0xB5BA
3 итерация: Делим остаток на 2: 0x3C93/2 = 0x1E49, вычитаем его из предыдущего промежуточного результата: 0xB5BA — 0x1E49 = 0x9771
А это не то же самое, что поделить остаток с шага 1 на 4 и прибавить?
0
  • avatar
  • Vga
  • 16 июля 2013, 15:55
Хмм. Кажется, что да, но есть такой момент:
0x7927 + (0x7927/4) = 0x7927 + 0x1E49 = 0x9770 против 0x9771
Единичка теряется и уже ниоткуда не возьмется, если навскидку.
Ну и если организовывать цикл, то на мой взгляд, одинаковые итерации более приоритетны в этом случае.
0
Итерации тоже останутся одинаковыми, только сдвиг не на 1 бит, а на 2. Но единички действительно теряются. В сообщении zubb похожий метод, но поточнее.
0
Ага, я уже плюсанул за его комментарий) Сам не додумался до такого)
0
Алгоритм ТС можно к любой разрядности применить без переделок, хотя по сути это одно и то же.
0
только сдвиги/сложения:
U16 div_by3_U16_soft(U16 data_in) {
    U32 U32_01, result;
    result = U32_01 = data_in;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    result += 0x5555; //correction
    return(result >> 16);
}

если есть аппаратное умножение:
U16 div_by3_U16_hmul(U16 data_in) {
    return((((U32)data_in * 0x5555) + 0x5555) >> 16);
}
+5
Тоже подумал об общем множителе
0
Да, это интереснее, спасибо!
Не подумал.
Туплю, но пока не втыкаю как 0x5555 получили)
0
:) обычная уличная магия
0
или так:
uint16_t div3_16_hmul(uint16_t data) {
    return((((uint32_t)data + 1) * 0x5555UL) >> 16);
}
0
Этот вариант получше оптимизируется (если 0x5555UL записать как 0x5555), т.к. нет необходимости вычислять младшее слово.
0
Сумма ряда 1/(2^n) = 1.0
Сумма ряда 1/(2^2n) = 2/3
0
Пардон, продолжу
Сумма ряда 1/(2^2n + 1) = 1/3

Алгоритм фактически вычитает из ряда 1/(2^2n) ряд 1/(2^2n + 1) и получается 1/3
0
Да, конечно это ряды, метод так и придумал — сидел вспоминал то, что запомнилось из института про ряды, да крутил в голове числа. Но числа сложились раньше, чем я пошел вспоминать про суммы рядов (на память не помню, с математикой туговато), локальная задача была решена, на теорию забито)
Спасибо.
0
Посмотрите здесь: www.hackersdelight.org/hdcodetxt/divuc.c.txt
Там много интересного.
+6
Спасибо, стащил файлик и себе)
0
что за ЛОЛ.
хз, как вы это придумали, но это алгоритм деления двоичных чисел.
и то, если нет аппаратного умножения. если оно есть, то быстрее (как вы понимаете) помножить на 256/3 и откинуть 8 младших бит.
-2
Пример умножения 8/16 битного беззнакового целого на 256/3 с откидыванием младших 8 бит, при наличии аппаратного умножения 8 х 8 бит = 16 бит (восьмибитная архетиктура же), не приведёте?
+1
очень просто.
допустим, 16бит состоит из 2х половин — U|V. его надо умножить на X. тогда получим
UV*X = UXh | UXl + VXh | VXl
l и h означают старшую и младшую части результатов умножений 8x8->16
откидывая 3й (младший байт результата) имеем 2 умножения и 1 сложение.
касательно деления на 3 будет:
UV/3 = h(U*85) | l(U*85) + h(V*85)
например для 20000/3:
4E20/3:
4E*55 = 19E6
20*55 = 0AA0
в итоге 19F0 = 6640(dec)
6640*3=19920, что достаточно точно. если надо точнее, можно умножать на 65536/3 по той же схеме
-2
Это не достаточно точно. Даже при выборе числа ровно делящегося на 3, мы получаем ошибку. Это не деление — это оценка.
+2
раскрыть комментарий
-5
получим 1/3 сразу с коруглением в «правильную сторону»
Как бы намекает.
А сразу вы написали «что за ЛОЛ», но ни как не про точность.
+2
Два умножения и три сложения.
y=3*x => x=y/3, y=2*y/3+y/3 => x=2*y/9+y/9
Допустим, нас устраивает точность плюс-минус 1/256. Тогда, что вычислить 256*x, нужно вычислить формулу 256*x=57*y+28*y+1.
Может, возникнуть вопрос, зачем прибавлять единицу. Проверяем. 57*3+28*3+1=256.
0
В чем глубокая мысль разбиения 85 на 2 слогаемых 57 + 28? Переполнений при умножении не будет же и без этого. Ваш код тот же самый, что
x = ( 85 * y  + 1 ) / 256
Да, при y=3 он у вас отработал, но уже при y=6 мы получаем x = 1, а не 2. Для больших чисел тоже получаем результат на 1 меньше.
0
Проверил — точно. Деление на 256 даёт стабильную ошибку округления, поэтому математически верно делить на 255.
x =  (85 * y + 28 * y) / 255

Проблема в том, что деление на 255 это не то же самое, что отбросить младший байт.
0
За саму работу (надо же посидеть и подумать, а не просто попросить камешек посильнее) плюсик. а в целом, если почитать литературу типа журнала квант и приложения к нему, способ известный.
0
  • avatar
  • xar
  • 17 июля 2013, 20:24
Уже не в личный.
0
Ну если пост может кому-то помочь, буду только рад. Хотя комментарии к нему, кажется, более ценны)
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.