Быстрая работа с числами в троичной системе

[aelita]

Знает ли кто-нибудь быстрый алгоритм\юнит для работы с целыми (и довольно большими -- до 3^80) числами в троичной системе?
Имеется в виду, заметно быстрее, чем с помощью стандартных операций div 3, mod 3 на языке высокого уровня (я работаю на Free Pascal).
Т.е. по-видимому, на Ассемблере и м.б. даже используя что-то вроде быстрых преобразований Фурье.

Прежде всего, такая задача:
на входе -- поток вычисленных некоторым способом чисел как неких величин вне зависимости от системы счисления,
и нужно максимально быстро определить, какая троичная цифра (0,1 или 2)
будет стоять на k-ой позиции в троичном представлении каждого числа.

Огромная благодарность тем, кто что-то подскажет, очень нужно!!!

Сообщение отредактировано: aelita - 04.10.11, 22:56

[Pavia]

aelita
Советую почитать Кнута.

Храни в байте по 5 разрядов. 3*3*3*3*3=243
При умножение и сложение используй длинную арифметику. Для получения разряда сначала находишь байт, а потом табличкой раскладываешь байт на разряды.
Правда div и mod сейчас работают быстро и оптимизировать их не надо.
Вот только делить на 3 не надо. Надо делить на 3*k,если k=0 делить не надо.

Сообщение отредактировано: Pavia - 04.10.11, 05:09

[aelita]

Спасибо!
В самом деле, Кнут может что-то подсказать.

1) Вы имеете в виду, что делить на 3k лучше, чем несколько раз на 3?

2) Мне все же представляется, что для реального ускорения счета нужно использовать 128-битные вычисления в ассемблере (поскольку 2^128 > 3^80).
Однако, в ассемблере я полная блондинка (программа нужна для научных вычислений, а я никоим образом не являюсь профи в программировании).

3) Впрочем, на первом этапе вполне достаточно считать, что на входе подаются 64-битные числа в формате QWord Free Pascal,
которые надо очень быстро перевести в троичную систему до 3^40. Вероятно, для скорости нужно использовать 64-битную арифметику ассемблера.

Сообщение отредактировано: aelita - 04.10.11, 23:20

[Pavia]

Цитата aelita @ 04.10.11, 23:00

1) Вы имеете в виду, что делить на 3k лучше, чем несколько раз на 3?

Да. Я как понял тебе нужно всего одно число в к-ой позиции.

Цитата aelita @ 04.10.11, 23:00

2) Мне все же представляется, что для реального ускорения счета нужно использовать 128-битные вычисления в ассемблере (поскольку 2^128 > 3^80).
Однако, в ассемблере я полная блондинка (программа нужна для научных вычислений, а я никоим образом не являюсь профи в программировании).

Во-первых 128-битные числа сами по себе не дают ускорение. Ускорение даёт параллельная обработка данных.
Во-вторых 128-битного деления CPU не поддерживает. И если бы поддерживал, то ускорения это бы не дало. Так как деление носит инерционный характер вычисления, то чем длиньше числа тем дольше они делятся.

[leo]

Цитата Pavia @ 04.10.11, 05:09

Правда div и mod сейчас работают быстро и оптимизировать их не надо

Тем не менее умножение работает почти на порядок быстрее, поэтому трюки с заменой деления на константу умножением на обратную величину никто не отменял (хотя для вычисления остатка это не так эффективно, но все же м.б.заметно быстрее деления)

Сообщение отредактировано: leo - 05.10.11, 07:30

[Pavia]

leo

Цитата leo @ 05.10.11, 07:15

Тем не менее умножение работает почти на порядок быстрее, поэтому трюки с заменой деления на константу умножением на обратную величину никто не отменял

А ты проверь Из-за зависимости по данным так как после умножения идёт сдвиг мы имеем, что умножение выполняется не оптимально. Отсюда имеем максимум 5 кратное увеличение. А если учесть что для некоторых делителе ещё требуется увеличение на 1 то прирост всего в 4 раза.
Но мая практика показывает что оно и до 2 раз не всегда доходит.
Если в цикле будет условные переходы то увеличении производительности можно забыть.
Даже проста операция такая как загрузка данных из ОЗУ в регистр может выполнятся дольше деления.

[leo]

Цитата Pavia @ 05.10.11, 08:15

А ты проверь Из-за зависимости по данным так как после умножения идёт сдвиг мы имеем, что умножение выполняется не оптимально

Причем тут оптимально\не_оптимально? Умножение выполянется с фикс.задержкой (латентностью) - 3 такта на (современных) AMD и 5 на Core (mul-5,imul-3), а 32-битное деление соотв-но до 40 тактов на AMD и до 25-30 на Core. Для вычисления частного и остатка от деления нужно 2 умножения (mul + imul), плюс несколько однотактовых операций (пересылка,сдвиг,вычитание), часть из которых может выполняться одновременно с умножением - в итоге все это дело тянет на (3..5)+1+3+1 = 8..10 тактов

//mov ebx,565592401 //= Trunc(2^37/243)
...
mov edi,eax    //+0 если одновременно с mul или пред.операцией
mul ebx        //+(3..5) тактов  
shr edx,5      //+1 такт
mov eax,edx    //+0 одновременно с imul
imul edx,243   //+3 такта
sub edi,edx    //+1 такт

Цитата Pavia @ 05.10.11, 08:15

Но мая практика показывает что оно и до 2 раз не всегда доходит

Ну, а "до 2 раз" - это разве мало?

Цитата Pavia @ 05.10.11, 08:15

Если в цикле будет условные переходы то увеличении производительности можно забыть.
Даже проста операция такая как загрузка данных из ОЗУ в регистр может выполнятся дольше деления.

Ну это вообще "из другой оперы"

[Pavia]

leo

Цитата leo @ 05.10.11, 11:06

Причем тут оптимально\не_оптимально? Умножение выполянется с фикс.задержкой (латентностью)

Есть 2 типа задержек. Latency и throughput. Первую я назвал не оптимальной вторую оптимальной.
Latency - задержка до завершения операции.
throughput - задержка до того как вычислительный блок можно будет использовать для другой операции

Так вот у деления задержка будет браться throughput. А вот если делать через умножение то там будет Latency.
Но в целом первое уравновешивает второе. Просто я упоминал про оптимально\не_оптимально чтобы вы правильно такты посчитали.

Сейчас залез в Агнера Фога с удивлением узнал, что руководство от intel привирает.
Так вот у Агнера Фога результат видимо точнее, он для маленьких чисел указывает результат гораздо меньше
Core в зависимости от модели для маленьких чисел
модель Latency throughput
CORE65 18 12
CORE45 9 -
Nehalem 11 7

Цитата

Ну, а "до 2 раз" - это разве мало?

Мало много понятие растяжимое.
2 раза хорошо, всё что меньше меня печалит. Дольше разбираться надо.

Цитата

Ну это вообще "из другой оперы"

Был у меня выбор добавить mod N в цикл или нет. Для безопасности кода решил добавить mod, а скорость и не изменилась. Относительная точность измерений скорости 10%

Сообщение отредактировано: Pavia - 05.10.11, 13:05

[leo]

Цитата Pavia @ 05.10.11, 12:47

Так вот у деления задержка будет браться throughput

Это только для независимых операций, а при переводе числа из одной системы счисления в другую, вычисление каждого следующего разряда зависит от предыдущего и соотв-но следующее деление не может начаться пока полностью не завершится предыдущее -> latency в чистом виде

Цитата Pavia @ 05.10.11, 12:47

Сейчас залез в Агнера Фога с удивлением узнал, что руководство от intel привирает.
Так вот у Агнера Фога результат видимо точнее, он для маленьких чисел указывает результат гораздо меньше

Не знаю, где ты увидел "гораздо", т.к. в интеловском мане примерно те же цифры (для IDIV r32).
Да, за счет фишки с "early exit" деление с малым результатом выполняется быстрее. Но в данной задачке речь идет о работе с "довольно большими -- до 3^80) числами", поэтому при многократных делениях будут встречаться и большие и малые задержки, так что можно расчитывать только на некое среднее значение

Добавлено 05.10.11, 15:39
PS: Конечно для частной задачки, когда нужно узнать только одну троичную цифру на фикс.позиции k (т.е. не обязательно раскладывать все число) можно и двумя делениями обойтись (на 3^k из таблицы и затем на 3 для получения остатка)

[Pavia]

Цитата leo @ 05.10.11, 15:29

зависит от предыдущего и соотв-но следующее деление не может начаться пока полностью не завершится предыдущее -> latency в чистом виде

Так чисел у него много. Можно делить каждое.
А если бы было одно то можно, так. Поделить на 3*3*3*3 получим частое и остаток. Их уже двое и их можно поделить на 3*3 что хорошо параллелится и так далее.

Цитата leo @ 05.10.11, 15:29

Но в данной задачке речь идет о работе с "довольно большими -- до 3^80) числами"

И что? Можно ведь взять алгоритм с постоянной скоростью основанный на деление маленькими числами.

Сообщение отредактировано: Pavia - 05.10.11, 16:03

[leo]

Pavia
Ладно, убедил