Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Java modulus isn't working with large numbers
New Posts  All Forums:Forum Nav:

Java modulus isn't working with large numbers

post #1 of 9
Thread Starter 
I'm doing a prime number program and whenever I try to find a prime with at least 17 digits (double i= Math.pow(10.0,16) ), isPrime never returns an answer for 17 digits or greater. I debugged and even for an odd number (k%2 ==0) is returning false, when the code should be skipped since if k is odd, k%2 ==1. I can't really change the data type because I need double for its size, but at large numbers it doesn't work for modulus.
How do I get isPrime to work for large values of k?
Code:
     while(true){

                Scanner input = new Scanner(System.in);
                System.out.print("Enter the minimum number of digits for your prime number (-1 to quit): ");
                int n = input.nextInt();
                if(n==-1)break;
                
                long startTime = System.currentTimeMillis();
                
                double i = Math.pow(10.0, n-1);
                while(true){    
                        if(isPrime(i) == true) break;
                        i++;
                }
                long endTime = System.currentTimeMillis();
                long duration = endTime - startTime;
                
                DecimalFormat df = new DecimalFormat("#");
                System.out.println("Prime of at least " + n + " digits is "+ df.format(i));
                System.out.println("It took " + duration + " miliseconds");
                }
                        
        }
                
        private static boolean isPrime (double k){
                if ( k%2.0 == 0.0) return false;
                if (k%3.0 == 0.0) return false;
                for (double i=1.0; 6*i+1<=Math.sqrt(k); i++)
                        if (k%(6*i-1) == 0.0 || k%(6*i+1) == 0.0) return false;
                return true;
        }

edit: even if I remove the decimal part .0 in isPrime I still have the problem.
(like this)
Code:
if ( k%2 == 0) return false;
                if (k%3 == 0) return false;
                for (double i=1; 6*i+1<=Math.sqrt(k); i++)
                        if (k%(6*i-1) == 0 || k%(6*i+1) == 0) return false;

Edited by 1keith1 - 8/11/13 at 4:26pm
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
post #2 of 9
Have you tried using a long instead of a double? Since checking if a non integer number is odd or even is pretty pointless, might as well use the more correct type.
Back in Black
(13 items)
 
  
CPUMotherboardGraphicsRAM
AMD Phenom II X4 965 BE (C3) Biostar TA790GX A3+ Sapphire HD 5770 (v2) CORSAIR XMS3 4GB DDR3 
Hard DriveOptical DriveOSMonitor
WD Caviar Black 640GB Sony Optiarc CD/DVD RW Windows 7 Ultimate x64 NEC MultiSync LCD 1960NXi 
KeyboardPowerCaseMouse
Microsoft Comfort Curve Keyboard 2000 Corsair 650TX Cooler Master Storm Scout Logitech MX 400 Laser 
  hide details  
Reply
Back in Black
(13 items)
 
  
CPUMotherboardGraphicsRAM
AMD Phenom II X4 965 BE (C3) Biostar TA790GX A3+ Sapphire HD 5770 (v2) CORSAIR XMS3 4GB DDR3 
Hard DriveOptical DriveOSMonitor
WD Caviar Black 640GB Sony Optiarc CD/DVD RW Windows 7 Ultimate x64 NEC MultiSync LCD 1960NXi 
KeyboardPowerCaseMouse
Microsoft Comfort Curve Keyboard 2000 Corsair 650TX Cooler Master Storm Scout Logitech MX 400 Laser 
  hide details  
Reply
post #3 of 9
Thread Starter 
Yea I guess I could, a double has a higher max value than long though, thats why.

just tried using long and it gives a negative number for finding a 20 digit prime number. not going to do.
Edited by 1keith1 - 8/12/13 at 12:03am
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
post #4 of 9
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
post #5 of 9
Thread Starter 
I tried, but the syntax is a lot more work for the for loop in isPrime. parcticularly had a problem when I need to take the square root of k.
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
post #6 of 9
Here is a solution for square root with the Biginteger class

http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
Code:
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);
}

usage
Code:
BigInteger n = new BigInteger("34598734524213124593869456843967349872984172392043275489357439720358723");
BigInteger temp = new BigInteger(sqrt(n).toString());

System.out.println(temp.toString());
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
post #7 of 9
Thread Starter 
That looks really good, i'll go ahead and convert my program to bigInteger tonight. too bad my cpu is only 3Ghz, any large prime numbers will take a bit of time. tongue.gif
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
post #8 of 9
Thread Starter 
Code:
private static boolean BigInteger_isPrime(BigInteger k)      
        {
                if( k.mod( BigInteger.valueOf(2) ) == BigInteger.ZERO ) return false;
                if( k.mod( BigInteger.valueOf(3) ) == BigInteger.ZERO ) return false;
                BigInteger root = sqrt(k);
                BigInteger j;
                for( BigInteger i = BigInteger.valueOf(1); BigInteger.ONE.add( j = i.multiply( BigInteger.valueOf(6) ) ).compareTo(root) != 1; i= i.add(BigInteger.ONE) )
                        if( (k.mod( BigInteger.ONE.add(j) ) == BigInteger.ZERO) || (k.mod( j.subtract(BigInteger.ONE) ) == BigInteger.ZERO) ) return false;
        
                return true;
        }

Cool code works great now thanks! Now I wait for my code to give me my answers. tongue.gif
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
Only 9" Tall
(8 items)
 
  
CPUMotherboardGraphicsRAM
i5 4570 3.6Ghz Turbo Asrock Z87E-ITX Powercolor 7750 Samsung 
Hard DriveCoolingOSCase
Mushkin Chronos Scythe Big Shuriken v2 Windows 8.1 64bit Lian Li PC-Q02B 
  hide details  
Reply
post #9 of 9
Glade to help.thumb.gif Good luck on your search.
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
Core I7
(13 items)
 
  
CPUMotherboardGraphicsRAM
I7 920 rev. D0 @ 4.26Ghz EVGA X58 SLI EVGA GTX 285 OCZ XMP 3x2Gb (pc3 12800) 
Hard DriveOptical DriveOSMonitor
Western Digital Caviar Black 640Gb x 2 LG GH22LS30 openSuse 12.1 x64 HP F2105 
PowerCase
CORSAIR 850TX Cooler Master ATCS 840 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Java modulus isn't working with large numbers