---

Til en 3d støjfunktion kunne jeg godt tænke mig at lave en funktion H(x,y,z)
som giver en god spredning og ikke alt for tydelige mønstre.
Jeg har nu ikke helt kunnet finde på en der ikke er voldsomt periodisk, og
hashfunktioner er som oftest ikke beregnet til at hashe så få værdier.

Er der mon nogle her der kan give et forslag til en god (og gerne hurtig)
metode?

---

Peter wrote:
> Til en 3d støjfunktion kunne jeg godt tænke mig at lave en funktion H(x,y,z)
> som giver en god spredning og ikke alt for tydelige mønstre.
> Jeg har nu ikke helt kunnet finde på en der ikke er voldsomt periodisk, og
> hashfunktioner er som oftest ikke beregnet til at hashe så få værdier.
>
> Er der mon nogle her der kan give et forslag til en god (og gerne hurtig)
> metode?
>
>
Jeg forstår ikke hvad du mener med "få værdier" så mit svar kan være ret langt
ude i skoven. Kommer det ikke an på hvor stort et domæne værdierne x, y og z
ligger i hvor god (aperiodisk) hashing du højst kan forvente? 3x32bit? Det
sætter naturligvis et loft på hvor mange værdier man kan hashe deterministisk
til. Og så kommer det også an på hvor kraftig støj du vil tillade:

* Måske kun afvigelser på højst k bits (lidt vilkårligt)
* Eller på |2^k| (lidt mere "realistisk støj")
* Eller min ynglings: sqrt(x_offset^2 + y_offset^2 + z_offset^2) <= k

Siden det skal gå rigtigt hurtigt er multiplikation og modulo måske for dyrt, så
jeg har prøvet om jeg kan nøjes med et par bitoperationer per kald.

Jeg ved ikke om det kan bruges til noget men here goes:
Først lavede jeg nogle tabeller tilfældigt. Det skal kun gøres én gang og kan
hardcodes, så brugen af dem er deterministisk. Jeg har for letheden og
overblikkets skyld ladet som om hvert koordinat kun er fra et 8-bit domæne. Du
kan selv gendanne dem med en vilkårlig præcision m, ved at vælge tre tilfældige
permutationer af de naturlige tal fra 0 til m-1:

[1|7|0|6|2|4|3|5] // mapping fra x til y
[3|0|6|2|5|7|4|1] // mapping fra y til z
[1|6|0|2|4|5|3|7] // mapping fra z til resultat

res_2^0 = x_2^5 xor y_2^0 xor z_2^6
res_2^1 = x_2^7 xor y_2^1 xor z_2^3
res_2^2 = x_2^4 xor y_2^6 xor z_2^2
res_2^3 = x_2^1 xor y_2^3 xor z_2^4
res_2^4 = x_2^3 xor y_2^2 xor z_2^5
res_2^5 = x_2^2 xor y_2^4 xor z_2^7
res_2^6 = x_2^6 xor y_2^7 xor z_2^0
res_2^7 = x_2^0 xor y_2^5 xor z_2^1

Resultatet er på den her måde en værdi i samme domæne som koordinaterne du kan
vælge at fortolke som en støj vektor på hvilken som helst (konsistent) måde der
passer dig. De enkelte bit tilgåes selvfølgeligt hurtigt med bitmasking og
shifting, så der er ikke nogle dyre potens udregninger.

Hvis det ikke umiddelbart giver gode resultater kan du prøve at smide et par
ekstra mappings ind for at få spredt informationen fra hver oprindelig bit lidt
mere. De 3 mappings vil jeg mene er minimum.

---

Martin Andersen <dur@ikke.nu> writes:

> Peter wrote:
>> Til en 3d støjfunktion kunne jeg godt tænke mig at lave en funktion
>> H(x,y,z) som giver en god spredning og ikke alt for tydelige mønstre.
>> Jeg har nu ikke helt kunnet finde på en der ikke er voldsomt
>> periodisk, og hashfunktioner er som oftest ikke beregnet til at
>> hashe så få værdier.
>> Er der mon nogle her der kan give et forslag til en god (og gerne
>> hurtig) metode?

> res_2^0 = x_2^5 xor y_2^0 xor z_2^6
> res_2^1 = x_2^7 xor y_2^1 xor z_2^3
> res_2^2 = x_2^4 xor y_2^6 xor z_2^2
> res_2^3 = x_2^1 xor y_2^3 xor z_2^4
> res_2^4 = x_2^3 xor y_2^2 xor z_2^5
> res_2^5 = x_2^2 xor y_2^4 xor z_2^7
> res_2^6 = x_2^6 xor y_2^7 xor z_2^0
> res_2^7 = x_2^0 xor y_2^5 xor z_2^1

Problemet med denne metode er, at en et-bits ændring i argumentet
giver en en-bits ændring i resultatet. Ikke nødvendigvis i samme bit,
men alligevel.

I en god hash-funktion skal en en-bit ændring i argumentet ændre
ca. halvdelen af bittene i resultatet, og helt ikke de samme bit hver
gang.

Multiplikation er god, da den kan ændre mange bit i resultatet med et
enkelt ændret bit i argumentet. Multiplikation kan godt være billig,
men det afhænger meget af hvilken processor, man har. Et alternativ
er brug af tabeller i lageret, hvor et ændret bit i adressen kan give
store ændringer i resultatet. Hvis tabellen kan ligge i cachen,
behøver det ikke at være voldsomt dyrt.

Metode ved brug af multiplikation:

(x+k1)*(y+k2)*(z+k3) roteret 11 bit.

hvor k1, k2 og k3 er tilfældige konstanter. Rotation af h med 11 bit
kan i C skrives som (h>>11)|(h<<21), hvis der er tale om 32-bit tal.
En god C-compiler kan generere en rotate-instruktion ud fra dette (det
kan C-compileren til ARM i hvert fald). Så i C kan du skrive det hele
som

h = (x+k1)*(y+k2)*(z+k3);
h = (r>>11)|(r<<21);

Metode ved brug af tabelopslag:

Vi antager at tabellen t har 256 tilfældige 32-bit tal. Vi starter
med at generere fire indgange til tabellen:

a1 = (x^(y>>8)^(z>>16))&255;
a2 = ((x>>8)^y^(z>>24))&255;
a3 = ((x>>16)^(y>>24)^z)&255;
a4 = ((x>>24)^(y>>16)^(z>>8))&255;

Dernæst slår vi op i tabellerne og XOR'er resultaterne:

h = t[a1]^t[a2]^t[a3]^t[a4];

Læg mærke til at alle bittene i x, y og z bliver brugt, så enhver
en-bits ændring i argumentet ændrer en af indgangene.

   Torben

---

> h = (x+k1)*(y+k2)*(z+k3);
> h = (r>>11)|(r<<21);

I den form får jeg tydelige mønstre hvis jeg kører 256*256 pixels i et
billede, og sætter farven til gråtoneværdien af hashen.

for(int x=0;x<256;x++) for (int y = 0; y < 256; y++){


UInt32 z = (UInt32)(x * 175426 + y * 678743641);

z = (z>>11)|(z<<21); ///z giver tydelige mønstre



for(int x=0;x<256;x++)for (int y = 0; y < 256; y++){


UInt32 z = (UInt32)(x * 175426 + y * 678743641);

z = (z>>11)|(z<<21);

byte a = (byte)((z & 0xFF000000) >> 24);

byte b = (byte)((z & 0x00FF0000) >> 16);

byte c = (byte)((z & 0x0000FF00) >> 8);

byte d = (byte)((z & 0x000000FF) >> 0);

byte z = (byte)(a ^ b ^ c ^ d); //giver mindre tydeligt mønster, men det er
der nu stadig



> Metode ved brug af tabelopslag:


Den virker bedre, men der er stadig nogle områder med en art mønster. Måske
fordi jeg lemlester metoden til et lille 256*256 område? Jeg ved heller ikke
om det er mig der forventer noget andet end jeg bør. Jeg håber på at se et
billede med ren gråtonestøj, hvor alle værdier forekommer lige ofte, og uden
nogen form for lokale mønstre.





>
> Vi antager at tabellen t har 256 tilfældige 32-bit tal.

Hvad kan man sige om cykluslængden som funktion af tabelstørrelsen? Er 256
lige så godt som større tabeller, eller i hvilket forhold er det bedre når
tabellen vokser?



>Vi starter
> med at generere fire indgange til tabellen:
>
> a1 = (x^(y>>8)^(z>>16))&255;
> a2 = ((x>>8)^y^(z>>24))&255;
> a3 = ((x>>16)^(y>>24)^z)&255;
> a4 = ((x>>24)^(y>>16)^(z>>8))&255;


Det er valgt så de otte største bit i x slår igennem i a1, mens de næste
otte er x og y, de næste 16 er x,y og z, eller hvorledes? Hvorfor shifter du
istedet for at rotere? Jeg kan ikke helt se efter hvilket mønster du vælger
a1..4, men hvis man ser på hvor mange måder man kan kombinere bytes fra
x,y,z i et 32 bit dword, så er der vel 9 måder, hvilket er et bedre valg, så
man har 9 index hvis tabelværdier så kunne xores?

> Læg mærke til at alle bittene i x, y og z bliver brugt, så enhver
> en-bits ændring i argumentet ændrer en af indgangene.


Ja, og når en indgang ændres så ændres resultatet af dens tabelopslag sig
vilkårligt meget, da indexn og indexn+1 intet forhold har til hinanden.

---

"Peter" <p@home.no.dk> writes:

> I den form får jeg tydelige mønstre hvis jeg kører 256*256 pixels i et
> billede, og sætter farven til gråtoneværdien af hashen.

Kan du ikke lave nogen modulo-ting med værdier der er meget større end
256 og indbyrdes primiske?
--
Thorbjørn Ravn Andersen

---

> Kan du ikke lave nogen modulo-ting med værdier der er meget større end
> 256 og indbyrdes primiske?

Jeg forsøgte med a=4294002047 og b=4294000717 som er store primtal nær
maksimum af hvad 32 bit kan rumme. Duede ikke for mig.
z=(x*a+b*z)%256

---

> [1|7|0|6|2|4|3|5] // mapping fra x til y
> [3|0|6|2|5|7|4|1] // mapping fra y til z
> [1|6|0|2|4|5|3|7] // mapping fra z til resultat

[[1|7|0|6|2|4|3|5]] Skal det forstås som at bit 7 i y er bit 1 i x, eller er
det at du bruger det som index i resultatet, så resultat_bit0 er x_bitA xor
y_bitB xor z_bitC, hvor A,B,C er disse mappingværdier? Det vil give mening,
jeg så genkender jeg ikke værdierne mellem de to beregninger, du viser.
resultatets første bit er tilsyneladende x5,y0 og z6, som ikke forekommer i
tabellen herover? Beklager hvis jeg bare er for langsom i toppen lige nu.

> res_2^0 = x_2^5 xor y_2^0 xor z_2^6
> res_2^1 = x_2^7 xor y_2^1 xor z_2^3
> res_2^2 = x_2^4 xor y_2^6 xor z_2^2
> res_2^3 = x_2^1 xor y_2^3 xor z_2^4
> res_2^4 = x_2^3 xor y_2^2 xor z_2^5
> res_2^5 = x_2^2 xor y_2^4 xor z_2^7
> res_2^6 = x_2^6 xor y_2^7 xor z_2^0
> res_2^7 = x_2^0 xor y_2^5 xor z_2^1

---

Peter wrote:
>>[1|7|0|6|2|4|3|5] // mapping fra x til y
>>[3|0|6|2|5|7|4|1] // mapping fra y til z
>>[1|6|0|2|4|5|3|7] // mapping fra z til resultat
>
>
> [[1|7|0|6|2|4|3|5]] Skal det forstås som at bit 7 i y er bit 1 i x, eller er
> det at du bruger det som index i resultatet, så resultat_bit0 er x_bitA xor
> y_bitB xor z_bitC, hvor A,B,C er disse mappingværdier? Det vil give mening,
> jeg så genkender jeg ikke værdierne mellem de to beregninger, du viser.
> resultatets første bit er tilsyneladende x5,y0 og z6, som ikke forekommer i
> tabellen herover? Beklager hvis jeg bare er for langsom i toppen lige nu.
>

   ****   * ** ***
>>res_2^0 = x_2^5 xor y_2^0 xor z_2^6
>>res_2^1 = x_2^7 xor y_2^1 xor z_2^3
>>res_2^2 = x_2^4 xor y_2^6 xor z_2^2
>>res_2^3 = x_2^1 xor y_2^3 xor z_2^4
>>res_2^4 = x_2^3 xor y_2^2 xor z_2^5
>>res_2^5 = x_2^2 xor y_2^4 xor z_2^7
>>res_2^6 = x_2^6 xor y_2^7 xor z_2^0
>>res_2^7 = x_2^0 xor y_2^5 xor z_2^1

* tallet i den her kolonne fremkommer af placeringen i første tabel, altså fra
højre mod venstre, zerobased.

** på den plads i første array står denne værdi

*** på samme plads men i andet array står denne værdi

**** på samme plads men i tredje array står denne værdi

Listen virker lidt tilfældig fordi jeg sorterede linierne fra mindst betydende
bit til mest, for at man kunne se opskriften fra den ene ende af resultatet til
det andet i stedet for i den vilkårlige rækkefølge som det er givet i arraysne.

Det er rigtigt som Torben siger, at én bit ændring i værdierne der hashes kun
giver én bit ændring i resultatet, men rent numerisk kan det godt se meget
tilfældigt ud fordi det ikke kun er en ændring i mindst betydende bit. Så en
lille bevægelse kan give et stort spring. Måske kan det med fordel kombineres
med andre teknikker, then again, måske ikke :)

---

"Peter" <p@home.no.dk> writes:

>> h = (x+k1)*(y+k2)*(z+k3);
>> h = (r>>11)|(r<<21);
>
> I den form får jeg tydelige mønstre hvis jeg kører 256*256 pixels i et
> billede, og sætter farven til gråtoneværdien af hashen.
>
> for(int x=0;x<256;x++) for (int y = 0; y < 256; y++){
>
>
> UInt32 z = (UInt32)(x * 175426 + y * 678743641);

Det er jo heller ikke det, som jeg skrev. Prøv

UInt32 z = (UInt32)((x + 175426) * (y + 678743641));

i stedet for.

>> Metode ved brug af tabelopslag:
>
>
> Den virker bedre, men der er stadig nogle områder med en art mønster. Måske
> fordi jeg lemlester metoden til et lille 256*256 område?

Ja, det kan have noget at sige, for når kun den nederste byte af hvert
tal er forskellig fra 0, reduceres indgangene til

a1 = x;
a2 = y;
a3 = z;
a4 = 0;

så et diagonalt ryk (f.eks. (x,y) -> (x+1,y-1)) vil ikke ændre noget.

> Jeg ved heller ikke
> om det er mig der forventer noget andet end jeg bør. Jeg håber på at se et
> billede med ren gråtonestøj, hvor alle værdier forekommer lige ofte, og uden
> nogen form for lokale mønstre.

Hvordan fandt du de 256 tabelværdier?

>> Vi antager at tabellen t har 256 tilfældige 32-bit tal.
>
> Hvad kan man sige om cykluslængden som funktion af tabelstørrelsen? Er 256
> lige så godt som større tabeller, eller i hvilket forhold er det bedre når
> tabellen vokser?

Ethvert tal fremkommer ved at XOR'e fire tal fra tabellen, så dr er
højst 256^4 = 2^32 forskellige tal, og medmindre du har valgt de 256
tabelværdier meget omhyggeligt, vil du få væsentligt færre forskellige
tal. Perioden afhænger også meget af tabellens værdier.

>>Vi starter
>> med at generere fire indgange til tabellen:
>>
>> a1 = (x^(y>>8)^(z>>16))&255;
>> a2 = ((x>>8)^y^(z>>24))&255;
>> a3 = ((x>>16)^(y>>24)^z)&255;
>> a4 = ((x>>24)^(y>>16)^(z>>8))&255;
>
>
> Det er valgt så de otte største bit i x slår igennem i a1, mens de næste
> otte er x og y, de næste 16 er x,y og z, eller hvorledes?

Hver indgang bruger en byte fra hvert tal, og alle de 12 forskellige
bytes bruges i en af indgangene.

> Hvorfor shifter du istedet for at rotere?

Da jeg kun bruger de sidste 8 bit af hvert tal, gør det ikke nogen forskel.

> Jeg kan ikke helt se efter hvilket mønster du vælger
> a1..4, men hvis man ser på hvor mange måder man kan kombinere bytes fra
> x,y,z i et 32 bit dword, så er der vel 9 måder, hvilket er et bedre valg, så
> man har 9 index hvis tabelværdier så kunne xores?

jeg ved ikke, hvor dit nital kommer fra. Som jeg nævnte, er der ialt
12 bytes i de tre tal. Der er ingen grund til at bruge hver byte mere
end en gang, så ovenstående burde være nok.

>> Læg mærke til at alle bittene i x, y og z bliver brugt, så enhver
>> en-bits ændring i argumentet ændrer en af indgangene.
>
> Ja, og når en indgang ændres så ændres resultatet af dens tabelopslag sig
> vilkårligt meget, da indexn og indexn+1 intet forhold har til hinanden.

Netop.

Men som dit eksempel viste, så er der problemer med "diagonale"
bevægelser. Det kan undgås, hvis man bruger fire forskellige tabeller
til de fire opslag i stedet for at genbruge den samme tabel.

   Torben

---

> Hvordan fandt du de 256 tabelværdier?

Jeg finder dem ved at starte en pseudorandom number generator op og lave 256
værdier.

>>> med at generere fire indgange til tabellen:
>>>
>>> a1 = (x^(y>>8)^(z>>16))&255;
>>> a2 = ((x>>8)^y^(z>>24))&255;
>>> a3 = ((x>>16)^(y>>24)^z)&255;
>>> a4 = ((x>>24)^(y>>16)^(z>>8))&255;

Jeg kan ikke få det til at fungere for mig. har dog også måttet konvertere
det til 16 bit :-/

Jeg laver lige nu fire tabeller med værdier mellem sådan her. De er på
[0..0xFFFF]

for (int i = 0; i < 256; i++){

t1[i] = (UInt16)rand.Next(0, 0xFFFF + 1);

t2[i] = (UInt16)rand.Next(0, 0xFFFF + 1);

t3[i] = (UInt16)rand.Next(0, 0xFFFF + 1);

t4[i] = (UInt16)rand.Next(0, 0xFFFF + 1);

}

så beregner jeg hash sådan her, og shifter i nibbles istedetfor bytes, så
det burde passe som i dit eksempel

float hash(UInt16 x, UInt16 y, UInt16 z){


byte a1 = (byte)((x ^ (y >> 4) ^ (z >> 8)) & 255);

byte a2 = (byte)(((x >> 4) ^ y ^ (z >> 12)) & 255);

byte a3 = (byte)(((x >> 8) ^ (y >> 12) ^ z) & 255);

byte a4 = (byte)(((x >> 12) ^ (y >> 8) ^ (z >> 4)) & 255);

UInt16 h = (UInt16)(t1[a1] ^ t2[a2] ^ t3[a3] ^ t4[a4]);

return (float)h / UInt16.MaxValue;




}

Hvis jeg plotter pixels som image(x,y)=hash(x,y)*255, så får jeg et markant
mønster, som ikke lige sådan er til at beskrive.

Hvad pokker er det jeg gør galt her? En mere kompleks metode som
http://www.cs.kuleuven.ac.be/~graphics/CGRG.PUBLICATIONS/LagaeDutre2006LongPeriodHashFunctionsForProceduralTexturing/paper.pdf
virker fint og giver noget der både visuelt og testmæssigt (linket fra Jens
Axel Søgård) giver et tilfældigt resultat. Det er imidlrtid en lidt
omstændig metode i forhold til hvad I har anvist her i gruppen, så hvis jeg
kan få det til at virke, så ville det være at foretrække.

---

> Hvad pokker er det jeg gør galt her?

Hovsa! Når jeg kalder funtionen så varierer jeg x og y, men ikke z. Hvis jeg
kalder som
hash(x,y,0), så er der mønster. hash(x,y,x) giver også mønster mens
hash(x,y,x*y) ikke gør.

Burde funktionen ikke fungere bare jeg kører langs een variabel?
Et tillægsspørgsmål er hvorfor
http://www.cs.kuleuven.ac.be/~graphics/CGRG.PUBLICATIONS/LagaeDutre2006LongPeriodHashFunctionsForProceduralTexturing/paper.pdf
skulle være bedre, hvis metoden fra tråden her fungerer så godt, som det
beskrives? Hvordan adskilder den anden sig?

---

> Et tillægsspørgsmål er hvorfor
http://www.cs.kuleuven.ac.be/~graphics/CGRG.PUBLICATIONS/LagaeDutre2006LongPeriodHashFunctionsForProceduralTexturing/paper.pdf >
skulle være bedre, hvis metoden fra tråden her fungerer så godt, som det
> beskrives? Hvordan adskilder den anden sig?

Ja.. ok.. jeg er åbenbart for doven til at læse teksten ordentligt. Det er
jo tydeligt forklaret. Jeg har iøvrigt fine resultater med deres simple
metode med at summere nogle små-periode funktioner. En på 103 og en på 107
giver glimrende resultater.
int a = p1[(p1[x % prime1] + y) % prime1];

int b = p2[(p2[x % prime2] + y) % prime2];

return (byte)((a + b) % 255);



Meget lettere bliver det jo ikke. Jeg er imidlertid stadig intereseret i
svarene på alle mine tidligere spørgsmål. De der ikke er alt for dumme.. så
som hvorfor torbens metode fejler (for mig) hvis ikke jeg varierer samtlige
variabler.

---

>> Hvordan fandt du de 256 tabelværdier?
>
> Jeg finder dem ved at starte en pseudorandom number generator op og lave
> 256 værdier.

Hov... det er permutationstabeller, ikke? Så bør de vel ikke have tilfældige
værdier, men (for en 256 stor tabel) istedet værdierne fra og med 0 til og
med 255, hvor hver forekommer een gang?

---

"Peter" <p@home.no.dk> writes:

> Jeg kan ikke få det til at fungere for mig. har dog også måttet konvertere
> det til 16 bit :-/
>
> Jeg laver lige nu fire tabeller med værdier mellem sådan her. De er på
> [0..0xFFFF]
>
> for (int i = 0; i < 256; i++){
>
> t1[i] = (UInt16)rand.Next(0, 0xFFFF + 1);
>
> t2[i] = (UInt16)rand.Next(0, 0xFFFF + 1);
>
> t3[i] = (UInt16)rand.Next(0, 0xFFFF + 1);
>
> t4[i] = (UInt16)rand.Next(0, 0xFFFF + 1);
>
> }
>
> så beregner jeg hash sådan her, og shifter i nibbles istedetfor bytes, så
> det burde passe som i dit eksempel
>
> float hash(UInt16 x, UInt16 y, UInt16 z){
>
>
> byte a1 = (byte)((x ^ (y >> 4) ^ (z >> 8)) & 255);
>
> byte a2 = (byte)(((x >> 4) ^ y ^ (z >> 12)) & 255);
>
> byte a3 = (byte)(((x >> 8) ^ (y >> 12) ^ z) & 255);
>
> byte a4 = (byte)(((x >> 12) ^ (y >> 8) ^ (z >> 4)) & 255);
>
> UInt16 h = (UInt16)(t1[a1] ^ t2[a2] ^ t3[a3] ^ t4[a4]);
>
> return (float)h / UInt16.MaxValue;
>
> }
>
> Hvis jeg plotter pixels som image(x,y)=hash(x,y)*255, så får jeg et markant
> mønster, som ikke lige sådan er til at beskrive.

Nar du skifter i nibbles i stedet for bytes, kan du kun bruge den
sidste nibble i resultatet. En af ideerne i metoden er at man bruger
hvert bit i x, y og z præcis en gang, men når du kun skifter 4 bit af
gangen men stadig bruger 8 bit i resultatet mister du den egenskab.

Tabeller med kun 16 indgange er nok i underkanten, men hvis du har
problemer med 32-bit tal kan du evt. prøve en 28 (4x7) bit version:

a1 = (x ^ (y>>7) ^ (z>>14)) & 127;
a2 = ((x>>7) ^ y ^ (z>>21)) & 127;
a3 = ((x>>14) ^ (y>>21) ^ z) & 127;
a4 = ((x>>21) ^ (y>>14) ^ (z>>7)) & 127;
h = t1[a1] ^ t2[a2] ^ t3[a3] ^ t4[a4];

Tabellerne t1, t2, t3 og t4 har nu 128 indgange hver.

   Torben

---

"Peter" <p@home.no.dk> writes:

>> Et tillægsspørgsmål er hvorfor
> http://www.cs.kuleuven.ac.be/~graphics/CGRG.PUBLICATIONS/LagaeDutre2006LongPeriodHashFunctionsForProceduralTexturing/paper.pdf >
> skulle være bedre, hvis metoden fra tråden her fungerer så godt, som det
>> beskrives? Hvordan adskilder den anden sig?
>
> Ja.. ok.. jeg er åbenbart for doven til at læse teksten ordentligt. Det er
> jo tydeligt forklaret. Jeg har iøvrigt fine resultater med deres simple
> metode med at summere nogle små-periode funktioner. En på 103 og en på 107
> giver glimrende resultater.
> int a = p1[(p1[x % prime1] + y) % prime1];
>
> int b = p2[(p2[x % prime2] + y) % prime2];
>
> return (byte)((a + b) % 255);
>
> Meget lettere bliver det jo ikke. Jeg er imidlertid stadig intereseret i
> svarene på alle mine tidligere spørgsmål. De der ikke er alt for dumme.. så
> som hvorfor torbens metode fejler (for mig) hvis ikke jeg varierer samtlige
> variabler.

Ovennævnte metode bruger % (modulus) som er ret dyr (en del dyrere end
multiplikation). Det troede jeg, at du ville undgå. Har du prøvet
mit forslag med (x+k1)*(y+k2)*(z+k3) roteret 11 bits? Du havde jo
byttet om på + og * i dit første forsøg.

   Torben

---

> Ovennævnte metode bruger % (modulus) som er ret dyr (en del dyrere end
> multiplikation). Det troede jeg, at du ville undgå.

Jeg formulerede mig måske lidt uklart oprindeligt. Med billig/hurtig mente
jeg ikke at det skulle være det optimale, men at jeg i hvert fald ikke kunne
bruge de store forkromede kryptografiske hashfunktioner, da jeg skal kalde
funktionen ofte.
Jeg vil lige lave nogle hastighedstest og se hvor meget det koster mig at
bruge modulus i forhold til bit shifting, som du foreslår.

>Har du prøvet
> mit forslag med (x+k1)*(y+k2)*(z+k3) roteret 11 bits? Du havde jo
> byttet om på + og * i dit første forsøg.

Ja, det var lidt åndsvagt af mig. Jeg vil prøve lige nu........ja. der er
mønster. Måske jeg igen laver rod i det, så her er lige linien...
return (byte)( ((x+187465984)*(y+77744127))%256);

Med lidt ændringer

UInt32 q = (UInt32)((x + 187465984) * (y + 77744127));

byte a = (byte)(q >> 24);

byte b = (byte)(q >> 16);

byte c = (byte)(q >> 8);

byte d = (byte)(q >> 0);

return (byte)(a ^ b ^ c ^ d);



får jeg mindre mønster, men det er stadig tydeligt.

Mønstrene er med en periode på ca 256 og første var afrundede firkanter hvor
den anden er stjerneformet.

Måske jeg laver for grove ændringer i din metode, når jeg skal teste den, så
hvis du kan se at jeg laver den slags fejl, og du kan , og gider, opskrive
metoden så jeg kan give den to 32 bit input og få en byte ud, så vil det
være det mest sikre.

Uanset hvad, så mange tak for hjælpen thus far. Dine forklaringer undervejs
har givet mig en lidt bedre forståelse, omend jeg tilsyneladende stadig
overser alle fælderne.

---

"Peter" <p@home.no.dk> writes:

>>> Hvordan fandt du de 256 tabelværdier?
>>
>> Jeg finder dem ved at starte en pseudorandom number generator op og lave
>> 256 værdier.
>
> Hov... det er permutationstabeller, ikke? Så bør de vel ikke have tilfældige
> værdier, men (for en 256 stor tabel) istedet værdierne fra og med 0 til og
> med 255, hvor hver forekommer een gang?

Hvis du kun bruger de sidste 8 bit af resultatet, så er det bestemt en
god ide. Mit oprindelige forslag var at bruge 32 bit, så der er ikke
plads til alle mulige værdier i tabellen. Men det er måske ikke nogen
dårlig ide, at sikre at de sidste 8 bit allesammen er forskellige, og
ligeså med de næste 8 bit osv.

   Torben

---

"Peter" <p@home.no.dk> writes:

>> Ovennævnte metode bruger % (modulus) som er ret dyr (en del dyrere end
>> multiplikation). Det troede jeg, at du ville undgå.
>
> Jeg formulerede mig måske lidt uklart oprindeligt. Med billig/hurtig mente
> jeg ikke at det skulle være det optimale, men at jeg i hvert fald ikke kunne
> bruge de store forkromede kryptografiske hashfunktioner, da jeg skal kalde
> funktionen ofte.
> Jeg vil lige lave nogle hastighedstest og se hvor meget det koster mig at
> bruge modulus i forhold til bit shifting, som du foreslår.
>
>>Har du prøvet
>> mit forslag med (x+k1)*(y+k2)*(z+k3) roteret 11 bits? Du havde jo
>> byttet om på + og * i dit første forsøg.
>
> Ja, det var lidt åndsvagt af mig. Jeg vil prøve lige nu........ja. der er
> mønster. Måske jeg igen laver rod i det, så her er lige linien...
> return (byte)( ((x+187465984)*(y+77744127))%256);

Hvis x øges med 1, øges resultatet inden modulo med 77744127, så efter
modulo øges værdien med 77744127%256 = 255, hvilket klart giver
mønstre. Mit forslag involverede en rotation med 11 bit efter
multiplikationen, men hvis du kun bruger de sidste 8 bit af resultatet
kan det ligesågodt være et højreskift pa 11 bit. Det giver stadig
lidt mønster, da x += 1 giver en forøgelse med 77744127/2^11, men da
der nogle gange er carry ind i bit 11, er øgningen skiftevis 37960 og
37961. Så mindre mønster, men stadig noget. Din gentage skift i den
modificerede udgave øger antallet af mulige carry-bit, så der er endnu
mindre mønster. Men for at undgå mønstre helt skal man lave mere om.

Jeg beklager, at jeg ikke testede mit forslag ordentligt inden jeg
postede. Jeg har brugt en lignende metode som tilfældighedsgenerator,
men ikke med systematiske ændringer i input som du gør, så jeg var
ikke helt opmærksom på problemet.

En mulig løsning er at iterere metoden et par gange:

q = (x+187465984)*(y+77744127);
q1 = (q>>11)|(q<<11);
q2 = (q>>19)|(q<<19);
q = (q1+187465984)*(q2+77744127);

> Måske jeg laver for grove ændringer i din metode, når jeg skal teste den, så
> hvis du kan se at jeg laver den slags fejl, og du kan , og gider, opskrive
> metoden så jeg kan give den to 32 bit input og få en byte ud, så vil det
> være det mest sikre.

En metode, som jeg ved virker, kræver lidt flere trin, men hvert trin
bruger kun simple operationer:

uint32 q;

q = (y>>11)|(y<<11)+x; /* lav meget primitiv hash af x og y */

for (i=0; i<32; i++) /* iterer en anden primitiv hash */
if (q&1) q = (q>>1)+K1;
else q = (q>>1)+K2;

hvor K1 og K2 er tilfældige 32-bit tal. Hvor godt resultatet bliver
kan dog afhænge meget af K1 og K2.

> Uanset hvad, så mange tak for hjælpen thus far. Dine forklaringer undervejs
> har givet mig en lidt bedre forståelse, omend jeg tilsyneladende stadig
> overser alle fælderne.

Jeg overser tilsyneladende også en del fælder.

   Torben

---

> som giver en god spredning og ikke alt for tydelige mønstre.

Hvordan tester man egentlig den slags, andet end som nu ved at tegne pixels
og kigge efter mønstre?
Jeg kunne velsagtens regne kovariansen ud for mine pixels positioner og
vægte dem med intensiteten. Så burde jeg få to lige store egenvektorer ud af
det, hvis det er tilfældigt, ik? Samtidigt bør middel være omkring centrum
og variansen skal være kæmpe... men... det kan man jo også fint opnå med
billeder der har tydelige mønstre

---

"Peter" <p@home.no.dk> writes:

> og variansen skal være kæmpe... men... det kan man jo også fint opnå med
> billeder der har tydelige mønstre

Spørgsmålet er hvilke mønstre der kan ses, og hvad der ønskes.

Hjernen finder mønstre i selv tilfældigt fordelte punkter.
--
Thorbjørn Ravn Andersen

---

> Hjernen finder mønstre i selv tilfældigt fordelte punkter.

Det jeg ikke ønsker at se, det er gentagelser. Man bør ikke kunne se noget
gentage sig.

---

"Peter" <p@home.no.dk> writes:

> Det jeg ikke ønsker at se, det er gentagelser. Man bør ikke kunne se noget
> gentage sig.

Kunne du eventuelt løfte sløret for hvad det skal bruges til.

Hvis det er noget visualisering kunne jeg forestille mig der måske var
noget at hente med "texture" og "noise" som søgeord.
--
Thorbjørn Ravn Andersen

---

Peter skrev:
>> som giver en god spredning og ikke alt for tydelige mønstre.
>
> Hvordan tester man egentlig den slags, andet end som nu ved at tegne pixels
> og kigge efter mønstre?

Nu drejer nedenstående side godt nok ikke om hash-funktioner, men
om frembringere af tilfældige tal:

<http://www.fourmilab.ch/random/>

Testene giver en ide om, hvordan man kigger efter "mønstre".

--
Jens Axel Søgaard

---

"Peter" <p@home.no.dk> skrev i en meddelelse
news:45628c7e$0$143$157c6196@dreader2.cybercity.dk...

> hashfunktioner

Hvad er det lige en "hashfunktion"?

Hvad er hash, udover Beatlestobak?

---

> Hvad er det lige en "hashfunktion"?

http://www.google.dk/search?sourceid=navclient&ie=UTF-8&rls=GGLJ,GGLJ:2006-35,GGLJ:en&q=define%3ahash+function

Eller bare google og så
define: hash function

---

"Peter" <p@home.no.dk> skrev i en meddelelse
news:45647c6e$0$145$157c6196@dreader2.cybercity.dk...
>> Hvad er det lige en "hashfunktion"?
>
> http://www.google.dk/search?sourceid=navclient&ie=UTF-8&rls=GGLJ,GGLJ:2006-35,GGLJ:en&q=define%3ahash+function
>
> Eller bare google og så
> define: hash function

Jatang, og så en kort forklaring på dansk?

---

ThomasB wrote:
> "Peter" <p@home.no.dk> skrev i en meddelelse
> news:45647c6e$0$145$157c6196@dreader2.cybercity.dk...
>
>>>Hvad er det lige en "hashfunktion"?
>>
>>http://www.google.dk/search?sourceid=navclient&ie=UTF-8&rls=GGLJ,GGLJ:2006-35,GGLJ:en&q=define%3ahash+function
>>
>>Eller bare google og så
>>define: hash function
>
>
> Jatang, og så en kort forklaring på dansk?
>
>
lav en søgning på dansk? "hashfunktion" ...

http://da.wikipedia.org/wiki/Hashfunktion

---

"Martin Andersen" <dur@ikke.nu> skrev i en meddelelse
news:456496e5$0$49209$14726298@news.sunsite.dk...

>> Jatang, og så en kort forklaring på dansk?
> lav en søgning på dansk? "hashfunktion" ...

Ja, hvad skal vi efterhånden med usenet?

> http://da.wikipedia.org/wiki/Hashfunktion

Tak, og det forstår jeg stadig ikke så meget af.

---

ThomasB skrev:

> Jatang, og så en kort forklaring på dansk?

En hashfunktion beregner en værdi ud fra et givet input. Det
bruges f.eks. ved sortering, men det kan også bruges som kontrol
af data.

Lad os sige at vi har nogle personnavne som data. Det vil tage
for lang tid at sortere dem direkte, men det ville hjælpe at lave
en hashfunktion der fordelte inddata i f.eks. 1000 grupper som
hver omfattede en promille af de mulige værdier. Disse grupper
kan sorteres separat, og så går det hurtigere.

Hvis et navn giver hashværdien 7, men inddata pludselig en dag
giver en anden hashværdi når dette navn afsendes, så ved man at
der er fejl i transmissionen.

Problemerne ved hashing er omfattende og interessante, så der er
skrevet en del om det. Ét fundamentalt problem er f.eks. om
hashfunktionen vitterligt deler de mange værdier jævnt ud på de
mulige grupper, eller om den putter 90 % af elementerne i gruppe
1 så det hele er spildt.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

"Bertel Lund Hansen" <unospamo@lundhansen.dk> skrev i en meddelelse
news:4564a4ae$0$4172$ba624c82@nntp02.dk.telia.net...
>> Jatang, og så en kort forklaring på dansk?
>
> En hashfunktion beregner en værdi ud fra et givet input. Det
> bruges f.eks. ved sortering, men det kan også bruges som kontrol
> af data.


Tak Bertel. Jeg researcher lige lidt og vender tilbage med en masse
spørgsmål