/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Permutation af to tal til et
Fra : Jakob Nielsen


Dato : 27-07-06 14:00

Jeg søger en funktion der tager to 16 bit tal og returnerer et tredie
16 bit tal.
Der skal ikke være nogen umiddelbart synlig sammenhæng mellem input
og output.
Det vil sige at hvis jeg tegner funktionen for et interval af x og y,
så skal der ikke opstå et mønster. Det skal gerne se tilfældigt ud.
Jeg troede at jeg let kunne gøre det ved at mikse bit et par gange ved
nogle ombytningstabeller, men det giver i hvert fald mønstre.
Hvis x og y er 0 til 500, så burde jeg også have kunnet undgå
mønstre ved at give x*501+y som seed til en random-generator, men det
giver også mønstre.


 
 
Jakob Nielsen (27-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 27-07-06 14:24

Det er naturligvis bare en hashfunktion, men det er et kriterium at den
er meget hurtig.


Thorbjørn Ravn Ander~ (27-07-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 27-07-06 17:13

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Der skal ikke være nogen umiddelbart synlig sammenhæng mellem input
> og output.

Hvad er det for en opgave du vil have løst?
--
Thorbjørn Ravn Andersen


Jakob Nielsen (27-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 27-07-06 21:52

Som beskrevet.
Kan også udtrykkes som at jeg ønsker et tilfældigt tal ud fra to
seeds uden at der er nogen umiddelbart indlysende sammenhæng mellem de
to seeds og det tilfældige tal.


Thorbjørn Ravn Ander~ (27-07-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 27-07-06 22:01

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Kan også udtrykkes som at jeg ønsker et tilfældigt tal ud fra to
> seeds uden at der er nogen umiddelbart indlysende sammenhæng mellem de
> to seeds og det tilfældige tal.

Så konstruer et seed ud fra dine to, og læs lidt på "random
generators" i Numerical Recipies.

--
Thorbjørn Ravn Andersen


Jakob Nielsen (27-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 27-07-06 22:28

Det har jeg gjort. Desuden er det overkill at starte en ordentlig
generator op, da de generelt er lidt dyre at seede, og jeg kun skal
bruge et resultat pr. seed.

Iøvrigt får jeg også mønstre selv hvis jeg går den vej.

Nedenstående giver et tydeligt mønster. Det selvom der ikke er to
positioner med samme seed.

void tegn()
{
for (int x = 0; x < 200; x++)
for (int y = 0; y < 200; y++)
{
int i = random(x, y);
bmp.SetPixel(x,y,Color.FromArgb(i,i,i));
}
}

int random(int a, int b)
{
//start en generator med a+b*307 som seed
System.Random r = new System.Random(a + b*307);
return r.Next(255);
}

Dette er med System.Random fra .net
Jeg har også forsøgt at tage to 16bit tal og lave en pokkers masse
ombytning af bit i de to tal, så jeg får to nye 16bit som derefter
xor'es sammen til eet 16bit som er resultatet. Når det vises grafisk,
så er der også mønstre der.


Thorbjørn Ravn Ander~ (28-07-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 28-07-06 08:07

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Iøvrigt får jeg også mønstre selv hvis jeg går den vej.

Jeg spørger igen, hvad skal du bruge det til?

> xor'es sammen til eet 16bit som er resultatet. Når det vises grafisk,
> så er der også mønstre der.

Regelmæssige mønstre? Rigtige tilfældige tal giver også mønstre, dog
uregelmæssige.

--
Thorbjørn Ravn Andersen


Ukendt (28-07-2006)
Kommentar
Fra : Ukendt


Dato : 28-07-06 00:52

> Jeg søger en funktion der tager to 16 bit
>tal og returnerer et tredie 16 bit tal.

Hvad med at køre de 4 bytes igennem en crc16 generator.
Den tabelbaserede implementation er hurtig.

Har ikke den fjerneste ide om hvordan det ser ud grafisk !!

tpt




Henning Makholm (28-07-2006)
Kommentar
Fra : Henning Makholm


Dato : 28-07-06 11:32

Scripsit "Jakob Nielsen" <spam@greenleaf.dk>

>> Hvad med at køre de 4 bytes igennem en crc16 generator.
>> Den tabelbaserede implementation er hurtig.

> Det prøvede jeg lige. Det giver desværre også et mønster, men det
> er faktisk det mindst tydelige mønster jeg hidtil har fået, så det
> er nok rette vej.

Hvad med at bruge en gennemtestet veloptimeret hashfunktion
konstrueret til tabelopslag? Lav en "nøgle" bestående af dine to
koordinater (måske gentaget et par gange), og kør den igennem en
hyldevarefunktion som fx <http://burtleburtle.net/bob/c/lookup3.c>.

--
Henning Makholm "Ambiguous cases are defined as those for which the
compiler being used finds a legitimate interpretation
which is different from that which the user had in mind."

Henning Makholm (29-07-2006)
Kommentar
Fra : Henning Makholm


Dato : 29-07-06 10:17

Scripsit "Jakob Nielsen" <spam@greenleaf.dk>

> Det virker også som den hidtil bedste metode.
> Det er dog ikke videre hurtigt, og det tager lidt tid at implementere
> hashfunktionen selv.

Hvorfor vil du implementere det selv når der du blev linket til
færdigsnabelbar kode?

> Dertil kommer at det måske alligevel ikke er godt
> nok, da crc16, som jeg prøvede med, stadig gav mønstre.

CRC er ikke konstrueret til at være hashfunktion, og er ikke særlig
god til det formål. Den er så dårlig som hash at man kan SE mønstrene,
sådan som du har fundet ud af...

--
Henning Makholm "Okay, okay, life's a beach."

Niels L Ellegaard (28-07-2006)
Kommentar
Fra : Niels L Ellegaard


Dato : 28-07-06 04:57

Jakob Nielsen wrote:
> void tegn()
> {
> for (int x = 0; x < 200; x++)
> for (int y = 0; y < 200; y++)
> {
> int i = random(x, y);
> bmp.SetPixel(x,y,Color.FromArgb(i,i,i));
> }
> }
>
> int random(int a, int b)
> {
> //start en generator med a+b*307 som seed
> System.Random r = new System.Random(a + b*307);
> return r.Next(255);
> }

Man skal kun bruge et enkelt seed per simulation. Derefter klarer
tilfældighedsgeneratoren resten.

void tegn(int seed=1)
{
System.Random r = new System.Random(seed);
for (int x = 0; x < 200; x++)
for (int y = 0; y < 200; y++)
{
int i = r.Next(1);
bmp.SetPixel(x,y,Color.FromArgb(i,i,i));
}
}


Jakob Nielsen (28-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 28-07-06 05:26

> Man skal kun bruge et enkelt seed per simulation. Derefter klarer
> tilfældighedsgeneratoren resten.

Normalt ja, men du misforstår. Jeg skal vitterlig bruge to seeds, da
jeg som sagt ønsker en funktion f(a,b)=>c hvor der ikke er noget
synligt mønster når man plotter f for et interval af a og b.

Det er til et terræn som dannes med "midpoint displacement", hvor der
rekursivt dannes nye datapunkter n mellem to eksisterende punkter a og
b. n er så (a+b)/2+rand(a.seed,b.seed).
Da terrænet er med level of detail, så vil man ikke altd danne
punkterne i samme rækkefølge. Derfor kan man ikke bare seede en
generator og så gå der ud af. Det skal jo gerne ligne det samme
terræn som man vil få hvis punkterne dannes i en anden rækkefølge.
Ens seed skal relatere til det nye punkt. Man kan evt bruge det nye
punktsxy-position som seed til en generator der giver offset i z, men
jeg ønsker at have et seed på hver af positionerne a og b, som bruges
til at give mig et tilfældigt tal som skal bruges ved displacement af
b.

De steder jeg har læst om midpoint displacement, der taler de altid
bare i generelle vendinger om et tilfældigt tal. Jeg søger nu en
velegnet metode, der kan give det, og som _ikke_ resulterer i et
mønster i mine displacement-værdier.


Thorbjørn Ravn Ander~ (28-07-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 28-07-06 08:10

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Det er til et terræn som dannes med "midpoint displacement", hvor der
> rekursivt dannes nye datapunkter n mellem to eksisterende punkter a og
> b. n er så (a+b)/2+rand(a.seed,b.seed).

Jeg tror du fokuserer på at det skal være et tilfældigt tal. JEg tror
ikke du kommer ud over at konstruere dit landskab først og så vise det
i forskellige opløsningsgrader.
--
Thorbjørn Ravn Andersen


Jakob Nielsen (28-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 28-07-06 05:32

> Hvad med at køre de 4 bytes igennem en crc16 generator.
> Den tabelbaserede implementation er hurtig.

Det prøvede jeg lige. Det giver desværre også et mønster, men det
er faktisk det mindst tydelige mønster jeg hidtil har fået, så det
er nok rette vej.

http://www.greenleaf.dk/public/pattern.bmp

Det skal bemærkes at selvom mit testbillede viser mønster, så er det
bestemt ikke givet at slutresultatet vil have et synligt mønster
også. Det er en noget indre systematisk måde jeg vil anvende
koordinaterne i den endelige løsning. Jeg har bare hidtil oplevet at
pludselig se en generende symetri eller andre artifacts i et færdigt
landskab, og den overraskelse vil jeg gerne have helt på afstand før
jeg begynder den nye implementation.


Jakob Nielsen (28-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 28-07-06 08:28

> Jeg tror du fokuserer på at det skal være et tilfældigt tal. JEg tror
> ikke du kommer ud over at konstruere dit landskab først og så vise det
> i forskellige opløsningsgrader.

Jeg tror ikke du forstår hvad det skal bruges til. Vel skal det være
et tilfældigt tal. Det skal dog kun være pseudotilfældigt, da man
skal få samme landskab uanset fra hvlken vinkel det dannes.

Hvis du er nysgerrig så se evt noget om fraktale landskaber og
midpoint displacement, som er den metode jeg bruger, da den er meget
velegnet til indbygning i eksempelvis ROAM. Bemærk at jeg ikke
konstruerer mit landskab. Det sker proceduralt.


Thorbjørn Ravn Ander~ (28-07-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 28-07-06 10:15

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> > Jeg tror du fokuserer på at det skal være et tilfældigt tal. JEg tror
> > ikke du kommer ud over at konstruere dit landskab først og så vise det
> > i forskellige opløsningsgrader.
>
> Jeg tror ikke du forstår hvad det skal bruges til. Vel skal det være
> et tilfældigt tal. Det skal dog kun være pseudotilfældigt, da man
> skal få samme landskab uanset fra hvlken vinkel det dannes.

Jeg tror jeg har forstået - du ønsker at have en deterministisk (da
landskabet ikke skal ændre sig) funktion som du kan proppe x og y ind
i og få at vide hvordan det ser ud lige der.

At denne er konstrueret rekursivt ud fra tilfældige tal, ændrer ikke
på at det er det du gerne il have.

De fleste randomfunktioner er bygget til at se tilfældige ud (se
Knuths spektralanalyse) ved gentagne kald, ikke til ikke at give
visuelle mønstre ved indledende kald (netop fordi de ofte af
hastighedsgrunde er modulofunktioner). Ovenikøbet kan de ikke
interpoleres.

Er der noget til hinder for at du gemmer de punkter du beregner?

> Hvis du er nysgerrig så se evt noget om fraktale landskaber og
> midpoint displacement, som er den metode jeg bruger, da den er meget
> velegnet til indbygning i eksempelvis ROAM. Bemærk at jeg ikke
> konstruerer mit landskab. Det sker proceduralt.

Havde du nu skrevet det med det samme havde vi været hurtigere ude

--
Thorbjørn Ravn Andersen


Jakob Nielsen (28-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 28-07-06 10:59

> Jeg tror jeg har forstået - du ønsker at have en deterministisk (da
> landskabet ikke skal ændre sig) funktion som du kan proppe x og y ind
> i og få at vide hvordan det ser ud lige der.

Det er næsten korrekt. Jeg vil proppe x og y ind og have et tal ud som
jeg kan bruge til at ofsette mit midtpunkt.

> De fleste randomfunktioner er bygget til at se tilfældige ud (se
> Knuths spektralanalyse) ved gentagne kald, ikke til ikke at give
> visuelle mønstre ved indledende kald (netop fordi de ofte af
> hastighedsgrunde er modulofunktioner). Ovenikøbet kan de ikke
> interpoleres.

Give visuelle mønstre? Jeg ønsker intet mønster. Det er netop deri
problemet ligger..?
Hvis du har en linie med højden a og b i endepunkterne, så er højden
i midten ½(a+b). Pertuberer du denne højde med eksempelvis q*r, hvor
r er et tilfældigt tal mellem 0 og 1 og q er abs(a-b), så kan du
gentage den proces med rekursiv opdeling og du vil få en art landskab.
Der skal i praksis mere til for at gøre det pænt, men ovenstående
giver et landskab som ikke har mønstre... hvis altså de tilfældige
tal ikke har mønstre.

> Er der noget til hinder for at du gemmer de punkter du beregner?

Nej. Det ønsker jeg at gøre. Når observatøren ændrer retning eller
position, så kan den fine opdeling dog kolapses til en grovere og
tallene slettes.

> Havde du nu skrevet det med det samme havde vi været hurtigere ude

Somme tider kan man også give mere information end hvad der er
relevant for et spørgsmål. Det kan så have den uheldige sideeffekt
at folk tror man er åndsvag eller at emnet er for kedeligt

Jeg søger sådan set stadig bare en funktion f(a,b) der hurtigt giver
en værdi som ikke danner mønstre selvom sekvensen af a og b er simpel
så som a og b=[0..199]


Thorbjørn Ravn Ander~ (28-07-2006)
Kommentar
Fra : Thorbjørn Ravn Ander~


Dato : 28-07-06 22:15

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Give visuelle mønstre? Jeg ønsker intet mønster. Det er netop deri
> problemet ligger..?

Præcis, og det er de ikke bygget til. Derfor synes jeg du skal
overveje grundigt hvad du gør, og så bruge rand-funktionen som designet.

> > Havde du nu skrevet det med det samme havde vi været hurtigere ude
>
> Somme tider kan man også give mere information end hvad der er
> relevant for et spørgsmål. Det kan så have den uheldige sideeffekt
> at folk tror man er åndsvag eller at emnet er for kedeligt

Det er lige så skadeligt at sige for lidt, da man risikerer at få svar
på sit spørgsmål i stedet for en god løsning på sit problem.


> Jeg søger sådan set stadig bare en funktion f(a,b) der hurtigt giver
> en værdi som ikke danner mønstre selvom sekvensen af a og b er simpel
> så som a og b=[0..199]

Du skal jo bruge en feltfunktion, og sådan en har jeg ikke hørt om i
denne sammenhæng.

--
Thorbjørn Ravn Andersen


Jakob Nielsen (29-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 29-07-06 09:41

Det virker også som den hidtil bedste metode.
Det er dog ikke videre hurtigt, og det tager lidt tid at implementere
hashfunktionen selv. Dertil kommer at det måske alligevel ikke er godt
nok, da crc16, som jeg prøvede med, stadig gav mønstre.

Nå, jeg vil udsætte det midlertidigt mens jeg går videre med andre
dele. Det er da heldigvis noget der kan isoleres helt, så man kan lave
forskellige funktioner at teste med hen ad vejen.

Takker til gruppen for feedback.


Jakob Nielsen (29-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 29-07-06 13:01

> Hvorfor vil du implementere det selv når der du blev linket til
> færdigsnabelbar kode?

Fordi min kode er c# og jeg ikke vil til at lave en unmanaged dll med
c++ bare for at kunne få den til-linkede kildekode til at køre.


Mathness (30-07-2006)
Kommentar
Fra : Mathness


Dato : 30-07-06 02:24

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Jeg søger en funktion der tager to 16 bit tal og returnerer et tredie
> 16 bit tal.
> Der skal ikke være nogen umiddelbart synlig sammenhæng mellem input
> og output.

Lyder som om Perlin noise er det du leder efter. Google burde give
nogle brug bare links (hans hp er http://mrl.nyu.edu/~perlin/).

--
Thomas Klietsch
m a t h n e s s @ z 4 2 . d k

Mathness (31-07-2006)
Kommentar
Fra : Mathness


Dato : 31-07-06 14:15

"Jakob Nielsen" <spam@greenleaf.dk> writes:

>> Lyder som om Perlin noise er det du leder efter. Google burde give
>> nogle brug bare links (hans hp er http://mrl.nyu.edu/~perlin/).
>
> Jeg kender godt perlin noise. Jeg har dog af forskellige grunde valgt
> at bruge midpoint displacement.
> Selve støjfunktionen skal stadig have et seed baseret på to værdier
> (et i hvert endepunkt), så problemstillingen er som sådan den samme.
> Hele problemstillingen udspringer jo af at en given position i
> landskabet skal have samme værdi uanset i hvilken rækkefølge
> punkterne beregnes.

Netop derfor jeg foreslog dig PN, da den jo afhænger af input
værdierne. :p

F.eks, kan du lave den med fire inputs (p1,p2,level,node#). Hvor p1 og
p2 er dine seed punkter, level er niveauet i rekursionen og node# er
det midtpunkt der skal forskydes (1 punkt i første level, 2 nodes i
level 2, 4 i level 3 etc.).

M.m. jeg har overset noget igen. >_<

--
Thomas Klietsch
m a t h n e s s @ z 4 2 . d k

Jakob Nielsen (30-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 30-07-06 18:31

> Lyder som om Perlin noise er det du leder efter. Google burde give
> nogle brug bare links (hans hp er http://mrl.nyu.edu/~perlin/).

Jeg kender godt perlin noise. Jeg har dog af forskellige grunde valgt
at bruge midpoint displacement.
Selve støjfunktionen skal stadig have et seed baseret på to værdier
(et i hvert endepunkt), så problemstillingen er som sådan den samme.
Hele problemstillingen udspringer jo af at en given position i
landskabet skal have samme værdi uanset i hvilken rækkefølge
punkterne beregnes.


Torben Ægidius Mogen~ (31-07-2006)
Kommentar
Fra : Torben Ægidius Mogen~


Dato : 31-07-06 08:36

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> > Lyder som om Perlin noise er det du leder efter. Google burde give
> > nogle brug bare links (hans hp er http://mrl.nyu.edu/~perlin/).
>
> Jeg kender godt perlin noise. Jeg har dog af forskellige grunde valgt
> at bruge midpoint displacement.
> Selve støjfunktionen skal stadig have et seed baseret på to værdier
> (et i hvert endepunkt), så problemstillingen er som sådan den samme.
> Hele problemstillingen udspringer jo af at en given position i
> landskabet skal have samme værdi uanset i hvilken rækkefølge
> punkterne beregnes.

Du kan eventuelt downloade mit planetgenereringsprogram fra
http://www.diku.dk/~torbenm . Det har en lignende problemstilling,
ydermere kompliceret af, at "mixeren" skal give samme resultat for
(x,y) som for (y,x). Mixet er ikke kryptografisk stærkt, men det
fungerer fint til formålet.

Torben


Niels L Ellegaard (31-07-2006)
Kommentar
Fra : Niels L Ellegaard


Dato : 31-07-06 06:25

Jakob Nielsen wrote:
> > Lyder som om Perlin noise er det du leder efter. Google burde give
> > nogle brug bare links (hans hp er http://mrl.nyu.edu/~perlin/).
>
> Jeg kender godt perlin noise. Jeg har dog af forskellige grunde valgt
> at bruge midpoint displacement.
> Selve støjfunktionen skal stadig have et seed baseret på to værdier
> (et i hvert endepunkt), så problemstillingen er som sådan den samme.
> Hele problemstillingen udspringer jo af at en given position i
> landskabet skal have samme værdi uanset i hvilken rækkefølge
> punkterne beregnes.

Hvis du er tilfreds med at gemme dine x og y koordinater som integers,
så vil dit landskab uundgåeligt blive endeligt.

Så vidt jeg kan se på nettet findes der en rekursiv implementation af
Perlin støj.
Jeg må indrømme at jeg ikke helt har forstået algoritmen, men jeg
gætter rigtigt, så tillader hver rekursion dig at zoome ind på dit
landskab. Hvis dette er rigtigt, så kan du sandsynligvis bruge
algoritmen til at definere et landskab der er så stort at det vil tage
milioner af år før din screensaver når til verdens udkant.

http://www.acm.org/pubs/tog/GraphicsGems/gemsii/noise3.c


Jakob Nielsen (31-07-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 31-07-06 07:36

> Hvis du er tilfreds med at gemme dine x og y koordinater som integers,
> så vil dit landskab uundgåeligt blive endeligt.

Mit landskab er planeter i et endeligt univers, så det er ikke et
reelt problem. Desuden kan jeg leve med mønstre som forekommer når to
16bit integers danner det samme 32 bit tal som et andet par. Det er
trods alt sjældent. Jeg kan bare ikke leve med mønstre som forekommer
på den lille skale jeg har testet med hidtil. Det vil sige mindre end
200x200.

> Så vidt jeg kan se på nettet findes der en rekursiv implementation af
> Perlin støj.

Takker for hintet. Det vil jeg læse mere om.


Torben Ægidius Mogen~ (31-07-2006)
Kommentar
Fra : Torben Ægidius Mogen~


Dato : 31-07-06 08:31

"Jakob Nielsen" <spam@greenleaf.dk> writes:

> Jeg søger en funktion der tager to 16 bit tal og returnerer et tredie
> 16 bit tal.
> Der skal ikke være nogen umiddelbart synlig sammenhæng mellem input
> og output.
> Det vil sige at hvis jeg tegner funktionen for et interval af x og y,
> så skal der ikke opstå et mønster. Det skal gerne se tilfældigt ud.
> Jeg troede at jeg let kunne gøre det ved at mikse bit et par gange ved
> nogle ombytningstabeller, men det giver i hvert fald mønstre.
> Hvis x og y er 0 til 500, så burde jeg også have kunnet undgå
> mønstre ved at give x*501+y som seed til en random-generator, men det
> giver også mønstre.

Tilfældighedsgeneratorer er ikke altid gode til at undgå mønstre, hvis
de køres med input, der har systematik. Deres force er som regel, at
de kan lave en sekvens, der ser tilfældig ud, når de foregående tal
bruges som input til næste tal. Du kan mindske mønsterdannelsen ved
at lade tilfældighedsgeneratoren køre et par iterationer.

Endnu bedre er det at bruge en kryptografisk hash (som f.eks. MD5), da
de er designede til at undgå mønstre.

Torben


Henning Makholm (31-07-2006)
Kommentar
Fra : Henning Makholm


Dato : 31-07-06 12:56

Scripsit torbenm@tyr.diku.dk (Torben Ægidius Mogensen)

> Tilfældighedsgeneratorer er ikke altid gode til at undgå mønstre, hvis
> de køres med input, der har systematik. Deres force er som regel, at
> de kan lave en sekvens, der ser tilfældig ud, når de foregående tal
> bruges som input til næste tal. Du kan mindske mønsterdannelsen ved
> at lade tilfældighedsgeneratoren køre et par iterationer.

> Endnu bedre er det at bruge en kryptografisk hash (som f.eks. MD5), da
> de er designede til at undgå mønstre.

Kryptografiske hashes er også forholdsvis beregningskrævende, fordi de
er designede til meget mere end at undgå mønstre. Hvis undgåelse af
mønstre er alt hvad man har brug for, kan man klare sig med langt
hurtigere metoder, fx Bob Jenkins' familie af hashfunktioner som jeg
tidligere henviste til.

--
Henning Makholm "Monarki, er ikke noget materielt ... Borger!"

Henning Makholm (04-08-2006)
Kommentar
Fra : Henning Makholm


Dato : 04-08-06 02:09

Scripsit "Jakob Nielsen" <spam@greenleaf.dk>

> Problemet med stærke hashalgoritmer som MD5 er at de er ret dyre at
> bruge så ofte som jeg skal. Besvarelserne på dette forum har
> overbevist mig om det (egentlig indlysende) fornuftige i at bruge en
> hash-algoritme. Problemet har bare hidtil være at de gode metoder er
> for langsomme, og de hurtige er for ringe.

Hvilken af de to ulemper mener du Jenkins' hashfunktioner lider af?

Ellers prøv en funktion af typen:

uint32_t hash(uint16_t x, uint16_t y) {
static uint32_t T[256] = {
0x3cbba0e6, 0x10a1f8d7, 0x1f39a527, 0xecb1bc61,
0x1df72c54, 0x6cb98ed7, 0xa3a20588, 0xe3c9ca16,
/* indsæt 248 flere tilfældige tal her */
0xdf74e127, 0x47cafff6, 0x07b407ba, 0x554a2a9e,
0xa67b42c5, 0x60de8def, 0x3f5abf6b, 0xcc92cfcd, };
uint32_t a = x ;
a += T[a & 0xFF] ;
a -= T[(a >> 8) & 0xFF] ;
a ^= y ;
a -= T[a & 0xFF] ;
a += T[(a >> 8) & 0xFF] ;
a ^= T[(a >> 16) & 0xFF] ;
a ^= T[(a >> 24) & 0xFF] ;
return a ;
}

Giver det stadig mønstre?

--
Henning Makholm "Børge råbte: Åh!"

Jakob Nielsen (01-08-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 01-08-06 12:09

> Endnu bedre er det at bruge en kryptografisk hash (som f.eks. MD5), da
> de er designede til at undgå mønstre.

Problemet med stærke hashalgoritmer som MD5 er at de er ret dyre at
bruge så ofte som jeg skal. Besvarelserne på dette forum har
overbevist mig om det (egentlig indlysende) fornuftige i at bruge en
hash-algoritme. Problemet har bare hidtil være at de gode metoder er
for langsomme, og de hurtige er for ringe.

Hvor grænsen helt præcis går for hvad jeg kan betale tidsmæssigt og
hvad jeg kan leve med af mønstre, det må jeg nu teste.


Jakob Nielsen (01-08-2006)
Kommentar
Fra : Jakob Nielsen


Dato : 01-08-06 19:32

> Du kan eventuelt downloade mit planetgenereringsprogram fra
> http://www.diku.dk/~torbenm . Det har en lignende problemstilling,
> ydermere kompliceret af, at "mixeren" skal give samme resultat for
> (x,y) som for (y,x). Mixet er ikke kryptografisk stærkt, men det
> fungerer fint til formålet.


Jeg vil tage et kig. Inspiration kan man i hvert fald altid bruge.
Måske jeg vender tilbage med nogle spørgsmål.
Nu ser det ellers lovende nok ud med en banal hash som den herunder.
Den giver også mønstre i mit testeksempel, men som jeg lidt håbede
på, så er mønstrene ikke så synlige i praktisk anvendelse. Jeg
søgte kun en nul-mønster metode for at sikre mig mod senere at skulle
lave tingene om.

float rand3(float x, float y, float z)
{
UInt32 t = (UInt32)(x * 4294967231 + y * 4294967029 + z * 4294967279);
t *= 4294967161; ///uden denne så er den grumt mønstret
t *= (UInt32)seed; ///skal ganges på konstanten herover og ikke i
hvert kald!
float f=(float)t/UInt32.MaxValue;
return (f-0.5F)*2; ///return -1..+1
}


Søg
Reklame
Statistik
Spørgsmål : 177501
Tips : 31968
Nyheder : 719565
Indlæg : 6408522
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste