Raar priem-idee...?

[Onno Dekker]

als ik wat schrijf gebruik ik C en dir zijn wat macro's die je in een
functie kunt gebruiken om te werken met priemgetallen binnen 32 of 64 bits.
Voorbeeld:
/*
descr: get next higher primenumber between lowest and largest prime number
input: any real odd number
rtval: next primenumber or zero on out of 32 bits space
nbugs: not known
revis: 0.7
mores:
autor: copyright ing. J. Onno Dekker 1972-2020
*/
static unsigned int nextprimenumber(unsigned int p)
{ p |= 1ul; // only odd prime numbers

if (p >= MAXPRIME) // prevents forever out of border
return 0ul;

nextprime(p); // ret thanks to above always new p
}

Het lijkt wat goor om dergelijke macro's te gebruiken, maar het werkt en is betrouwbaar als je maar publieke en beschermde code scheidt. Bij primes is het wel zo fijn om weinig tijd te verliezen in
dure functie calls; vandaar de oneliners die het doen.

Onno

[Onno Dekker]

als ik wat schrijf gebruik ik C en dir zijn wat macro's die je in een
functie kunt gebruiken om te werken met priemgetallen binnen 32 of 64 bits.
Voorbeeld:
/*
descr: get next higher primenumber between lowest and largest prime number
input: any real odd number
rtval: next primenumber or zero on out of 32 bits space
nbugs: not known
revis: 0.7
mores:
autor: copyright ing. J. Onno Dekker 1972-2020
*/
static unsigned int nextprimenumber(unsigned int p)
{ p |= 1ul; // only odd prime numbers

if (p >= MAXPRIME) // prevents forever out of border
return 0ul;

nextprime(p); // ret thanks to above always new p
}

Het lijkt wat goor om dergelijke macro's te gebruiken, maar het werkt en is betrouwbaar als je maar publieke en beschermde code scheidt. Bij primes is het wel zo fijn om weinig tijd te verliezen in
dure functie calls; vandaar de oneliners die het doen.

Onno


sorry forgot macro for above code:
# define nextprime(P) unsigned int I; for(;;) { uptoprime(I,P); if (I == P) return P;} error("nextpr")
# define echoprime(P) unsigned int I; isprime(I,P); return I
# define prevprime(P) unsigned int I; for(;;) {downtoprime(I,P); if (I == P) return P;} error("prevpr")

# define uptoprime(I,P) for(P+=2ul, I=3ul; P%I && I < P/I; I += 2ul); I = (P%I == 0ul && P != 3ul)?(P/I):P
# define isprime(I,P) for( I=3ul; P%I && I < P/I; I += 2ul); I = (P%I == 0ul && P != 3ul)?(0ul):P
# define downtoprime(I,P) for(P-=2ul, I=3ul; P%I && I < P/I; I += 2ul); I = (P%I == 0ul && P != 3ul)?(P/I):P

[EvilBro]

Bij primes is het wel zo fijn om weinig tijd te verliezen in dure functie calls;

De code die je hebt geproduceerd is echter totaal niet efficient (naast dat ie zowat onleesbaar is en zeer foutgevoelig). Bijvoorbeeld: Om te bepalen of 83 een priemgetal is, deelt de code 83 door 9. Dit is een zinloze test als je al weet dat 83 niet door 3 deelbaar is (iets dat de code eerder al deed). Hiermee verspil je veel meer rekenkracht dan je wint door een zogenaamde 'dure function calls' te vermijden.

Mijn advies: programmeer netjes. De meeste compilers zijn veel beter in optimaliseren dan jij. Alleen als er echt een probleem is qua performance dan kun je eens gaan overwegen om te kijken waar de bottleneck zit dmv profiling. Een beter algoritme zal in de meeste gevallen de oplossing zijn (niet het besparen van een paar function calls).

[Onno Dekker]

Je hebt helemaal gelijk wat de zinloze tests betreft, maar het gros van de niet priem getallen valt al door de mand bij relelatief kleine delers.
Je kunt uiteraard eerst wortels gaan bepalen en met metainfo (een reeks priemgetallen als deler werken) om sneller te zijn. Uiteraard wordt hier zeer veel overbodig gerekend, maar dat is ook het geval bij
het eerst bepalen van een reeks delers en wortels. Snellere methoden
voor grote priemgetallen zijn in feite niet sneller bij kleine priemgetallen. Wat betreft leesbaarheid en foutgevoeligheid: juist macro's maken code leesbaarder en geven geen onderhoud.
Voor 256 bits priemgetallen heb je zeker gelijk, maar daar gebruik ik ook macro's voor en geen functies. Info: Gehani on C en Bentley on
writing efficient programs. Optimaliseren doe je alleen als het loont.
Voorbeeld de simpele hash in the C programming Language van K&R is vaak bekritiseerd maar zit nog steeds in veel C code, zonder enig probleem. Keep it stupid.
Zelfs als driedubbele for loops de dure functie calls vermijden.
Overigens is hier alleen veel geneste functies vermeden, fraught with peril, en de code leesbaar en kort gemaakt.

I love macro's and the gnu compiler

H 0u /* definitly no patt, in stream*/
#define NBITS 31u /* last bitno (machine depen.)*/
#define SHIFT(PATLEN) (MAX((NBITS/(unsigned int)(PATLEN)),1u))
#define TOTALSHIFT(PATLEN) (MIN(((SHIFT((unsigned int)(PATLEN)))*(((unsigned int)(PATLEN))-1u)),(NBITS)))

#define SETSHFT(SHI,PATLEN) SHI = SHIFT(PATLEN)
#define SETDIMF(DIM,PATLEN) DIM = TOTALSHIFT(PATLEN)
#define HASH(HVAL,IVAL,SHI) HVAL <<= (SHI); HVAL += (unsigned int)(IVAL)
#define UNHASH(HVAL,IVL,DI) HVAL -= ((unsigned int)(IVL) << (unsigned int)(DI))

Vriendelijk groet,

Onno

[EvilBro]

Wat betreft leesbaarheid en foutgevoeligheid: juist macro's maken code leesbaarder en geven geen onderhoud.

Ik denk dat wij verschillen van mening over wat 'leesbaarder zijn' betekent. Qua onderhoud heb ik nog wel wat opmerkingen: stukje code dat nooit wordt aangeroepen, zinloze deling, variable types die niet matchen.

Keep it stupid.

Bedoel je "Keep it simple, stupid"?

[Xilvo]

Opmerking moderator

Graag on topic blijven.
De laatste reacties hebben niets meer met het onderwerp te maken.

Open eventueel een nieuw topic over programmeren.

[Professor Puntje]

Jammer genoeg is mijn idee in dit topic alweer vastgelopen. Zo gaat het altijd: een inval kan leuk en inspirerend zijn, maar als ik daar dan mee aan de slag ga stoot ik gaandeweg op zoveel problemen dat de lol er al snel vanaf is.

Eigenlijk is het ook wel logisch dat het steeds zo gaat, want alle min of meer voor de hand liggende wiskundige ideeën zijn onderhand al uitgeprobeerd en onderzocht. De kans dat een amateur in deze tijd nog met iets nieuws op de proppen komt is miniem.