From Perl to Java

Question

I'm trying to solve some online puzzles, I find the biggest simple coefficient of a very large number (7393913335919140050521110339491123405991919445111971, to be precise). Looking for a solution, I came across 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 this algorithm seems to work! A small problem with Perl is that it does not accept really large numbers. Therefore I rewrote

 my $magic = <number>; 

to

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

but it just works for centuries. So I rewrote it in Java (in which I am a little more familiar), resulting in:

 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 ) ) ); } 

Using assistive devices (which seem accurate):

 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 actually not so good as to reverse engineer the source code. Does anyone know what I am missing?

== UPDATE: the problem is (somewhat) resolved in a workaround

Answer 1

To answer the question about the translation ...

Your Java translation is very close. This has only one problem - your while condition should be >= 0 , not >0 . With this amendment, it will work. Be that as it may - in some cases it gives out the second largest simple coefficient.

To show this - try on 1148487369611039 - which has simple coefficients 104717 , 104723 and 104729 . Without correction - displays 104723 , with the correction you will receive the correct answer: 104729

Comment on the algorithm

As others have noted in the comments, this is not a very quick way to do what you want. In fact, this is an understatement - it is very slow. It took me more than 3 minutes on my box to find the correct answer ( 459905301806642105202622615174502491 ) ¹ but it would take a very long time (maybe 500 years or this order) to prove that the number was just a simple method, dividing every odd number to its square root (which is what the algorithm does).

You can use all sorts of tricks to speed up, depending on how definitely you want an answer. It would be possible to pre-test any candidates for primary - for example, inserting a test using BigInteger.isProbablePrime() with a high degree of confidence in the quality of the test in goAtIt() and returning earlier if you get a very big prime at the beginning of the process. If you do not like the probabilistic element of this, you can overturn your own deterministic test of the Miller-Rabin primitive . You can also create prime numbers tables and use them only in any trial units and / or search. You can also consider the Pollard-Strassen algorithm.

¹ _{(I goAtIt() result right after the while in goAtIt() to check when it really found a solution)}

A note on large Perl numbers

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

I think this is worse because Perl will implicitly turn a large integer into a double-precision floating-point if you just replace

 my $magic = <number>; 

with

 my $magic = 7393913335919140050521110339491123405991919445111971; 

So - this will give the wrong answer, and not throw an error, as shown on ideone here . It’s rather nasty, because the algorithm works fine for small numbers and can reduce unwary users with a false sense of security if used with large inputs ...