Chanllege: Lad os se hvis computer kan regne dette hurtigst

Fedest - men hvorfor ikke vælge en test vi ikke kan klare "i hånden"?

S= 1 + 2 + 3+......+N
=> S = (N+1)*N/2

N= 2⁶³-1

=> S= 2⁶³ * (2⁶²-½) = 2¹²⁵-2⁶² = 4,2535296E37

stig65 vinder prisen som den hurtigste CPU.

Hvem vil have kage?

hmmm, jeg vil hellere have en computer...

Nej, helt alvorligt - var det ikke smartere at sætte folk til at udregne pi med 1000 cifre, beregne de 1000 første primtal eller lignende?

Stig du har regne forkert du har regnet med 2^63 ikke i 64
De først prim tal skulle ikke være så svært
MEn det kan vi godt sige i stedet for

(2⁶⁴)/2 = 2⁶³

Nu må i lige bestemme jer hvad der skal regnes på?? ;)
Hvem skriver først en løsning til brug på Amazon cloud løsning ;)

vi går efter den med prime

Egentligt tror jeg ikke jeg gider - den slags lavede vi lidt for meget under min uddannelse.

HØHØ
Kan informer om at på en
MacBook Pro fall 08
4GB 1067 MHz DDR3 ram
2.8 GHz Intel Core 2 Duo

Kan gøre det på 4sek og svaret er: 501498
Hvis jeg ellers har kodet rigtigt

Hvad er det nøjagtigt, du har regnet ud på 4 sekunder?

sum af de først 1000 primes

System.out.println <-- er der ikke ret voldsom overhead ved at skrive til en terminal konstant?
Oggg nu vi er igang, så har implementationen af java en del at sige + at en virtuel maskine er ungefair 10 gange langsommere end compilet kode, hvorfor er det vi ikke laver et c-program? :P


#! /usr/bin/env python3

def calcFromAtoB(a, b):
sum = 0
while (a <= b):
print(a)
sum += a
a = a + 1

x = ((2**64) / 2) - 1
calcFromAtoB(0, x)


Mit er skrevet i Python 3 og sat i kog her kl. 20:27.

Debian Testing

Jeg kan Ikke lige huske specs på min pc dog. Men en lille fin 12" packard bell - ca, 1½ år gammel.

Skrevet i c - den burde gøre det du specificere og den burde ikke lave overflow, men giver ingen garantier :P
Skal compiles med gcc eller andet der understøtter long long...

#include
#include
#include

int main(int argc, char *argv[])
{
unsigned long long int a,b,c;
a = 0;
b = (pow(2,64)/2)-1;
c = 0;
while(a <= b){
c += a;
a++;
printf("%lld\n",a);
}
exit(0);
}


#9 der er da vist noget grueligt galt med din macbook, (eller dine kodeevner) hvis det skal tage 4 sekunder

[brian@Lapdog ~]$ time python 1kprimesum.py
3682913

real 0m0.217s
user 0m0.167s
sys 0m0.007s


og kildekoden er her


#!/usr/bin/env python
import math
def is_prime(number):
if number <= 1: return False
if number == 2: return True
if number % 2 == 0: return False
root = math.ceil(math.sqrt(number))+1
for test in range(2,root):
if number % test == 0: return False
return True

primesum = 0
primes = 0
testme = 0
while primes < 1000:
if is_prime(testme):
primesum += testme
primes += 1
if(testme <= 2): testme += 1
else: testme += 2
print(primesum)


Når den er færdig, skal verdenskortene nok tegnes om. :-)

Jeg kørte dit script (Python 2.6.1, Core 2 Duo, 2.26 GHz) med x=2²⁴/2-1 for at blive færdig i dag.
Uden print statementet tog det 3,52 s, og med tog det 142,9 s.
Skaleret til x=2³²/2-1 er det hhv. 901s og 36575s ~ 10 timer. Som det ses, bruges det meste af tiden til at printe.

For sammenligningens skyld prøvede jeg også med Forth (Gforth 0.6.2), hvilket uden print tog 30s til x=2³²/2-1
( -1 1 rshift giver $7FFFFFFF = 2³²/2-1 )
: Test 0. -1 1 rshift 0 DO I s>d D+ LOOP ;

Test cr D.
2305843005992468481

For at køre til 2⁶⁴/2-1 skal man gange tiden med 2³².
Go figure.

@16 gik ud fra hvad eclipse sagde og har lige kørt det igen:
Start: 7:44:06
Stop: 7:44:10

#18, det ændrer ikke på at det tager 20x længere tid for dit java program på en c2d@2,8GHz, hhv mit python script kørt på en pentium M @1.6 GHz

Retfærdigvis skal det siges at det tager ~1,5 sek hvis jeg rydder cachen inden scriptet eksekveres, men det viser bare at jeg har en ufattelig langsom harddisk.

EDIT:
Men nu viser #17 jo også hvor meget et print statement koster, så hvis din ikke offentliggjorte prime kode spytter 1000 prints ud, så kan det være at pengene passer.

Nå så er det min tur til at komme med tallene. Jeg valgte dog fra start af at bruge en noget anderledes algortime for at vise at den her test bare er idiotisk eftersom vi ikke alle sammen bruger samme program med samme algoritme i samme programmeringssprog. Men fair nok.

Test foretaget på en 700 Mhz Pentium III med 256 MB ram:
[julemand101@DOLPH ~]$ time java PrimeMain
3682913

real 0m0.344s
user 0m0.263s
sys 0m0.077s

Test foretaget på en Intel Core i5 med 2.80 GHZ med 16 GB ram:
julemand@servi:~$ time java PrimeMain
3682913

real 0m0.064s
user 0m0.040s
sys 0m0.020s

Programmet er skrevet i Java og kører helt sikkert meget hurtigere hvis det blev skrevet i C men nu havde jeg lige koden liggende efter en Euler Opgave. Koden kan ses her:

public class PrimeMain {

public static void main(String[] args) {
int limit = 8000;
int sievebound = (limit - 1) / 2;

boolean[] sieve = new boolean[sievebound];

int crosslimit = ((int)Math.floor(Math.sqrt(limit)) - 1) / 2;

for (int i = 1; i <= crosslimit; i++) {
if (!sieve[i]) {
for (int j = 2*i*(i+1); j < sievebound; j += 2*i+1) {
sieve[j] = true;
}
}
}
int count = 1;
int sum = 2;
for (int i = 1; count < 1000; i++) {
if (!sieve[i]) {
sum += 2*i+1;
count++;
}
}

System.out.println(sum);
}
}
Det eneste besværlige er lige at finde frem til limit variablen. Algoritmen bygger på sieve algoritmen og er derfor således lavet til at finde alle primtal mellem 2 og n. Eftersom opgaven går ud på at finde summen på de første 1000 primtal skal der lige findes frem til en passende limit hvilket kan gøres ved at lave den meget stor og så se hvor stor i er når den har fundet de første 1000 primtal.

Okay så den computer som jeg havde til at regne summe af tal i 63 bit er gået ned på grund af det - eller retter andtager det er pga. det ^_^