Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
21.11.2006, 11:47 Uhr
~grimmel
Gast

Hallo,
ich habe eine hashfunktion die für double vektoren einen 32 Bit schlüssel errechnet. Das läuft super!

Jetzt reicht mir der 32 Bit schlüssel definitiv nicht! Ich brauche mindestens 128 Bit. Oder besser 256 BIt. Allerdings habe ich schwierigkeiten bei solchen Bitgrössen die funktion um zuschreiben....vielleicht hat jemand eine gute Idee?

Hier erstmal die alte variante mit 32 Bit:

Zur erklärung:
für jedes vektor element errechne ich einen 32 Bit key der addiert wird zum vorherigen ergebnis.
Ein 32 Bit wert für einen double wird so errechnet:
auf ganzzahl 64 Bit casten, dann die oberen 32 Bit mit den unteren verXORen
und dann die unteren 32 Bit rausschmeissen.

C++:

...
typedef unsigned int U_Int32;

...
U_Int32
Hash::compute_key(const double* vec, size_t size) const
{
    U_Int32 ret = 0;
    while(size--)
    {
        ret = (ret * 31) + hash_double(*vec);
        vec++;
    }
    return ret;
}



inline U_Int32
Hash::hash_double(double x)
{
    U_Int64* p = reinterpret_cast< U_Int64* > (&x);
    return *p ^ (*p >> 32);
}

ginge das irgendwie mittels unsigned long long ? sind dann aber wohl net 256 BIt oder?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
21.11.2006, 12:30 Uhr
(un)wissender
Niveauwart

doubles lassen sich so nicht hashen. Erstens sind die nicht unbedingt 8 Bytes lang, zweitens ist es wichtig ob die Werte normalisiert sind oder nicht. Mach einen String draus und hashe den. Ist portabel und ein wirklicher hash.

So und nun zu deinem Problem. Ich würde erstmal vorschlagen du nimmt eine BigInt Klasse. Auf die schnelle habe ich diese hier gefunden, macht eine passablen Eindruck.
--
Wer früher stirbt ist länger tot.

Dieser Post wurde am 21.11.2006 um 12:30 Uhr von (un)wissender editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
21.11.2006, 14:19 Uhr
~grimmel
Gast

Danke für die Hilfe...

naja...für meine Zwecke funktioniert es zu 100%. Bis auf eine genauigkeit von 10^-16. Habe das ausgiebige getestet. Auch mit double vektoren die absolut identisch sind oder auch nur auf < 10^-16 sich unterscheiden. Er produziert wirklich korrekte ergebnisse. Ich habe noch einen mix-value drin falls nur nuller auftauchen - den hab ich hier rausgenommen damit es übersichtlicher ist - aber war eh nur 2 zeilen dir draußen sind jetzt.

Big int? Danke für den Link - ich werds mir anschauen....

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: