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 ^_^