priemgetallen

woensdag 14 maart 2001 19:27

Nu ben ik benieuwd of iemand dit kan porten naar een pc-programma, en eens wil kijken hoe snel een pc erover doet om de eerste 22.000 priemgetallen te bereken. Wie durft?

Ik heb 't even in Delphi gedaan: 1 seconde op een celly 523.

Acties:

Witlof

Op Wednesday 14 March 2001 19:20 schreef Onno het volgende:

[..]

Ik heb 't even in Delphi gedaan: 1 seconde op een celly 523.

En wat heeft Onno nou gewonnen?

woensdag 14 maart 2001 19:37

Acties:

Geckoo

Good news, everyone!

Een koelkast??

Professor Hubert Farnsworth: Shut up friends.
My internet browser heard us saying the word Fry and it found a movie about Philip J. Fry for us. It also opened my calendar to Friday and ordered me some french fries.

woensdag 14 maart 2001 19:55

Acties:

Verwijderd

En?
Zou hij door gaan voor de auto?

Je kan trouwens ergens ik geloof $100.000 (of $1.000.000:9) winnen als je eenpriemgetal uitrekent met een bepaald aantal cijfers.

woensdag 14 maart 2001 20:01

Acties:

woensdag 14 maart 2001 20:08

Devver

Pixelated

Topicstarter

Op Wednesday 14 March 2001 19:55 schreef matthijs1985 het volgende:
En?
Zou hij door gaan voor de auto?

Je kan trouwens ergens ik geloof $100.000 (of $1.000.000:9) winnen als je eenpriemgetal uitrekent met een bepaald aantal cijfers.

idd; 100.000 dollar als je een priemgetal vind met meer dan 10 miljoen cijfers.
Onno: laat maar ff doorlopen dus!

Intentionally left blank

Acties:

woensdag 14 maart 2001 20:09

Ja doei, dat kan ik m'n koetje echt niet aandoen hoor!

Acties:

woensdag 14 maart 2001 20:27

Devver

Pixelated

Topicstarter

Op Wednesday 14 March 2001 19:20 schreef Onno het volgende:

[..]

Ik heb 't even in Delphi gedaan: 1 seconde op een celly 523.

Zo blijkt maar weer eens hoe slecht een AS/400 in rekenen is.. Wat dat betreft vind ik het niet erg dat er nog geen koe voor is; zou toch weinig opleveren.
ff strikvraag voor Onno: wat was het grootste priemgetal vlak voor de 250.000???
En kan je de source ook ff posten (ben zelf niet bekent met Delphi)?

Intentionally left blank

Acties:

woensdag 14 maart 2001 20:37

249989

code:

var
  priem:array[1..100000] of integer;
  priemen:integer;
  i,n,d,p:integer;
begin
  pr[1]:=2;
  pr[2]:=3;
  priemen:=2;
  n:=pr[priemen];
  while (n<250000) do begin
    inc(n,2);
    i:=1;
    d:=1;
    p:=n;
    while ((d>0) and (p > pr[i])) do begin
      inc(i);
      p:=n div priem[i]; // deze twee regels zouden in
      d:=n mod priem[i]; // asm in 1x kunnen :)
    end;
    if (d>0) then begin
      inc(priemen);
      priem[priemen]:=n;
    end;
  end;
end.

Acties:

Verwijderd

Nevermind...

woensdag 14 maart 2001 21:38

Acties:

woensdag 14 maart 2001 22:51

Devver

Pixelated

Topicstarter

Onno: helemaal correct.
Ik zie echter wel een duidelijk verschil dat het verschil in performance verklaart: jij maakt gebruik van een array, waar ik gebruik maak van een fysiek (en keyed) bestand, Disk i/o vreet natuurlijk een groot stuk performance, en daar heeft jouw programma geen last van.
Eerste stap in optimalisatie van mijn programma zou zijn om het bestand niet keyed te benaderen (hij wordt toch in sequence gevuld); op deze manier kan een AS/400 vele records met 1 i/o bufferen (4K buffer).
Ik wil sowieso een bestand hebben om later op een bepaald punt door te kunnen gaan.
Tweede stap zou zijn om ook gebruik te maken van arrays. Nadeel is dat in gewoon RPG een array maar 9.999 entries kan bevatten (in ILE-RPG max 32.767 entries). Je moet dus arrays gaan 'swappen' op een gegeven moment. Een andere manier van berekenen is dan noodzakelijk om veelvuldig swappen tegen te gaan (een soort 'slices' maken).
Ander probleem is dat op een gegeven moment zelfs een long integer te klein wordt om de getallen op te slaan; dan moet je echt rudimentair gaan rekenen en de getallen als strings op gaan slaan....
Enfin, ik ga er nog een nachtje over slapen...

Intentionally left blank

Acties:

[eNeRGy]

Waarom denk je dat bij het project Prime95 de client er soms 60 uur over doet over 1 blokje...

donderdag 15 maart 2001 00:41

Acties:

Verwijderd

ongeveer 0.5 sec of minder op mijn tb700@850, en dan heb ik 'm nog niet eens geoptimaliseert (hij loopt nog alle getallen bij langs)
maar ach wat het nut er van is, er zijn al gigantisch grote priemgetallen gezocht, de enige manier om er een wedstrijd van te maken is, is door meerdere teams dezelfde priemgetallen op te laten zoeken en de gene die als eerst bij 100000000000000000000000000000000000000000000000000000000 is heeft gewonnen.
het klinkt raar maar dat is volgens mij de enige manier om er een wedstrijd van te maken, maar dat is weer niet interessant voor de wedstrijdleiders.

Je kan het idd ook weer dmv blokjes doen, maar in de blokjes komen steeds grotere getallen voor waardoor het steeds langer duurt om het op te lossen. Ok de processoren worden steeds sneller, maar ook dat houdt op den duur op en dan zie je je aantal blokjes alleen nog maar dalen, niet erg bevordelijk lijkt mij.

donderdag 15 maart 2001 08:05

Acties:

donderdag 15 maart 2001 10:08

Devver

Pixelated

Topicstarter

Het gaat mij eigenlijk helemaal niet om die priemgetalletjes, maar gewoon puur om een proggie te maken dat ze zo efficient mogelijk kan berekenen.
Ik hou gewoon van korte efficiente proggies

Intentionally left blank

Acties:

0rbit

Koop dan eerst een boek Assembly

Ik ben geheel voldaan, dank u wel!

donderdag 15 maart 2001 10:22

Acties:

Grrrrrene

Op Thursday 15 March 2001 00:41 schreef hitsnoopy het volgende:
ongeveer 0.5 sec of minder op mijn tb700@850, en dan heb ik 'm nog niet eens geoptimaliseert (hij loopt nog alle getallen bij langs)
maar ach wat het nut er van is, er zijn al gigantisch grote priemgetallen gezocht, de enige manier om er een wedstrijd van te maken is, is door meerdere teams dezelfde priemgetallen op te laten zoeken en de gene die als eerst bij 100000000000000000000000000000000000000000000000000000000 is heeft gewonnen.
het klinkt raar maar dat is volgens mij de enige manier om er een wedstrijd van te maken, maar dat is weer niet interessant voor de wedstrijdleiders.

Je kan het idd ook weer dmv blokjes doen, maar in de blokjes komen steeds grotere getallen voor waardoor het steeds langer duurt om het op te lossen. Ok de processoren worden steeds sneller, maar ook dat houdt op den duur op en dan zie je je aantal blokjes alleen nog maar dalen, niet erg bevordelijk lijkt mij.

100000000000000000000000000000000000000000000000000000000 slaat hij vrolijk over

Imitation is the sincerest form of flattery
Stressed is desserts spelled backwards

donderdag 15 maart 2001 16:51

Acties:

Verwijderd

Nou als je minstens een bepaalde lengte moet hebben kan je net zo goed daar beginnen... en de rest niet doen... Schiet volgens mij meer op ....

[test modus]
1 = priem (volgens mij is dit niet priem)
2 = priem
3 = priem (2 + 1)
5 = priem (3 + 2)
7 = priem (5 + 2)
11 = priem (5 + 3 + 2 + 1)
13 = priem (7 + 3 + 2 + 1)
17 = priem (7 + 5 + 3 + 2)
23 = priem (11 + 7 + 3 + 2)
29 = priem (11 + 7 + 5 + 3 + 2 + 1)
[test modus]

aantal regels:
1. bij oneven aantal priem getallen + 1
2. uhm uhm...

Zit hier een logica in??? Zoja. dan kom je er volgens mij veel sneller. Ben benieuwd wat er hier op wordt gereageert.

donderdag 15 maart 2001 17:02

Acties:

donderdag 15 maart 2001 17:06

Om te onderzoeken of een getal p priem is, is het wel een stuk efficienter om als mogelijke delers de getallen tot en met sqrt(p) te bekijken (in plaats van dus alle getallen kleiner dan p te onderzoeken).

Acties:

Verwijderd

sqrt(b) en dat doet???
de wortel???

Maar bij hele grote wordt dat toch anders

donderdag 15 maart 2001 17:07

Acties:

donderdag 15 maart 2001 17:09

Op Thursday 15 March 2001 16:51 schreef volcano[gbb] het volgende:
Nou als je minstens een bepaalde lengte moet hebben kan je net zo goed daar beginnen... en de rest niet doen... Schiet volgens mij meer op ....

[test modus]
1 = priem (volgens mij is dit niet priem)
2 = priem
3 = priem (2 + 1)
5 = priem (3 + 2)
7 = priem (5 + 2)
11 = priem (5 + 3 + 2 + 1)
13 = priem (7 + 3 + 2 + 1)
17 = priem (7 + 5 + 3 + 2)
23 = priem (11 + 7 + 3 + 2)
29 = priem (11 + 7 + 5 + 3 + 2 + 1)
[test modus]

aantal regels:
1. bij oneven aantal priem getallen + 1
2. uhm uhm...

Zit hier een logica in??? Zoja. dan kom je er volgens mij veel sneller. Ben benieuwd wat er hier op wordt gereageert.

Lees http://www.utm.edu/research/primes/glossary/GoldbachConjecture.html maar eens. Het vermoeden van Goldbach zegt dat elk even getal groter dan 2 de som is van 2 priemgetallen. Oftewel, elk oneven getal groter dan 3 is de som van 2 priemgetallen + 1.

Acties:

donderdag 15 maart 2001 18:16

Op Thursday 15 March 2001 17:06 schreef volcano[gbb] het volgende:
sqrt(b) en dat doet???
de wortel???

Maar bij hele grote wordt dat toch anders

Ga maar na: stel p is niet priem. Dan geldt dus p=a*b. Dan geldt of a<=sqrt(p), of b<=sqrt(p), of a=b=sqrt(p).

Ik kan het wel met een voorbeeld verduidelijken als je dat wilt.

Acties:

Verwijderd

Op Thursday 15 March 2001 17:09 schreef Upquark het volgende:

[..]

Ga maar na: stel p is niet priem. Dan geldt dus p=a*b. Dan geldt of a<=sqrt(p), of b<=sqrt(p), of a=b=sqrt(p).

Ik kan het wel met een voorbeeld verduidelijken als je dat wilt.

Nou..... je kan een hoop voorbeelden erbij zetten... maar mij zijn jullie alang kwijt

donderdag 15 maart 2001 19:26

Acties:

donderdag 15 maart 2001 20:31

Devver

Pixelated

Topicstarter

Op Thursday 15 March 2001 17:02 schreef Upquark het volgende:
Om te onderzoeken of een getal p priem is, is het wel een stuk efficienter om als mogelijke delers de getallen tot en met sqrt(p) te bekijken (in plaats van dus alle getallen kleiner dan p te onderzoeken).

Dat is ook precies wat mijn programma doet.
Ik heb btw vandaag ff getest met een array, en alleen een bestand gebruikt voor output. Die AS/400 deed er toen nog maar 4 seconden over. Zonder output naar bestand nog maar 2 seconden, en dat terwijl er 100 man op die bak werkt

Worteltrekken is trouwens ook een leuke uitdaging. Hoe bepaal je nl de wortel van een getal, en wat is de meest efficiente manier om dat te berekenen met zoveel mogelijk cijfers achter de comma.

Ik heb daar vandaag een proggie voor gemaakt dat gemiddeld 34 iteraties nodig had voor een precisie van 8 cijfers achter de comma, nog niet echt efficient dus. Plus dat ik delingen gebruik, wat nogal zwaar is voor een computer.

Intentionally left blank

Acties:

Verwijderd

klinkt als typisch iets waar een mac goed in is...

donderdag 15 maart 2001 20:39

Acties:

donderdag 15 maart 2001 20:47

Ik heb hier nog niet 't efficienste algorithme gezien. Misschien moeten de heren eens Knuth gaan lezen

Je wilt weten of N een priemgetal is doe je door N te testen op alle priemgetallen tot INT(sqrt(N)). Dus als je wilt weten of 29 priem is: INT(sqrt(29)) = 5

29 mod 2 = 1
29 mod 3 = 2
29 mod 4 HOEFT NIET (want zit al in 2)
29 mod 5 = 4

Verder hoef je niet te gaan.

Dit staat bekend als the Sieve en is voor computers alleen handig om *alle* priemetjes te berekenen tot een bepaalde grote.

Mersene primes zijn 2^n-1 primes daarvoor zijn andere algorithmen nodig, je wilt alleen weten of *dat* nummertje priem is zonder alle priemgetallen tot sqrt(2^n-1) te bekrenene.

Meer informatie over Sieve een een nog efficientere binary_quadratic op:

http://primes.utm.edu/links/programs/sieves/binary_quadratic/

Acties:

donderdag 15 maart 2001 20:51

Devver

Pixelated

Topicstarter

Op Thursday 15 March 2001 20:39 schreef Theswitch het volgende:
Ik heb hier nog niet 't efficienste algorithme gezien. Misschien moeten de heren eens Knuth gaan lezen

Je wilt weten of N een priemgetal is doe je door N te testen op alle priemgetallen tot INT(sqrt(N)). Dus als je wilt weten of 29 priem is: INT(sqrt(29)) = 5

29 mod 2 = 1
29 mod 3 = 2
29 mod 4 HOEFT NIET (want zit al in 2)
29 mod 5 = 4

Verder hoef je niet te gaan.

Dit staat bekend als the Sieve en is voor computers alleen handig om *alle* priemetjes te berekenen tot een bepaalde grote.

Mersene primes zijn 2^n-1 primes daarvoor zijn andere algorithmen nodig, je wilt alleen weten of *dat* nummertje priem is zonder alle priemgetallen tot sqrt(2^n-1) te bekrenene.

Meer informatie over Sieve een een nog efficientere binary_quadratic op:

http://primes.utm.edu/links/programs/sieves/binary_quadratic/

Als je goed kijkt dan zie je dat mijn proggie dus WEL deze methode gebruikt. Ik test namelijk of er idd een restgetal is na deling, en stop met testen zodra het resultaat van de deling kleiner is dan de deler zelf of als er een deling mogelijk is zonder rest (geen priem). Ik doe dus eigenlijk 1 deling teveel, maar dat is imho effectiever dan eerst de wortel te moeten trekken om te kijken waar je op moet houden met delen (delen is sneller dan worteltrekken op een computer).

29 mod 2 = 1

is trouwens ook overbodig, na het getal 2 hoef je nl alleen nog maar de oneven nummers te checken; ik doe dat door N telkens met 2 op te hogen. Eigenlijk kan je na het getal 5 ook alle cijfers die eindigen op 5 overslaan, is nog effectiever (anders zou je 'm eerst door 3 delen, en dan nog eens door 5 en er dan pas achter komen dat het toch geen priem is).

Intentionally left blank

Acties:

Verwijderd

Op Thursday 15 March 2001 19:26 schreef crisp het volgende:

[..]

Dat is ook precies wat mijn programma doet.
Ik heb btw vandaag ff getest met een array, en alleen een bestand gebruikt voor output. Die AS/400 deed er toen nog maar 4 seconden over. Zonder output naar bestand nog maar 2 seconden, en dat terwijl er 100 man op die bak werkt

Worteltrekken is trouwens ook een leuke uitdaging. Hoe bepaal je nl de wortel van een getal, en wat is de meest efficiente manier om dat te berekenen met zoveel mogelijk cijfers achter de comma.

Ik heb daar vandaag een proggie voor gemaakt dat gemiddeld 34 iteraties nodig had voor een precisie van 8 cijfers achter de comma, nog niet echt efficient dus. Plus dat ik delingen gebruik, wat nogal zwaar is voor een computer.

source!!! source!!! source!!!

donderdag 15 maart 2001 20:58

Acties:

Burat

bos wortels

Doe dit in Haskell (http://www.haskell.org) en het gaat 10 keer zo snel en met een "oneindige" (naja) nauwkeurigheid (dwz: hij kapt het aantal cijfers niet af als het groter wordt dan x. Dus 100000000000000000000000 ipv 10e23.

Homepage | Me @ T.net | Having fun @ Procurios | Collega's gezocht: Webontwikkelaar PHP

donderdag 15 maart 2001 21:09

Acties:

donderdag 15 maart 2001 21:32

Devver

Pixelated

Topicstarter

Op Thursday 15 March 2001 20:51 schreef stefana3a_revision_3 het volgende:

[..]

source!!! source!!! source!!!

Zal het morgen ff meenemen...

Doe dit in Haskell (http://www.haskell.org) en het gaat 10 keer zo snel en met een "oneindige" (naja) nauwkeurigheid (dwz: hij kapt het aantal cijfers niet af als het groter wordt dan x. Dus 100000000000000000000000 ipv 10e23.

maximale integer lengte met RPG op AS/400 is 31 cijfers, max 9 achter de komma

Intentionally left blank

Acties:

donderdag 15 maart 2001 21:54

Op Thursday 15 March 2001 20:47 schreef crisp het volgende:

[..]
is trouwens ook overbodig, na het getal 2 hoef je nl alleen nog maar de oneven nummers te checken; ik doe dat door N telkens met 2 op te hogen. Eigenlijk kan je na het getal 5 ook alle cijfers die eindigen op 5 overslaan, is nog effectiever

neem 127 als voorbeeld:
delen door 2
delen door 3
delen door 5
delen door 7
delen door 11
Je hoeft dus niet door 9 te delen (anders was deze deelbaar door 3). Je hoeft dus alleen deelbaarheid op primes te testen. Het gaat om het algorithme, het idee, niet om het programma. Trouwens van de pagina uit m'n url:

Sieve of Atkins - This version generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.

Acties:

donderdag 15 maart 2001 22:46

Devver

Pixelated

Topicstarter

Op Thursday 15 March 2001 21:32 schreef Theswitch het volgende:

[..]

neem 127 als voorbeeld:
delen door 2
delen door 3
delen door 5
delen door 7
delen door 11
Je hoeft dus niet door 9 te delen (anders was deze deelbaar door 3). Je hoeft dus alleen deelbaarheid op primes te testen. Het gaat om het algorithme, het idee, niet om het programma. Trouwens van de pagina uit m'n url:

Sieve of Atkins - This version generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.

Maar als mijn programma nou precies hetzelfde doet (ik gebruik de opgeslagen priemgetallen weer als delers), dan gebruik ik toch hetzelfde algorithme? Dat een of andere Griek dat in 230 BC ook al had uitgevonden boeit me verder niet, ik vond het wel leuk dat ik er zelf opgekomen was...

Intentionally left blank

Acties:

Steven

Nog een tip, als een getal niet deelbaar is door de 3 is het ook niet deelbaar als alle cijfers van het getal bij elkaar opgeteld door drie te delen is

6458
6+4+5+8=23 is dus niet deelbaar door 3

6237
6+2+3+7=18 is dus deelbaar door 3

Voor getalleen onder de miljoen of zoiets is dit niet efficient, daarboven wel...

vrijdag 16 maart 2001 16:13

Acties:

Verwijderd

code:

        getallen[0] = 2;
        testgetal = 3;
        priemaantal = 1;
        while(priemaantal < 22000)
        {
            for(int i = 0;i<priemaantal;i++)
            {
                if(getallen[i]*getallen[i] < testgetal)
                {
                    if(testgetal % getallen[i] == 0)
                    {
                        i = priemaantal;
                    }
                }
                else
                {
                    getallen[priemaantal] = testgetal;
                    priemaantal++;
                    i = priemaantal;
                }
            }
            testgetal++;
        }

dit heb ik gebruikt voor het vinden van m'n priemgetallen. voor rezultaat zie /\/\/\

vrijdag 16 maart 2001 20:30

Acties:

vrijdag 16 maart 2001 21:02

Devver

Pixelated

Topicstarter

Source voor AS/400 (en andere freeware programma's voor AS/400) nu op mijn [url="http:://www.crisp.demon.nl/as400.htm"]website[/url]!

Intentionally left blank

Acties:

Verwijderd

Op Thursday 15 March 2001 22:46 schreef Steven_NL het volgende:
Nog een tip, als een getal niet deelbaar is door de 3 is het ook niet deelbaar als alle cijfers van het getal bij elkaar opgeteld door drie te delen is

6458
6+4+5+8=23 is dus niet deelbaar door 3

6237
6+2+3+7=18 is dus deelbaar door 3

Voor getalleen onder de miljoen of zoiets is dit niet efficient, daarboven wel...

okee we kunnen al best wat regeltjes maken dus om te controleren of het GEEN priemgetal is zonder het uit te rekenen.

1. Het optellen van de cijfers en kijken of dat deelbaar is door 3 (lijkt me inderdaad een stuk sneller bij grotere getallen)
2. als het getal eindigt op 2 (maarja we controlleren toch alleen maar de oneven getallen dus dit is niet erg boeiend
3. Als het getal eindigt op 5 (dan is het altijd deelbaar door 5), hiermaa valt al weer 10% van alle getallen af

Oja, ik heb nog iets verzonnen (misschien heeft iemand anders het allang verzonnen maar dat boeit even niet).
Maak een leuke database (een errug grote)
als je een getal hebt uitgerekent of het priem is of niet vermenigvuldig je dit met 6 ofzo tot en met je een resultaat hebt dat groter is dan tot het te zoeken priemgetal hebt).
Dit gooi je in een data baseje. Als je nu voor controleert of dat getal erin staat, bij het berekenen van het volgende priemgetal, dan weet je meteen of het een priemgetal is of niet als het erin voorkomt.
Meteen verwijderen daarna, want anders krijg je wel een erg grote database.

voordeel: Je sluit hier veel getallen mee uit, dus je kan sneller doorrekenen

nadeel: errug grote database nodig. (als we voor de 10miljoen decimalen, en de 100.000 dollar gaan).

vrijdag 16 maart 2001 21:29

Acties:

MeneerKrab

Ik zal eens ff gaan spitten in mijn pascal directory, daar hadden we zo'n proggie liggen die we op school hadden gemaakt.
slaat alle priem getalletjes op in een txt bestand.

vrijdag 16 maart 2001 21:35

Acties:

Verwijderd

Ik weet niet of dit al gezegd is maar.... volgens mij is de definitie van een priemgetal dat het alleen door zichzelf en door 1 deelbaar is dus dat maakt 2 dus geen priemgetal een 1 wel.

vrijdag 16 maart 2001 21:37

Acties:

Verwijderd

Op Wednesday 14 March 2001 18:50 schreef cyberax99 het volgende:
zoiets bestaat toch al??

Ja, dat programma heet Prime95 (heb het hier ergens op mijn HD), volgens mij is daar ook een contest van (geweest).

vrijdag 16 maart 2001 22:52

Acties:

vrijdag 16 maart 2001 23:20

Devver

Pixelated

Topicstarter

Op Friday 16 March 2001 21:35 schreef Hedeon het volgende:
Ik weet niet of dit al gezegd is maar.... volgens mij is de definitie van een priemgetal dat het alleen door zichzelf en door 1 deelbaar is dus dat maakt 2 dus geen priemgetal een 1 wel.

2 is ook alleen maar deelbaar door 2 en 1, dus is een priemgetal. 1 telt niet mee geloof ik (al weet ik niet waarom)...
En Prime95 bestaat volgens mij nog steeds; die zoeken Mersene primes.

Volcano: jij doelt een beetje op het principe van wegstrepen: je maakt een rij cijfers:
2-3-4-5-6-7-8-9-10 (1 doet niet mee)
Vervolgens neem je het eerste getal en streept alle veelvouden daarvan weg, dus krijg je:
2-3-5-7-9-10
Dan neem je het 2e getal en streept alle veelvouden weg, dus krijg je:
2-3-5-7-10
Zelfde met het 3e getal:
2-3-5-7-10
etcetera..
Voordeel is dat je geen delingen hoeft uit te voeren, maar je hebt idd een enorme DB nodig....

PowerCow: wordt wel een enorm textbestand dan

Intentionally left blank

Acties:

zaterdag 17 maart 2001 11:39

Devver

Pixelated

Topicstarter

Op Thursday 15 March 2001 20:51 schreef stefana3a_revision_3 het volgende:

[..]

source!!! source!!! source!!!

ok, is toch niet al te groot (nu met commentaar):

DDS

code:

********************************************************************************
      *
      *                  <<< P R I M E S >>>
      *
      * Author:  Tino Zijdel  14/03/2001
      * E-mail:  tino@crisp.demon.nl
      *
      * Compile options: set the inital number of records as high as
      * possible; the program will generate many records. Watch your
      * disk usage!!!!! e.g. use SIZE(*NOMAX) or just a high number
      * I calculated that 1 record is approx. 55 bytes, so
      * 1 milion records will occupy around 52.45 Mbytes
      *
***********************************************************************
      *  Record format
***********************************************************************
      *
     A                                      UNIQUE
     A          R PRREC
      *
     A            PRIME         30P 0       COLHDG('Prime')
     A          K PRIME

RPG:

code:

********************************************************************************
      *
      *                  <<< P R I M E S >>>
      *
      * Program:PRIMES - Calculate primes
      * Version: 01.00
      *
      * Author : Tino Zijdel  14/03/2001  tino@crisp.demon.nl
      *
      * Warning: will run a long time, and will create millions
      * of records!
      * It will test all numbers up to 10.000.000.000 for primality
      * My guess is that this will find approx. 900.000.000 primes
      * Finding all primes up to 250.000 took 3 seconds on my AS/400
      * (model 720 - single processor) during daytime (100 active
      * users). However, beyond that it will take more and more time
      * to test each number.
      * Letting this program actually test all the numbers up to
      * 10.000.000.000 will probably take days, and will generate
      * a file that is around 50 Gigabytes large!
      *
      *
***********************************************************************
      *
     FPRIMEF  IF  E           K        DISK                      A
     E                    PRIM     9999 15 0             CHECK PRIMES
     I            DS
     I                                        1  300N
     I                                       30  300CHK5
      *
      *Check file; fill array if file has contents
      * else write first 3 primes to file and start from there
      *
     C           *HIVAL    SETGTPRIMEF
     C                     READPPRIMEF                   03
     C           *IN03     IFEQ *ON
     C                     Z-ADD2         PRIME
     C                     WRITEPRREC
     C                     Z-ADD3         PRIME
     C                     WRITEPRREC
     C                     Z-ADDPRIME     PRIM,1
     C                     Z-ADD5         PRIME
     C                     WRITEPRREC
     C                     Z-ADDPRIME     PRIM,2
     C                     Z-ADD3         C       40
     C                     Z-ADDPRIME     N
     C                     ELSE
     C                     Z-ADDPRIME     N
     C                     Z-ADD1         C       40
     C           *LOVAL    SETLLPRIMEF
     C                     READ PRIMEF                   03
     C           *IN03     DOWEQ*OFF
     C           C         ANDNE0
     C                     Z-ADDPRIME     PRIM,C
     C                     ADD  1         C
     C                     READ PRIMEF                   03
     C                     ENDDO
     C                     ENDIF
      *
      *Using the array we can check N up to 10.000.000.000
      * because the largest check divider in the array is 104.729
      * (prime number 10.000 - we don't store 2 in the array)
      * thus N cannot be larger than 104.729^2
      *
     C           100000    MULT 100000    MAX    300
      *
     C           N         DOWLTMAX
      *
      *We start checking either with the last prime in the file,
      * or with number 5. Primes up from here are always uneven,
      * so we add 2 instead of 1 to the number to check.
      * also when the number to check ends with 5 we can skip it
      * (add 2 more)
      *
     C                     ADD  2         N
     C           CHK5      IFEQ 5
     C                     ADD  2         N
     C                     ENDIF
      *
     C                     Z-ADD1         DIFF   300
     C                     Z-ADDN         P      300
     C                     Z-ADD1         L       40
      *
      *DIFF is the remainder of dividing the check number with the
      * primes from the array. We can stop checking when DIFF is 0,
      * because than the check number can be evenly divided (so it is
      * not a prime). Also we can stop checking when the result of the
      * division (P) becomes greater than the divider; this means we
      * have checked all possible dividers upto SQRT(N). If this is
      * the case we have found a new prime.
      *
     C           DIFF      DOWNE0
     C           P         ANDGTPRIM,L
      *
     C           N         DIV  PRIM,L    P
     C                     MVR            DIFF
      *
     C                     ADD  1         L
      *
     C                     ENDDO
      *
      *Here we write the new prime to file, and if the array is not
      * fully filled yet, we also add it to the array.
      *
     C           DIFF      IFNE 0
     C                     Z-ADDN         PRIME
     C                     WRITEPRREC
     C           C         IFNE 0
     C                     Z-ADDN         PRIM,C
     C                     ADD  1         C
     C                     ENDIF
     C                     ENDIF
      *
     C                     ENDDO
      *
     C                     SETON                     LR

Ook hier te vinden als savefile met nog andere as/400 goodies!

Intentionally left blank

Acties:

Steven

Nog een (logische tip) alle getallen groter dan de helft van het te onderzoeken getal kan je ook wegsmijten. Maar dat hebben jullie volgens mij al in de proggies gezet...

zaterdag 17 maart 2001 11:51

Acties:

zaterdag 17 maart 2001 13:38

Devver

Pixelated

Topicstarter

Op Saturday 17 March 2001 11:39 schreef Steven_NL het volgende:
Nog een (logische tip) alle getallen groter dan de helft van het te onderzoeken getal kan je ook wegsmijten. Maar dat hebben jullie volgens mij al in de proggies gezet...

Sterker nog; alle getallen groter dan de wortel van het te onderzoeken getal kan je wegsmijten...

Intentionally left blank

Acties:

zaterdag 17 maart 2001 14:59

Op Friday 16 March 2001 23:20 schreef crisp het volgende:

* not a prime). Also we can stop checking when the result of the
* division (P) becomes greater than the divider; this means we
* have checked all possible dividers upto SQRT(N).

Hier kan ieder geval nog een optimalisatie.
Iedere keer delen is overbodig, je kan beter direct de sqrt(N) uitrekenen. Waarom? een worteltrekking kost wel iets meer als een deling, maar die hoeft maar 1x . de deling moet per getal voor alle dividers en is bij grotere getallen dus zeker zeer nadelig. Pas je proggie maar aan en kijk of het uitmaakt.

Acties:

zaterdag 17 maart 2001 17:26

Devver

Pixelated

Topicstarter

Op Saturday 17 March 2001 13:38 schreef Theswitch het volgende:

[..]

Hier kan ieder geval nog een optimalisatie.
Iedere keer delen is overbodig, je kan beter direct de sqrt(N) uitrekenen. Waarom? een worteltrekking kost wel iets meer als een deling, maar die hoeft maar 1x . de deling moet per getal voor alle dividers en is bij grotere getallen dus zeker zeer nadelig. Pas je proggie maar aan en kijk of het uitmaakt.

Voor elke nieuwe N moet je opnieuw de wortel bepalen. Mijn programma doet echter maar 1 deling teveel, maar hoeft geen wortel te bepalen. Wat is er dan effectiever?

Intentionally left blank

Acties:

Verwijderd

[quote]Op Friday 16 March 2001 22:52 schreef crisp het volgende:

[..]

Volcano: jij doelt een beetje op het principe van wegstrepen: je maakt een rij cijfers:
2-3-4-5-6-7-8-9-10 (1 doet niet mee)
Vervolgens neem je het eerste getal en streept alle veelvouden daarvan weg, dus krijg je:
2-3-5-7-9-10
Dan neem je het 2e getal en streept alle veelvouden weg, dus krijg je:
2-3-5-7-10
Zelfde met het 3e getal:
2-3-5-7-10
etcetera..
Voordeel is dat je geen delingen hoeft uit te voeren, maar je hebt idd een enorme DB nodig....

[/qoute]

Dit is dus precies wat Erasthotanes (hoe schrijf je dat nu toch

)bedacht had. De eerder gegeven programma's zijn allemaal mogelijke implementaties hiervan.

Wisten jullie trouwens dat 2999999 een priemgetal is?

zaterdag 17 maart 2001 19:30

Acties:

zaterdag 17 maart 2001 20:08

Op Saturday 17 March 2001 14:59 schreef crisp het volgende:

[..]

Voor elke nieuwe N moet je opnieuw de wortel bepalen. Mijn programma doet echter maar 1 deling teveel, maar hoeft geen wortel te bepalen. Wat is er dan effectiever?

Stel je moet voor 2999999 bepalen of het priem is:

A: Je trekt de wortel uit 299999 (=1732)
B:
2999999/3
2999999/5
2999999/7
2999999/11
...
2999999/1731 (ofzo)

Zoals je ziet, voor 1 getal is het of 1x een wortel of x* een deling. Dus 1x worteltrekken is altijd effectiever als x* een deling (hoe hoger het getal, hoe efficienter)

Acties:

zaterdag 17 maart 2001 23:06

* It will test all numbers up to 10.000.000.000 for primality
* My guess is that this will find approx. 900.000.000 primes

Het aantal priemen tussen 1 en n is ongeveer n/(ln n).

Acties:

zaterdag 17 maart 2001 23:08

Devver

Pixelated

Topicstarter

Op zaterdag 17 maart 2001 19:30 schreef Theswitch het volgende:

[..]

Stel je moet voor 2999999 bepalen of het priem is:

A: Je trekt de wortel uit 299999 (=1732)
B:
2999999/3
2999999/5
2999999/7
2999999/11
...
2999999/1731 (ofzo)

Zoals je ziet, voor 1 getal is het of 1x een wortel of x* een deling. Dus 1x worteltrekken is altijd effectiever als x* een deling (hoe hoger het getal, hoe efficienter)

De kans dat het getal kwadratisch is (dat wil zeggen dat er na worteltrekken een reeel getal uitkomt) is vele malen kleiner dan dat het bv deelbaar is door 3. Door te beginnen met checken op deelbaarheid met kleine factoren elimineer je de meeste getallen sneller IMHO. Als nl blijkt dat na worteltrekken het getal niet geelimineerd kan worden, dan moet je alsnog delingen uit gaan voeren.
In dit geval zal ik getal 2999999 delen door alle priemgetallen t/m 1733 (wortel uit 2999999 is 1732,0505...; 1733 is de daaropvolgende priem)
2999999 / 1733 = 1731,1015... - nu is het resultaat van de deling kleiner dan de deler, dus als alle andere delingen ook geen reeel getal hebben opgeleverd is het een priem.
(2999999 is idd priem)

Intentionally left blank

Acties:

zondag 18 maart 2001 12:17

Devver

Pixelated

Topicstarter

Op zaterdag 17 maart 2001 20:08 schreef Onno het volgende:

[..]

Het aantal priemen tussen 1 en n is ongeveer n/(ln n).

Dan zat ik er maar een factor 2 naast: 10.000.000.000 / (ln 10.000.000.000) = 434.294.481,9032...

Intentionally left blank

Acties:

zondag 18 maart 2001 12:51

Op zaterdag 17 maart 2001 23:06 schreef crisp het volgende:

[..]

De kans dat het getal kwadratisch is (dat wil zeggen dat er na worteltrekken een reeel getal uitkomt)

Daar gaat het hier helemaal niet om. Het gaat om de *kosten* van het programma voor een wortelfunctie of een deelfunctie.

Ben je met me eens dat je voor uitrekenen van 1 getal of het priem is je maar 1 wortel moet doen en x* een deelfunctie. Zie je ook in dat hoe duur(veel tijd) een wortelfunctie ook kost, door de factor x* die in de deeloperatie zit dit altijd duurder is uiteindelijk.

Als je dit niet vind.. Graag een onderbouwd bewijsje ofzo, IMHO = geen bewijs.

Acties:

Gizmo_mokum

waarom wil je wortels met 8 cijfers achter de komma berekenen, met 1 cijfer achter de komma weet je ook al waar je berekeningen mogen stoppen, je moet alleen integers aftesten, dus voegen die extra honderdsten niets meer toe.

zondag 18 maart 2001 13:39

Acties:

zondag 18 maart 2001 13:52

Devver

Pixelated

Topicstarter

Op zondag 18 maart 2001 12:17 schreef Theswitch het volgende:

[..]

Daar gaat het hier helemaal niet om. Het gaat om de *kosten* van het programma voor een wortelfunctie of een deelfunctie.

Ben je met me eens dat je voor uitrekenen van 1 getal of het priem is je maar 1 wortel moet doen en x* een deelfunctie. Zie je ook in dat hoe duur(veel tijd) een wortelfunctie ook kost, door de factor x* die in de deeloperatie zit dit altijd duurder is uiteindelijk.

Als je dit niet vind.. Graag een onderbouwd bewijsje ofzo, IMHO = geen bewijs.

De enige toegevoegde waarde van het bepalen van de wortel voordat je testdelingen gaat uitvoeren is dat je van te voren weet tot welke deler je hoeft te gaan. De kans dat je het getal mbv een wortel al meteen kunt uitsluiten is minimaal (maar is volgens mij ook niet jouw bedoeling).
Mijn programma bepaalt geen wortel, en dus weet ik van te voren niet wanneer ik niet meer verder hoef te delen. Ik bepaal dat wanneer het resultaat van de deling kleiner is dan de deler zelf dat ik niet meer verder hoef te gaan.
Op dat moment heb ik dus 1 deling teveel gedaan - immers, had ik van tevoren de wortel bepaald dan had ik geweten dat de laatste deling overbodig was omdat de deler groter was dan de wortel van het te testen getal.
Kortom: de keus is of 1 keer extra delen, of van te voren de wortel bepalen.

Probleem is: een wortel bepalen bestaat normaal gesproken ook uit testdelingen. Het ligt eraan hoe slim je je begin getal bepaalt, en hoeveel cijfers je achter de komma wilt. Ik heb eens een programma gemaakt dat gemiddeld 34 delingen moest doen om een wortel te bepalen met 8 cijfers achter de komma.
Zelfs als je maar 1 of zelfs 0 decimalen nodig hebt voor de wortel zul je toch een aantal delingen moeten uitvoeren (een AS/400 heeft sowieso geen wortel functie).

Ergo: ik kies liever voor 1 extra (overbodige) deling, dan voor het vantevoren bepalen van de wortel omdat die ene extra deling het qua performance wint.

Er zijn trouwens ook andere manier om wortel te trekken (mbv tabellen), maar zelfs dan is een deling volgens mij sneller.

edit:

Nog 1 keer ter verduidelijking (en hopelijk overtuigend bewijs):
Op het moment dat het resultaat van een testdeling kleiner is dan de deler dan wil dat zeggen dat ik zojuist de wortel ben gepasseert.
eg; de wortel van 101 is grofweg 10
Als je dit vantevoren bepaalt dan test je dit getal dus door te delen door 2,3,5 en 7
de volgende priem is 11, dus stop je zonder die deling uit te voeren.
Ik bepaal geen wortel, en doe dus wel de deling door 11:
101 / 11 = 9,1818...
Het resultaat van deze deling is kleiner als de deler (11), dus hier stop ik met delingen.

Intentionally left blank

Acties:

zondag 18 maart 2001 21:17

Op zondag 18 maart 2001 13:39 schreef crisp het volgende:

[..]

De enige toegevoegde waarde van het bepalen van de wortel voordat je testdelingen gaat uitvoeren is dat je van te voren weet tot welke deler je hoeft te gaan.

En dat is ook het enige wat je *wil* weten.

Zelfs als je maar 1 of zelfs 0 decimalen nodig hebt voor de wortel zul je toch een aantal delingen moeten uitvoeren (een AS/400 heeft sowieso geen wortel functie).

een paar delingen ja.

Ergo: ik kies liever voor 1 extra (overbodige) deling, dan voor het vantevoren bepalen van de wortel omdat die ene extra deling het qua performance wint.

Nu mijn vraag: Waarom zou je uberhaupt nog willen delen, als je al weet tot hoe ver je moet? Je hoeft alleen maar de rest te weten (= een andere functie). JE wilt niet eens meer delen, aangezien je toch al weet hoe ver je moet.

Dus de deling kan dan helemaal wegvallen en hoef je alleen maar de MOD te bepalen.

(Kijken hoe lang dit nog doorgaat

)

Acties:

Verwijderd

Op zondag 18 maart 2001 13:39 schreef crisp het volgende:

[..]

Probleem is: een wortel bepalen bestaat normaal gesproken ook uit testdelingen. Het ligt eraan hoe slim je je begin getal bepaalt, en hoeveel cijfers je achter de komma wilt. Ik heb eens een programma gemaakt dat gemiddeld 34 delingen moest doen om een wortel te bepalen met 8 cijfers achter de komma.

Erhm, je kan een wortel ook berekenen door (bijna) alleen gebruik te maken van optellen, dat zou ik alleen ff na moeten kijken hoe dat ook alweer moest. Het komt er in ieder geval op neer dat je geen gebruik maakt van delen, maar alleen van optellen en vermenigvuldigen.

En bovendien gaat dat ook nog verdomde snel. Ik zeg dit nu wel allemaal uit m'n hoofd, maar als je echt bewijs wilt kan ik het nog wel 'ns nakijken in m'n college aantekeningen /boek van dat vak.

zondag 18 maart 2001 21:39

Acties:

geintje

=| zeiken met een glimlach |=

Op woensdag 14 maart 2001 18:26 schreef crisp het volgende:
Ik heb dit dus geprogrammeerd in RPG op een AS/400 (720 - single processor), en binnen 2 minuten had ik al alle priemgetallen tussen de 0 en 250.000 (dat zijn er 22.044).
Nu is een AS/400 geen rekenwonder, maar ik vond het toch best snel gaan.

Klopt een beetje..van origine is AS400 een database machine.. ( nog steeds eigenlijk)
maar---- in 720 zit net als zijn RS6000 broers/zussies een RISC processor..
en dus met deze processor kan AS400 ook best een stukkie rekenen.. helaas voorRC5/OGR draaien ze op OS400 en daar is geen client voor. ( en draaien op ene IPCS is zinloos ..die kaart heeft eigen processor en gebruikt rekenkracht AS400 processor niet !)

de nieuwere modellen ( 8xx) zijn zelfs de AS400 /RS6000 qua hardware nagenoeg identiek)

wel jammer... ik zou best een paar machientjes weten die zouden kunnen gaan reken ):O

/edit mode
f**king toetsenbord..of toch dikke vingers ?? *lol*
/end edit mode

________________________Team ColdFusion________________________
#1 DPAD, #1 OGR-27, #2 F@H, #4 RC5, #18 WCG

maandag 19 maart 2001 00:34

Acties:

maandag 19 maart 2001 08:11

Als iemand soms op zoek was naar een contest voor het zoeken naar priemgetallen: www.mersenne.org/prime.htm

Van hieruit ook veel informatie over priemgetallen in het algemeen, etc.

Acties: