Zaszczepianie generatora liczb losowych w JavaScript

372

Czy jest możliwe zaszczepienie generatora liczb losowych (Math.random) w JavaScript?

płaczliwy
źródło
nie jest jasne, czy chcesz go zaszczepić, aby uzyskać te same wyniki wielokrotnie dla różnych przebiegów testowych, czy też chcesz zaszczepić go „czymś wyjątkowym” na użytkownika dla lepszej losowości między użyciem.
simbo1905
2
Nie, niestety nie jest to możliwe. jsrand to mała biblioteka, którą napisałem, gdy potrzebowałem wysiewnego PRNG. Istnieją również inne, bardziej złożone biblioteki, w których można znaleźć googlowanie.
Domenico De Felice
4
Dodając do pytania: w jaki sposób dobrym pomysłem jest zaoferowanie PRNG bez możliwości jego wysiewu? Czy jest jakiś dobry powód?
Alan
Zobacz także stackoverflow.com/questions/424292
Palimondo

Odpowiedzi:

159

UWAGA: Pomimo (a raczej z powodu) zwięzłości i pozornej elegancji, algorytm ten nie jest wysokiej jakości pod względem losowości. Poszukaj np. Tych wymienionych w tej odpowiedzi, aby uzyskać lepsze wyniki.

(Pierwotnie dostosowany do sprytnego pomysłu przedstawionego w komentarzu do innej odpowiedzi).

var seed = 1;
function random() {
    var x = Math.sin(seed++) * 10000;
    return x - Math.floor(x);
}

Możesz ustawić seeddowolną liczbę, po prostu unikaj zera (lub dowolnej wielokrotności Math.PI).

Moim zdaniem elegancja tego rozwiązania wynika z braku jakichkolwiek „magicznych” liczb (oprócz 10000, co odpowiada mniej więcej minimalnej liczbie cyfr, którą należy wyrzucić, aby uniknąć nieparzystych wzorów - patrz wyniki o wartościach 10 , 100 , 1000 ). Brevity jest również miłe.

Jest nieco wolniejszy niż Math.random () (2 lub 3 razy), ale uważam, że jest tak szybki jak każde inne rozwiązanie napisane w JavaScript.

Antti Kissaniemi
źródło
20
Czy istnieje sposób, aby udowodnić, że RNG generuje liczby, które są równomiernie rozmieszczone? Eksperymentalnie wydaje się to: jsfiddle.net/bhrLT
Nathan Breit
6
6 000 000 operacji na sekundę jest dość szybkich, nie planuję generować więcej niż ~ 3 000 000 na kliknięcie. Żartuję, to jest genialne.
AMK
59
-1, To wcale nie jest jednolity sampler - jest on dość tendencyjny w stosunku do 0 i 1 (patrz jsfiddle.net/bhrLT/17 , co może chwilę potrwać). Kolejne wartości są skorelowane - co 355 wartości, a tym bardziej co 710, są powiązane. Proszę użyć czegoś bardziej przemyślanego!
spencer nelson
37
Pytanie nie dotyczy stworzenia kryptograficznie bezpiecznego generatora liczb losowych, ale czegoś, co działa w javascript, przydatnego do szybkich wersji demonstracyjnych itp. Wezmę coś szybkiego i prostego, co zapewni dobrze wyglądający rozkład ponad miliona liczb losowych w tym celu.
Jason Goemaat
15
Bądź ostrożny. Math.sin () może dawać różne wyniki na kliencie i serwerze. Używam Meteor (używa javascript na kliencie i serwerze).
Obiwahn
145

Zaimplementowałem wiele dobrych, krótkich i szybkich funkcji generatora liczb pseudolosowych (PRNG) w zwykłym JavaScript. Wszystkie z nich można wysiać i zapewnić dobrą jakość liczb.

Przede wszystkim zadbaj o prawidłową inicjalizację swoich PRNG. Większość poniższych generatorów nie ma wbudowanej procedury generowania nasion (dla uproszczenia), ale akceptuje jedną lub więcej 32-bitowych wartości jako stan początkowy PRNG. Podobne nasiona (np. Proste ziarno 1 i 2) mogą powodować korelacje w słabszych PRNG, w wyniku czego dane wyjściowe mają podobne właściwości (takie jak losowo generowane poziomy są podobne). Aby tego uniknąć, najlepszą praktyką jest inicjowanie PRNG z dobrze rozłożonym nasieniem.

Na szczęście funkcje skrótu są bardzo dobre w generowaniu zarodków PRNG z krótkich ciągów. Dobra funkcja skrótu generuje bardzo różne wyniki, nawet gdy dwa ciągi znaków są podobne. Oto przykład oparty na funkcji mieszania MurmurHash3:

function xmur3(str) {
    for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++)
        h = Math.imul(h ^ str.charCodeAt(i), 3432918353),
        h = h << 13 | h >>> 19;
    return function() {
        h = Math.imul(h ^ h >>> 16, 2246822507);
        h = Math.imul(h ^ h >>> 13, 3266489909);
        return (h ^= h >>> 16) >>> 0;
    }
}

Każde kolejne wywołanie funkcji powrotnej z xmur3produkcją nowego „Random” 32-bitową wartość skrótu, który będzie używany jako materiał siewny w PRNG. Oto jak możesz go użyć:

// Create xmur3 state:
var seed = xmur3("apples");
// Output four 32-bit hashes to provide the seed for sfc32.
var rand = sfc32(seed(), seed(), seed(), seed());

// Output one 32-bit hash to provide the seed for mulberry32.
var rand = mulberry32(seed());

// Obtain sequential random numbers like so:
rand();
rand();

Alternatywnie, po prostu wybierz dane zastępcze, którymi chcesz wypełnić ziarno, i przesuń generator kilka razy (12-20 iteracji), aby dokładnie wymieszać stan początkowy. Jest to często widoczne w referencyjnych implementacjach PRNG, ale ogranicza liczbę stanów początkowych.

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();

Dane wyjściowe tych funkcji PRNG generują dodatnią liczbę 32-bitową (od 0 do 2 32 -1), która jest następnie przekształcana na liczbę zmiennoprzecinkową między 0-1 (0 włącznie, 1 wyłącznie) równoważną Math.random(), jeśli chcesz liczb losowych określonego zakresu, przeczytaj ten artykuł na MDN . Jeśli chcesz tylko surowych bitów, po prostu usuń ostatnią operację dzielenia.

Należy również zwrócić uwagę na ograniczenia JS. Liczby mogą reprezentować tylko liczby całkowite do 53-bitowej rozdzielczości. W przypadku operacji bitowych liczba ta jest zmniejszana do 32. Utrudnia to implementację algorytmów napisanych w C lub C ++, które używają liczb 64-bitowych. Przeniesienie 64-bitowego kodu wymaga podkładek, które mogą drastycznie zmniejszyć wydajność. Ze względu na prostotę i wydajność rozważałem tylko algorytmy wykorzystujące matematykę 32-bitową, ponieważ jest ona bezpośrednio kompatybilna z JS.

Teraz przejdźmy do generatorów. (Utrzymuję pełną listę z odnośnikami tutaj )


sfc32 (prosty szybki licznik)

sfc32 jest częścią pakietu do testowania liczb losowych PractRand (który oczywiście przechodzi). sfc32 ma stan 128-bitowy i jest bardzo szybki w JS.

function sfc32(a, b, c, d) {
    return function() {
      a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0; 
      var t = (a + b) | 0;
      a = b ^ b >>> 9;
      b = c + (c << 3) | 0;
      c = (c << 21 | c >>> 11);
      d = d + 1 | 0;
      t = t + d | 0;
      c = c + t | 0;
      return (t >>> 0) / 4294967296;
    }
}

Morwa32

Mulberry32 jest prostym generatorem ze stanem 32-bitowym, ale jest niezwykle szybki i ma dobrą jakość (autor twierdzi, że przeszedł wszystkie testy pakietu testowego gjrand i ma pełny okres 32 , ale nie zweryfikowałem).

function mulberry32(a) {
    return function() {
      var t = a += 0x6D2B79F5;
      t = Math.imul(t ^ t >>> 15, t | 1);
      t ^= t + Math.imul(t ^ t >>> 7, t | 61);
      return ((t ^ t >>> 14) >>> 0) / 4294967296;
    }
}

Poleciłbym to, jeśli potrzebujesz tylko prostego, ale przyzwoitego PRNG i nie potrzebujesz miliardów liczb losowych (patrz problem z urodzinami ).

xoshiro128 **

Od maja 2018 r. Xoshiro128 ** jest nowym członkiem rodziny Xorshift autorstwa Vigna / Blackman (który napisał również xoroshiro, który jest używany w Chrome). Jest to najszybszy generator oferujący stan 128-bitowy.

function xoshiro128ss(a, b, c, d) {
    return function() {
        var t = b << 9, r = a * 5; r = (r << 7 | r >>> 25) * 9;
        c ^= a; d ^= b;
        b ^= c; a ^= d; c ^= t;
        d = d << 11 | d >>> 21;
        return (r >>> 0) / 4294967296;
    }
}

Autorzy twierdzą, że dobrze przechodzi testy losowości ( choć z zastrzeżeniami ). Inni badacze zauważyli, że niektóre testy w TestU01 nie udają się (szczególnie LinearComp i BinaryRank). W praktyce nie powinno to powodować problemów, gdy używane są zmiennoprzecinkowe (takie jak te implementacje), ale może powodować problemy, jeśli polegasz na surowych niskich bitach.

JSF (mały post Jenkinsa)

To jest JSF lub „smallprng” Boba Jenkinsa (2007), facet, który stworzył ISAAC i SpookyHash . To przechodzi testy PractRand i powinny być dość szybko, choć nie tak szybko jak SFC.

function jsf32(a, b, c, d) {
    return function() {
        a |= 0; b |= 0; c |= 0; d |= 0;
        var t = a - (b << 27 | b >>> 5) | 0;
        a = b ^ (c << 17 | c >>> 15);
        b = c + d | 0;
        c = d + t | 0;
        d = a + t | 0;
        return (d >>> 0) / 4294967296;
    }
}

LCG (alias Lehmer / Park-Miller RNG lub MCG)

LCG jest niezwykle szybki i prosty, ale jakość jego losowości jest tak niska, że ​​niewłaściwe użycie może faktycznie powodować błędy w twoim programie! Niemniej jednak jest znacznie lepszy niż niektóre odpowiedzi sugerujące użycie Math.sinlub Math.PI! Jest to jednak jedna linijka, co jest miłe :).

var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31;

Ta implementacja nazywa się minimalnym standardowym RNG, jak zaproponował Park – Miller w 1988 i 1993 r. I zaimplementowano w C ++ 11 as minstd_rand. Należy pamiętać, że stan jest 31-bitowy (31 bitów daje 2 miliardy możliwych stanów, 32 bity daje dwa razy więcej). Jest to rodzaj PRNG, który inni próbują zastąpić!

Będzie działał, ale nie użyłbym go, chyba że naprawdę potrzebujesz szybkości i nie zależy ci na jakości losowości (co w ogóle jest losowe?). Idealne do gry jam, demo lub coś takiego. LCG cierpią na korelacje nasion, więc najlepiej odrzucić pierwszy wynik LCG. A jeśli nalegasz na użycie LCG, dodanie wartości przyrostowej może poprawić wyniki, ale prawdopodobnie jest to ćwiczenie bezcelowe, gdy istnieją znacznie lepsze opcje.

Wydaje się, że istnieją inne mnożniki oferujące stan 32-bitowy (zwiększona przestrzeń stanu):

var LCG=s=>()=>(s=Math.imul(741103597,s)>>>0)/2**32;
var LCG=s=>()=>(s=Math.imul(1597334677,s)>>>0)/2**32;

Te wartości LCG pochodzą z: P. L'Ecuyer: Tabela liniowych kongruencjalnych generatorów o różnych rozmiarach i dobrej strukturze sieci, 30 kwietnia 1997 r.

bryc
źródło
5
To niesamowita odpowiedź. Na pewno wrócę do tego.
DavidsKanal
1
Wierzę, że wartości, które zacytowałeś w „Tabelach liniowych generatorów prądów zbieżnych ...” Pierre'a L'ecuyera, mogą przekroczyć maksymalny rozmiar całkowity w Javascript. Maksymalne ziarno (2 ^ 32-1) * 741103597 ≈ 3e18, które jest większe niż maksymalny rozmiar int JavaScript ≈ 9e15. Myślę, że następujące wartości z książki Pierre'a mają największy okres, w rodzimych granicach: seed = (seed * 185852 + 1) % 34359738337.
Lachmanski
1
@Lachmanski prawda, ale są one ograniczone 32-bitami (i Park-Miller 31-bitami). Użycie Math.imulpozwala na przepełnienie, tak jak w przypadku mnożenia w C na 32-bitowych liczbach całkowitych. Sugerujesz, że LCG wykorzystuje pełny zakres przestrzeni całkowitej JS, co jest zdecydowanie interesującym obszarem do zbadania. :)
bryc
1
To jest niesamowite! Czy mogę po prostu skopiować sfc32 do programu LGPL?
user334639,
4
@ blobber2 nie jestem pewien, co masz na myśli, ale oryginalny kod jest stąd (wraz z innymi): github.com/bryc/code/blob/master/jshash/PRNGs.md . mniej więcej istota w repozytorium :-)
bryc
39

Nie, ale oto prosty generator pseudolosowy, implementacja Multiply-with-carry, którą zaadaptowałem z Wikipedii (od tego czasu został usunięty):

var m_w = 123456789;
var m_z = 987654321;
var mask = 0xffffffff;

// Takes any integer
function seed(i) {
    m_w = (123456789 + i) & mask;
    m_z = (987654321 - i) & mask;
}

// Returns number between 0 (inclusive) and 1.0 (exclusive),
// just like Math.random().
function random()
{
    m_z = (36969 * (m_z & 65535) + (m_z >> 16)) & mask;
    m_w = (18000 * (m_w & 65535) + (m_w >> 16)) & mask;
    var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
    result /= 4294967296;
    return result;
}

EDYCJA: naprawiono funkcję początkową poprzez jej zresetowanie m_z
EDIT2: Naprawiono poważne błędy implementacyjne

Antti Kissaniemi
źródło
3
Czy ktoś przetestował tę funkcję pod kątem losowości?
Justin
3
Jest to losowy generator multiply-with-carry (MWC) z dość długim okresem. Na podstawie wikipedii Generatory liczb losowych
Michael_Scharf
10
seedFunkcja nie zresetować generatora liczb losowych, ponieważ mz_zzmienna ulega zmianie, gdy random()jest tzw. Dlatego ustaw mz_z = 987654321(lub dowolną inną wartość) wseed
Michael_Scharf
Kiedy używam go z moim generatorem losowych kolorów (HSL), generuje on tylko kolory zielony i cyjan. Oryginalny generator losowy generuje wszystkie kolory. Więc to nie to samo lub to nie działa.
Tomas Kubes,
@Michael_Scharf 1) Zmiana nasion m_w, nie m_z. 2) Oba m_wi m_zzmieniają się w oparciu o swoje poprzednie wartości, więc modyfikuje wynik.
ESL
26

Algorytm Antti Sykäri jest ładny i krótki. Początkowo zrobiłem odmianę, która zastąpiła JavaScript Math.random JavaScript, gdy wywołujesz Math.seed (s), ale potem Jason skomentował, że zwrócenie funkcji byłoby lepsze:

Math.seed = function(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

// usage:
var random1 = Math.seed(42);
var random2 = Math.seed(random1());
Math.random = Math.seed(random2());

Daje to kolejną funkcjonalność, której Javascript nie ma: wiele niezależnych generatorów losowych. Jest to szczególnie ważne, jeśli chcesz mieć jednocześnie wiele powtarzalnych symulacji.


źródło
3
Jeśli zwrócisz funkcję zamiast ustawienia Math.random, które pozwoli ci mieć wiele niezależnych generatorów, prawda?
Jason Goemaat
1
Pamiętaj, aby zobaczyć powyższe komentarze dotyczące rozkładu losowości, jeśli jest to dla Ciebie ważne: stackoverflow.com/questions/521295/…
jocull
Jak losy generowane przez to mogą się powtarzać?
Nadal podaje
za każdym razem, gdy Math.seed(42);to robisz , resetuje funkcję, więc jeśli var random = Math.seed(42); random(); random();dostaniesz 0.70..., to 0.38.... Jeśli zresetujesz go, dzwoniąc var random = Math.seed(42);ponownie, to następnym razem, gdy zadzwonisz random(), dostaniesz 0.70...ponownie, a następnym razem 0.38...znowu.
WOUNDEDStevenJones
1
Proszę nie używać tego. Poświęć trochę czasu, aby zamiast tego użyć lokalnej zmiennej o nazwie randomzamiast nadpisania natywnej funkcji javascript. Zastąpienie Math.randommoże spowodować, że kompilator JIST nie zoptymalizuje całego kodu.
Jack Giffin,
11

Zobacz prace Pierre'a L'Ecuyera sięgające końca lat 80. i początku lat 90. Są też inni. Samo tworzenie (pseudo) generatora liczb losowych, jeśli nie jesteś ekspertem, jest dość niebezpieczne, ponieważ istnieje wysokie prawdopodobieństwo, że wyniki nie będą statystycznie losowe lub będą miały krótki okres. Pierre (i inni) stworzyli kilka dobrych (pseudo) generatorów liczb losowych, które są łatwe do wdrożenia. Używam jednego z jego generatorów LFSR.

https://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf

Phil Troy

użytkownik2383235
źródło
1
Świetna odpowiedź, ale nie związana z javascript :)
Nikolay Fominyh
3
Kod do implementacji pracy profesora L'Ecuyera jest publicznie dostępny dla java i jest łatwy do przetłumaczenia przez większość programistów na Javascript.
user2383235
6

Łącząc niektóre z poprzednich odpowiedzi, jest to funkcja losowa, której szukasz:

Math.seed = function(s) {
    var mask = 0xffffffff;
    var m_w  = (123456789 + s) & mask;
    var m_z  = (987654321 - s) & mask;

    return function() {
      m_z = (36969 * (m_z & 65535) + (m_z >>> 16)) & mask;
      m_w = (18000 * (m_w & 65535) + (m_w >>> 16)) & mask;

      var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
      result /= 4294967296;
      return result;
    }
}

var myRandomFunction = Math.seed(1234);
var randomNumber = myRandomFunction();
użytkownik3158327
źródło
4
Daje to bardzo podobne wyniki na początku sekwencji z różnymi nasionami. Na przykład Math.seed(0)()zwraca 0.2322845458984375i Math.seed(1)()zwraca 0.23228873685002327. Wydaje się, że zmiana obu m_wi m_zwedług nasion pomaga. var m_w = 987654321 + s; var m_z = 123456789 - s;daje dobry rozkład pierwszych wartości dla różnych nasion.
niezdefiniowany
1
@ Niezdefiniowany opisany problem został naprawiony od ostatniej edycji, był to błąd w implementacji MWC.
bryc
Ładnie działa teraz, od stycznia 2020 r. Ziarno z 0, dostaje 0,7322976540308446. Nasiona z 1, 0,16818441334180534, z 2: 0,6040864314418286, z 3: 0,03998844954185188. Dziękuję wam obu!
Eureka
3

Napisanie własnego pseudolosowego generatora jest dość proste.

Sugestia Dave'a Scotese'a jest użyteczna, ale jak zauważyli inni, nie jest ona dość jednolicie rozłożona.

Nie dzieje się tak jednak z powodu całkowitej liczby argumentów grzechu. Jest tak po prostu z powodu zasięgu grzechu, który okazuje się być jednowymiarową projekcją koła. Jeśli zamiast tego przyjmiesz kąt koła, będzie on jednolity.

Więc zamiast sin (x) użyj arg (exp (i * x)) / (2 * PI).

Jeśli nie podoba ci się porządek liniowy, zmieszaj go nieco z xor. Faktyczny czynnik też nie ma tak wielkiego znaczenia.

Aby wygenerować n pseudolosowych liczb, można użyć kodu:

function psora(k, n) {
  var r = Math.PI * (k ^ n)
  return r - Math.floor(r)
}
n = 42; for(k = 0; k < n; k++) console.log(psora(k, n))

Należy również pamiętać, że nie można używać pseudolosowych sekwencji, gdy potrzebna jest prawdziwa entropia.

Lajos Bodrogi
źródło
Nie jestem ekspertem, ale sekwencyjne nasiona mają stały wzór . Kolorowe piksele mają> = 0,5. Zgaduję, że to tylko iteracja w promieniu w kółko?
bryc
1

Math.randomnie, ale uruchomiona biblioteka rozwiązuje ten problem. Ma prawie wszystkie rozkłady, jakie możesz sobie wyobrazić, i obsługuje generowanie liczb losowych. Przykład:

ran.core.seed(0)
myDist = new ran.Dist.Uniform(0, 1)
samples = myDist.sample(1000)
Ulf Aslak
źródło
-1

Napisałem funkcję, która zwraca rozstawioną liczbę losową, używa Math.sin, aby mieć długą liczbę losową i używa zarodka do wybierania liczb z tego.

Posługiwać się :

seedRandom("k9]:2@", 15)

zwróci liczbę początkową; pierwszym parametrem jest dowolna wartość ciągu; twoje nasienie. drugim parametrem jest liczba cyfr, które powrócą.

     function seedRandom(inputSeed, lengthOfNumber){

           var output = "";
           var seed = inputSeed.toString();
           var newSeed = 0;
           var characterArray = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','y','x','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','U','R','S','T','U','V','W','X','Y','Z','!','@','#','$','%','^','&','*','(',')',' ','[','{',']','}','|',';',':',"'",',','<','.','>','/','?','`','~','-','_','=','+'];
           var longNum = "";
           var counter = 0;
           var accumulator = 0;

           for(var i = 0; i < seed.length; i++){
                var a = seed.length - (i+1);
                for(var x = 0; x < characterArray.length; x++){
                     var tempX = x.toString();
                     var lastDigit = tempX.charAt(tempX.length-1);
                     var xOutput = parseInt(lastDigit);
                     addToSeed(characterArray[x], xOutput, a, i); 
                }                  
           }

                function addToSeed(character, value, a, i){
                     if(seed.charAt(i) === character){newSeed = newSeed + value * Math.pow(10, a)}
                }
                newSeed = newSeed.toString();

                var copy = newSeed;
           for(var i=0; i<lengthOfNumber*9; i++){
                newSeed = newSeed + copy;
                var x = Math.sin(20982+(i)) * 10000;
                var y = Math.floor((x - Math.floor(x))*10);
                longNum = longNum + y.toString()
           }

           for(var i=0; i<lengthOfNumber; i++){
                output = output + longNum.charAt(accumulator);
                counter++;
                accumulator = accumulator + parseInt(newSeed.charAt(counter));
           }
           return(output)
      }
Tyler Hudson
źródło
1
Wytworzone przez nie sekwencje liczb tak naprawdę nie przybliżają właściwości sekwencji liczb losowych. Wygeneruj z nim 15 liczb, a wynikowy ciąg prawie zawsze zaczyna się na przykład od 7 dla prawie dowolnego klucza, na przykład.
Gabriel,
-2

Proste podejście do ustalonego materiału siewnego:

function fixedrandom(p){
    const seed = 43758.5453123;
    return (Math.abs(Math.sin(p)) * seed)%1;
}
Carlos Oliveira
źródło
-6

Dla liczby od 0 do 100.

Number.parseInt(Math.floor(Math.random() * 100))
Lord Elrond
źródło
3
Pytanie dotyczy wysiewu w Math.randomtaki sposób, że za każdym razem, gdy Math.randomzostanie zaszczepiony tym samym ziarnem, wytworzy tę samą kolejną liczbę liczb losowych. To pytanie nie dotyczy, powiedzmy, faktycznego użycia / demonstracji Math.random.
Jack Giffin,