1. Простые и быстрые алгоритмы есть в Perl Cookbook
2. Массивы размером миллиард и триллион элементов так не сравнить - памяти просто не хватит.
3. Какой тип данных? Понятно что в Perl это вроде не так важно, но для решения задачи значение имеет.
Навскидку решение:
Допустим что у нас только целые числа - значения от 0 до 65535. Построим битовую маску имеющихся в массиве чисел, причем если число есть - соответствующий ему бит выставим в 1. Размер маски очевидно 65536 бит или 8192 байта, что совсем и не много.
Итак, идем по первому массиву и заполняем маску.
Теперь идем по второму массиву и если бит в маске для текущего числа выставлен в 1, то число не уникально.