Здравствуйте, ch00k, Вы писали:

C>Здравствуйте,

C>Возникла недавно задача: есть последовательность 64-битных чисел s1, s2, ... sN, где N — достаточно большое (для определенности пусть будет 4 миллиарда)
C>требуется, обработав эту последовательность, определить, сколько различных элементов нахождится в этой последовательности (т.е., посчитать количество элементов без повторений). Сама послеодвательность находится во внешней памяти, Ответ можно дать приблизительно, с указанным интервалом ошибки.

C>Числа s1.. sN могут быть абсолютно любые 64-битные, т.е. нельзя просто добавлять числа в какую-то структуру данных типа хеша и потом почитать количество ключей — памяти не хватит (ее есть 2Гб).

C>кто-нибдуь может подсказать, в какую сторону копать?

Можно попробывать следующее (точной оценки временной сложности и расхода памяти не делал):
Нужна длинная арифметика то есть работа с большими числами. Каждое новое число последовательности являеться порядковым номером простого числа, то есть мы производим преобразование числа из последовательности в простое число. Далее в нужно производить умножение каждого последующего простого числа на то произведение всех предыдущих, предварительно проверив не встретилось ли такое число на уже раньше. Проверка осуществляеться делением — если на цело то это число у нас уже есть и его добавлять, то есть умножать на уже накопленное произведение не будем. Не трудно организовать счетчик различных чисел так как есть процедура проверки. Загвоздка может быть в формировании простых чисел, хранении конечного произведения (так как чисел всего 2^32 может и хватить — все ж таки не 2^64 как в случае с другой структоруой данных)

Вобщем можно попробывать, рекомендую просмотреть теорию чисел, арифметку по модулю (может удасться теряя точность повысить плотность хранения) и другие похожие темы.