I was curious how Perl was getting such good performance from this code, so I felt like I needed to do a comparison. Since there are some seemingly useless differences in the control flow and operations between the versions of Perl and Julia code in this question, I ported each version to a different language and compared all four. I also wrote the fifth version of Julia using more idiomatic numerical functions, but with the same control flow structure as the Perl version question.
The first option is essentially the Perl code from the question, but wrapped in a function:
sub perl1 { my $k = $_[0]; foreach my $n (10**($k-1) .. 10**($k)-1) { my $front = $n * (10**$k + $n); my $root = int(sqrt($front)); foreach my $t ($root-2 .. $root+2) { my $back = $t * ($t - 1); last if length($t) > $k; last if $back > $front; if ($back == $front) { print STDERR "$n$t\n"; last; } } } }
Then I transferred it to Julia, preserving the same control flow and using the same operations - it takes the integer floor of the square root from front in the outer loop and takes the length of the “structure” t in the inner loop:
function julia1(k) for n = 10^(k-1):10^k-1 front = n*(10^k + n) root = floor(Int,sqrt(front)) for t = root-2:root+2 back = t * (t - 1) length(string(t)) > k && break back > front && break if back == front println(STDERR,n,t) break end end end end
Here's the question, Julia's code with some minor formatting techs wrapped in a function:
function julia2(k) for a = 10^(k-1):10^k-1 front = a * (10^k + a) root = floor(front^0.5) for b = root-1:root+1 back = b * (b - 1); back > front && break log(10,b) > k && continue if front == back @printf STDERR "%d%d\n" ab
I translated this to Perl, preserving the same structure of the control flow and using the same operations as the Perl code occupying the root floor, raised to 0.5 in the outer loop and taking the logarithmic base 10 into the inner loop:
sub perl2 { my $k = $_[0]; foreach my $a (10**($k-1) .. 10**($k)-1) { my $front = $a * (10**$k + $a); my $root = int($front**0.5); foreach my $b ($root-1 .. $root+1) { my $back = $b * ($b - 1); last if $back > $front; next if log($b)/log(10) > $k; if ($front == $back) { print STDERR "$a$b\n" } } } }
Finally, I wrote a version of Julia with the same control flow structure as the Perl question, but it uses more idiomatic numerical operations - the isqrt and ndigits :
function julia3(k) for n = 10^(k-1):10^k-1 front = n*(10^k + n) root = isqrt(front) for t = root-2:root+2 back = t * (t - 1) ndigits(t) > k && break back > front && break if back == front println(STDERR,n,t) break end end end end
As far as I know (I used a lot of Perl programming, but it was a while), there are no versions of Perl for any of these operations, so there is no corresponding version of perl3 .
I completed all five options with Perl 5.18.2 and Julia 0.3.9 respectively, ten times each for 2, 4, 6, 8, 10, 12, and 14 digits. Here are the sync results:
The x axis is the number of digits requested. Y-axis - the average time in seconds required to calculate each function. The Y axis is plotted on a log scale (there is some rendering error in the Cairo backend Gadfly , so the superscripts don't appear very raised). We can see that with the exception of the smallest number of digits (2), all three Julia variants are faster than both Perl variants, and julia3 much faster than everything else. How much faster? Here's a comparison of the other four options regarding julia3 (not a logarithmic scale):
The x axis is the number of digits requested, and the y axis is how many times slower than each option than julia3 . As you can see here, I was unable to reproduce the Perl performance stated in the question - Perl code was not 2 times faster than Julia - it was 7-40 times slower than julia3 and at least 2 times slower than the slowest Julia version for any non-trivial number of digits. I have not tested Perl 5.20 - maybe someone could follow up on these tests with the new Perl and see if this explains the different results? The code to run the tests can be found here: excellent.pl , excellent.jl . I ran them as follows:
cat /dev/null >excellent.csv for d in 2 4 6 8 10 12 14; do perl excellent.pl $d >>excellent.csv julia excellent.jl $d >>excellent.csv done
I analyzed the resulting excellent.csv file using this Julia script .
Finally, as mentioned in the comments, using BigInt or Int128 is an option for learning great great numbers in Julia. However, this requires a little caution when writing the algorithm as a whole. Here is the fourth option that works as a whole:
function julia4(k) ten = oftype(k,10) for n = ten^(k-1):ten^k-1 front = n*(ten^k + n) root = isqrt(front) for t = root-2:root+2 back = t * (t - 1) ndigits(t) > k && break back > front && break if back == front println(STDERR,n,t) break end end end end
This is the same as julia3 , but works for universal integer types by converting 10 to the type of its argument. Since the algorithm scales exponentially, however, it takes a lot of time to calculate the number of digits larger than 14.
julia> @time julia4(int128(10))
It works, but 37 minutes is a long wait. Using a faster programming language gives you a constant acceleration factor - 40 times in this case - but it only buys a couple of extra digits. To really explore great great numbers, you need to learn the best algorithms.