Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Programming Challenge (Out-of-Date)
New Posts  All Forums:Forum Nav:

# Programming Challenge (Out-of-Date) - Page 19

### Poll Results: Are you interested in participating in and/or helping organise and post these programming challenges?

• 100% (2)
I want to participate.
• 0% (0)
I want to contribute by helping posting and organise these challenges.
• 0% (0)
I'll only take part if other people are willing to participate.
• 0% (0)
I can help and participate - I love programming!
• 0% (0)
I do not wish to participate or help.
Pipps pointed out that I wasn't doing exactly what the problem wanted.. i added in the zip function (noted by the woohoo) and had to change the Perin vals to a bigint.

Interesting thing is... that the primes would divide the perin numbers multiple times... i'm trying to say something like p(12) % a(4) == 0 was valid a lot of the time. Anyhow.. proper run for 30 took 15 milliseconds, 300 115 milliseconds, 3000 15 seconds... and somehow prime generation doesn't seem to be the bulk of it. Gonna look into that.

Code:
``````
package test

import scala.collection.mutable.{MutableList => List}
import scala.math.BigInt;

class FindPrime {

def getNextPerin(inp:List[BigInt]):List[BigInt] =
{
val out = inp(inp.length-3) + inp(inp.length-2)
return inp += out
}

def primeList(k:Int):List[Int] =
{
var curr:Int = 3;
var primeList:List[Int] = new List() += 2;
while(primeList.length != k)
{
if(isPrime(curr)) {
primeList += curr;
}

curr+=1;
}
return primeList
}

def isPrime(curr:Int):Boolean = {

if(curr % 2 == 0) { return false; }
var start:Int = curr/2;
if(start == 1) {start = 2; }
while(start > 1)
{
if(curr % start == 0)
{
return false;
}
start -=1;
}

return true;

}

}

object FindPrime {

def main(args : Array[String]) : Unit = {

println(System.currentTimeMillis)
val start = System.currentTimeMillis
var fp =  new FindPrime();
var primeList = fp.primeList(30);
var perinList:List[BigInt] = new List() +=  BigInt(3) += BigInt(0) += BigInt(2)
while(perinList.size != max+1)
{
fp.getNextPerin(perinList)
}
//woohoo
val divs:Seq[(Int,BigInt)] = primeList.zip(primeList.map(i => perinList(i) ));
for(i <- divs)
{

if(i._2 % i._1 == 0) { println(i._2 + "%" + i._1 + "=0")  }
else
{
println("error " + i._2 + "%" + i._1 )

}

}

println(System.currentTimeMillis)
println(System.currentTimeMillis - start);
}
}``````
Here is my java shot at it to make up for the masochistic code to come.

Code:
``````import java.util.Vector;

public class PerrinNumber {

private static Vector<Long> perrin = new Vector<Long>();
private static Vector<Long> prime = new Vector<Long>();

public static void main(String[] args) {
makePrimes(30);
makePerrin(prime.get(prime.size() - 1));
for (int i = 0; i < prime.size(); i ++)
{
System.out.println("P(" + (i+1) + ") = " + prime.get(i)
+ "; A(P(" + (i+1) + ")) = " + perrin.get(prime.get(i).intValue())
+ "; " + perrin.get(prime.get(i).intValue()) + " modulus " + prime.get(i)
+ " => " + (perrin.get(prime.get(i).intValue()) % prime.get(i)));
}
}

private static void makePrimes(int numOfPrimes)
{
boolean primeFound = false;
prime.clear();
for (int i = 0; i < numOfPrimes; i++)
{
primeFound = false;
while (!primeFound)
{
for (int a = 2; a <= primeNumber; a++)
{
primeFound = true;

if ((primeNumber % a) == 0)
break;
}
}
}
}

private static void makePerrin(Long long1)
{
perrin.clear();
for (int i = 3; i < (long1 + 1); i++)
{
perrin.add(perrin.get(i - 2) + perrin.get(i - 3));
}
}

}``````
and the outpu
Code:
``````P(1) = 2; A(P(1)) = 2; 2 modulus 2 => 0
P(2) = 3; A(P(2)) = 3; 3 modulus 3 => 0
P(3) = 5; A(P(3)) = 5; 5 modulus 5 => 0
P(4) = 7; A(P(4)) = 7; 7 modulus 7 => 0
P(5) = 11; A(P(5)) = 22; 22 modulus 11 => 0
P(6) = 13; A(P(6)) = 39; 39 modulus 13 => 0
P(7) = 17; A(P(7)) = 119; 119 modulus 17 => 0
P(8) = 19; A(P(8)) = 209; 209 modulus 19 => 0
P(9) = 23; A(P(9)) = 644; 644 modulus 23 => 0
P(10) = 29; A(P(10)) = 3480; 3480 modulus 29 => 0
P(11) = 31; A(P(11)) = 6107; 6107 modulus 31 => 0
P(12) = 37; A(P(12)) = 33004; 33004 modulus 37 => 0
P(13) = 41; A(P(13)) = 101639; 101639 modulus 41 => 0
P(14) = 43; A(P(14)) = 178364; 178364 modulus 43 => 0
P(15) = 47; A(P(15)) = 549289; 549289 modulus 47 => 0
P(16) = 53; A(P(16)) = 2968530; 2968530 modulus 53 => 0
P(17) = 59; A(P(17)) = 16042867; 16042867 modulus 59 => 0
P(18) = 61; A(P(18)) = 28153269; 28153269 modulus 61 => 0
P(19) = 67; A(P(19)) = 152149094; 152149094 modulus 67 => 0
P(20) = 71; A(P(20)) = 468557684; 468557684 modulus 71 => 0
P(21) = 73; A(P(21)) = 822261415; 822261415 modulus 73 => 0
P(22) = 79; A(P(22)) = 4443758532; 4443758532 modulus 79 => 0
P(23) = 83; A(P(23)) = 13684979327; 13684979327 modulus 83 => 0
P(24) = 89; A(P(24)) = 73957919629; 73957919629 modulus 89 => 0
P(25) = 97; A(P(25)) = 701410194695; 701410194695 modulus 97 => 0
P(26) = 101; A(P(26)) = 2160059765855; 2160059765855 modulus 101 => 0
P(27) = 103; A(P(27)) = 3790640640857; 3790640640857 modulus 103 => 0
P(28) = 107; A(P(28)) = 11673640327812; 11673640327812 modulus 107 => 0
P(29) = 109; A(P(29)) = 20485810695074; 20485810695074 modulus 109 => 0
P(30) = 113; A(P(30)) = 63088012960224; 63088012960224 modulus 113 => 0
P(31) = 127; A(P(31)) = 3233514234548132; 3233514234548132 modulus 127 => 0``````
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
after playing a little bit maybe the better challenge would have been how high can you go
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
Quote:
 Originally Posted by Midpipps after playing a little bit maybe the better challenge would have been how high can you go
That could be another challenge How high can you go in two minutes?
I can get to 30000 in 3 minutes but I need to add a different data type cause longs overflow so it does not technically work
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
This is a sloppily re-factored version of Midpipps' code. Adds support for massive numbers and file output. It does 10,000 primes in roughly 252 seconds on my system.

Code:
``````package challenge.perrin;

import java.io.BufferedOutputStream;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.math.BigInteger;
import java.util.Vector;

public class PerrinPrime {
private static final int NUM_PRIMES = 1000;

private static Vector<BigInteger> perrinList = new Vector<BigInteger>();
private static Vector<BigInteger> primeList = new Vector<BigInteger>();

private long start;
private long end;

private void startTimer() {
this.start = System.currentTimeMillis();
}

private void stopTimer() {
this.end = System.currentTimeMillis();
}

private double getTimedResult() {
return (end - start);
}

public static void main(String[] args) throws Exception {
PerrinPrime perrinPrime = new PerrinPrime();
perrinPrime.startTimer();
makePrimes(NUM_PRIMES);
makePerrin(primeList.get(primeList.size() - 1));
OutputStream os = new BufferedOutputStream(new FileOutputStream("C:\\\
esults.txt"));
for (int i = 0; i < primeList.size() - 1; i ++)
{
String line = ("P(" + (i+1) + ") = " + primeList.get(i)
+ "; A(P(" + (i+1) + ")) = " + perrinList.get(primeList.get(i).intValue())
+ "; " + perrinList.get(primeList.get(i).intValue()) + " modulus " + primeList.get(i)
+ " => " + (perrinList.get(primeList.get(i).intValue()).mod(primeList.get(i))) + "\
");

byte[] bytes = line.getBytes();

os.write(bytes);
}
perrinPrime.stopTimer();
os.close();
System.out.println("Executed in " + (perrinPrime.getTimedResult() / 1000) + " seconds");
}

private static void makePrimes(int numOfPrimes)
{
boolean primeFound = false;
primeList.clear();
for (int i = 0; i < numOfPrimes; i++)
{
primeFound = false;
while (!primeFound)
{

BigInteger index = new BigInteger("2");

primeFound = true;

break;

}
}
}
}

private static void makePerrin(BigInteger long1)
{
perrinList.clear();

BigInteger index = new BigInteger("3");

while(index.compareTo(long1) < 0) {
}
}
}``````
Check out how much big int's slow you down. If you make the prime vector int's(I guess Integer) instead of big ints. I did 20k without displaying the Perrin numbers in about 16 seconds. Will update it tomorrow to print Perrin's out to a file and use similar stop watchery.
Ah a fun night of coding

We made a graph of xTasco run of 10K with his code of how long between iterations.
His code is posted above.

here is the newest code that we are working with less memory intensive but faster we are not sure yet the initial view looks good but will not know for sure until we graph another set of data on it.

Code:
``````import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Vector;

public class PerrinNumber {

private static Vector<BigInteger> perrin = new Vector<BigInteger>();
private static BigInteger prime = BigInteger.valueOf(2);
private static BigInteger currentPerrinPosition = BigInteger.valueOf(3);
private static final int tests = 20000;
private static PrintWriter out = null;

public static void main(String[] args) {
try {
out = new PrintWriter(new FileWriter("output.txt"));
} catch (IOException e) {
e.printStackTrace();
}
long before = System.currentTimeMillis();
printMessage(0);
prime = prime.subtract(BigInteger.valueOf(1));
for (int i = 1; i < tests; i ++)
{
makePrime();
nextPerrin(prime);
printMessage(i);
}
long after = System.currentTimeMillis();
out.close();
System.out.println((after-before)/1000);
}

private static void makePrime()
{
boolean primeFound = false;
while (!primeFound)
{
for (BigInteger a = BigInteger.valueOf(2); a.compareTo(prime) <= 0; a = a.add(BigInteger.valueOf(1)))
{
if (a.compareTo(prime) == 0)
primeFound = true;
if (prime.mod(a) == BigInteger.valueOf(0))
break;
}

}
}

private static void nextPerrin(BigInteger B)
{
while(currentPerrinPosition.compareTo(prime) <= 0)
{
perrin.remove(0);
}
}

private static void printMessage(int i)
{
/*System.out.println("P(" + (i+1) + ") = " + prime.toString()
+ "; A(P(" + (i+1) + ")) = " + perrin.get(3).toString()
+ "; " + perrin.get(3).toString() + " modulus " + prime.toString()
+ " => " + (perrin.get(3).mod(prime)));*/
out.println("P(" + (i+1) + ") = " + prime.toString()
+ "; A(P(" + (i+1) + ")) = " + perrin.get(3).toString()
+ "; " + perrin.get(3).toString() + " modulus " + prime.toString()
+ " => " + (perrin.get(3).mod(prime)));
}
}``````
Will try and run all codes including imps tomorrow on my machine to see the comparability and post results if anyone else wants in on the optimization fun have at it make your own or improve ours have fun it was basically a full night so far of try this run code try that run code. I would upload the data set that is output but it is 499 MB for 20K iterations

Edited by Midpipps - 1/5/11 at 9:48pm
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
 Got a deal on parts (13 items)
CPUMotherboardGraphicsRAM
Q6600 DG33TL XFX 6950 2GB 4gigs Corsair XMS2 DDR2
Hard DriveOptical DriveOSMonitor
1.5TB seagate 2X640GB Samsung DVDRW Windows Vista & Debian Linux Samsung 19" + Acer 24" Wide
KeyboardPowerCaseMouse
Microsoft SideWinder X6 Antec 750 TruePower Raidmax Smilodon COOLER MASTER Sentinel
RocketFish
I hosed mine.. trying to make it use actors. Should have just done the normal thread model. Must.. do.. work.
Ah I slacked up on my C++ studying and now I found this thread proper gonna get back into it.

I should be joining the festivities pretty soon!
CPUMotherboardGraphicsRAM
Intel i7 920 @ 4.03Ghz (Max 4.4) Gigabyte GA-X58A-UD3R REV2.0 ASUS GTX 480 @ 851/1900 6GB Triple Channel DDR3 1600Mhz Corsair+OCZ
Hard DriveOptical DriveOSMonitor
500GB WD Cavair Blue + 500GB Seagate Storage Drive LG HG22NS50 22x DVDRW Windows 7 Ultimate x64/ Snow Leopard Samsung SyncMaster B2230H 1080P
KeyboardPowerCaseMouse
Apple Wired Aluminum Keyboard Corsair HX650W Modular HAF X Logitech G500
Inno3D IChiLL
CPUMotherboardGraphicsRAM
Intel i7 920 @ 4.03Ghz (Max 4.4) Gigabyte GA-X58A-UD3R REV2.0 ASUS GTX 480 @ 851/1900 6GB Triple Channel DDR3 1600Mhz Corsair+OCZ
Hard DriveOptical DriveOSMonitor
500GB WD Cavair Blue + 500GB Seagate Storage Drive LG HG22NS50 22x DVDRW Windows 7 Ultimate x64/ Snow Leopard Samsung SyncMaster B2230H 1080P
KeyboardPowerCaseMouse
Apple Wired Aluminum Keyboard Corsair HX650W Modular HAF X Logitech G500