From Perl to Java

Question

I am trying to solve some online puzzle finding the largest prime factor of a very large number (7393913335919140050521110339491123405991919445111971 to be exact). In my search for a solution I stumbled upon this Perl code (from here):

use strict;
use warnings;

my $magic = <number>;

sub largestprimef($);
sub max($$);

print largestprimef($magic);

sub largestprimef($) {
    my $n = shift;

    my $i;
    return largestprimef(max(2, $n/2)) if($n % 2 == 0); 
    my $sn = int( sqrt($n) );

    for ( $i = 3 ; $i <= $sn ; $i += 2 ) {
        if ( $n % $i == 0 ) { last; }
    }
    if ( $i > $sn )    #loop ran over, means the number is prime
    {
        return $n;
    }
    else {
        return max( $i, largestprimef( $n / $i ) );
    }
}

sub max($$) {
    return ( sort { $a <=> $b } (@_) )[1];
}

Now that algorithm seemed to work! Small problem with Perl is that it doesn't accept really big numbers. So I rewrote

my $magic = <number>;

to

my $magic = Math::BigInt->new(' <number> ');

but that just runs for ages and ages. So I rewrote it to Java (in which I'm a bit more familiar) which resulted in this:

static final BigInteger two = new BigInteger( "2" );

public static void main( String[] args ) {
    BigInteger number = new BigInteger( "<number>" );

    System.out.println( goAtIt( number ) );
}

static BigInteger goAtIt( BigInteger prime ) {
    if ( isEven( prime ) )
        return goAtIt( prime.divide( two ).max( two ) );

    BigInteger sqrt = sqrt( prime );
    BigInteger comp = new BigInteger( "3" );

    while (sqrt.compareTo( comp ) > 0) {
        if ( prime.remainder( comp ).equals( BigInteger.ZERO ) )
            break;
        comp = comp.add( two );
    }

    if ( comp.compareTo( sqrt ) > 0 )
        return prime;

    return comp.max( goAtIt( prime.divide( comp ) ) );
}

With as auxiliaries (which seem to be fine):

static boolean isEven( BigInteger number ) {
    return number.getLowestSetBit() != 0;
}

static BigInteger sqrt( BigInteger n ) {
    BigInteger a = BigInteger.ONE;
    BigInteger b = new BigInteger( n.shiftRight( 5 ).add( new BigInteger( "8" ) ).toString() );
    while (b.compareTo( a ) >= 0) {
        BigInteger mid = new BigInteger( a.add( b ).shiftRight( 1 ).toString() );
        if ( mid.multiply( mid ).compareTo( n ) > 0 )
            b = mid.subtract( BigInteger.ONE );
        else
            a = mid.add( BigInteger.ONE );
    }
    return a.subtract( BigInteger.ONE );
}

But my results are always off... and my Perl is not really that good to reverse-engineer the original code. Does anyone have a clue on what I'm missing?

==UPDATE: problem is (somewhat) solved by workaround

Answer 1

To answer the translation question...

Your Java translation is very close. It only has one problem - your while loop condition should be >= 0, rather than >0. With that amendment, it will work. As it is - it will output the second largest prime factor in a some cases.

To show this - try it on 1148487369611039 - which has prime factors 104717, 104723 & 104729. Without the correction - it outputs 104723, with the correction, you get the right answer: 104729

Comment on algorithm

As others have noted in comments - this isn't a particularly fast way to do what you want. In fact that's an understatement - it's very slow. On my box it took over 3 minutes to find the correct answer (459905301806642105202622615174502491)¹, but it would take a very long time (maybe 500 years, or that kind of order), to prove that number was prime by simply trial dividing every odd number up to its square root (which is what the algorithm does).

You could use all kinds of tricks to get faster, depending how certain you want to be of getting the answer. One would be to pre-test any candidates for primality - e.g. inserting a test using BigInteger.isProbablePrime() with high certainty as a test in goAtIt() and returning early if you get a very big prime early in the process. If you don't like the probabilistic element of that, you could roll your own Miller-Rabin primality deterministic test. You could also build tables of primes and only ever use those in any trial divisions and / or lookups. You might also consider the Pollard-Strassen algorithm

¹_{(I put an output just after the while loop in goAtIt() to check when it actually found the solution)}

Note on Perl big numbers

Small problem with Perl is that it doesn't accept really big numbers

I think its worse than that because Perl will implicitly turn the large integer into a double precision floating point if you simply replace

my $magic = <number>;

with

my $magic = 7393913335919140050521110339491123405991919445111971;

So - it would give the wrong answer rather than throwing an error as demonstrated on ideone here. Rather nasty, as the algorithm works fine for small numbers and could lull unwary users into a false sense of security if used with larger inputs...