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

[aelita]

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

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

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

[alexrayne]

Вот здесь вам книга по трюкам для ускоренойоптимальной работе с делениями на константу и кажись есть главы по работе с числами с базисом /= 2
http://www.hackersdelight.org/


Добавлено спустя 1 секунду:
родной базис для современной электроники - 2, все остальное достигается значительными издержками по определению. для работы с другими базисами надо пилить либо свою электронику либо менять постановку задачи.
а постановка задачи,имхо, гнилая, остается ощущение что Вам объяснили как идиоту какомуто, не способному понять чего же требуется. результат Ваших трудов будет соответствовать этому подходу - будет идиотский.

Добавлено спустя 6 минут 28 секунд:
3^81 >= 2^128. насколько я понимаю Вам надо работать с 128битными числами. фрипаскаль, имхо, в настоящее время вам не поможет. стоит посмотреть в сторону pascal XSC или в сторону gcc - там есть спец либы для работы с числами различной точности и разрядности.

[Иван Шихалев]

1. Как уже сказано, лучше всего пилить свою электронику
2. 3^81 таки строго больше, чем 2^128, и это означает, что даже расширения процессора не помогут. Если же достаточно 3^80, то следует обратить внимание на SSE/SSE2 — там имеется арифметика для 128-битных чисел. Работать придется через ассемблер, поскольку соответствующего целого типа в FPC не предусмотрено.
3. Я бы подумал на предмет того, чтобы брать степени тройки из заранее сформированной таблицы и реализовать какие-то операции с использованием этого, а не напрямую.

Добавлено спустя 2 минуты 22 секунды:
И все-таки интересен формат входного потока...

[aelita]

Большое спасибо за советы!

Если быть аккуратнее, 3^80 определенно хватит.
Более того, для некоторого важного подмножества задачи должно хватить даже 3^40.
Поэтому мне крайне интересны советы, ориентированные на Free Pascal с его 64-битным QWord.
На первом этапе можно считать, что на входном потоке подаются именно QWord.

Но мне кажется, что для реального ускорения счета действительно нужен ассемблер с 64 или 128-битной арифметикой.
Проблема, однако, в том, что я никоим образом не являюсь профи в программировании и в ассемблере полная блондинка
(тихо кропаю себе программы для научных вычислений).

Кстати, жаль, что во Free Pascal-e до сих пор не реализованы 128-битные числа...

[alexrayne]

я всетаки поостерегся бы вам советовать делать чегото на асемблере. непортируемо и нефакт что результат будет действительно так хорош как Вы предполагаете. а писать сразу на паскале грамотно - получите готовый резуьтат очень быстро, потом уже если припрет емо можно оптимизировать.
имхо, как раз на такой задаче оптимизатор компилера очень неплохо справится, особенно если Вы целевую платформу LLVM зададите. в пределе имеет смысл написать свои перегруженые операторы для работы со 128бит числами инлайнами ассемблерными.

Добавлено спустя 4 минуты 3 секунды:
и посмотрите всетаки в книжку на которую я ссылку дал, там есть хороший трюк деления на 3 умножением - вот это реальное ускорение которое может даже както скомпенсировать малоразрядность.
+1 за 3й совет Ивана Шихалева про таблицу - может помочь сильно побить ваше большое число на несколько мелких.

[Иван Шихалев]

Если можно ограничиться QWord, то лучше писать на паскале. Включив оптимизацию. Компилятор сам разберется, как это лучше организовать. Ну и алгоритмы важны.

[aelita]

Большое спасибо за информацию и рекомендации, очень полезно!