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

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
 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
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
 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
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
 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
 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
 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
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
 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
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) {
if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(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
 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
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.
 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
 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
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.
 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
 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
 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
 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
New Posts  All Forums:Forum Nav:
Return Home
Back to Forum: Coding and Programming
• Java modulus isn't working with large numbers
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Java modulus isn't working with large numbers