Yep, that's pretty stupid code all right. Actually we seem to be running about one or two questions a week that look like that so don't feel too bad. The answer is generally the same: use a hash. However in this case there is a twist: "20 million lines from 40 million" is a fairly bif hash. But there may be a smarter solution: if you don't need exactly 20 million lines, then you can:

rand () < 0.5 and print while <>;
[download]

If you need the hash then your current code changes to something like:

open my $rndLines, '<', "rand_sorted.txt" or die "Can't open rand_sort
+ed.txt: $!";
my %lines = map {$_ => undef} grep {chomp; length} <$rndLines>;
close $rndLines;

exists $lines{$.} and print while <>;
[download]

I find it interesting that you couldn't generate a random number list using Perl however. What was the issue that you struck? Are you aware of Math::Random::MT btw?