## Fibonacci Hash

### June 19, 2018

We implement Fibonacci hash in Scheme, which requires an explicit modulo operation because integer operations overflow to bigints instead of wrapping around:

```(define (fibhash h)
(let ((two64 (expt 2 64)) (two54 (expt 2 54)))
(quotient (modulo (* h 11400714819323198485) two64)
two54)))```

Here are some examples:

```> (fibhash 123412341234)
831
> (fibhash 12341234123412341234)
269
> (fibhash 1234123412341234123412341234)
20```

You can run the program at https://ideone.com/AB6Q0h.

Pages: 1 2

### 3 Responses to “Fibonacci Hash”

1. Daniel said

```import Data.Bits

fibhash :: Word -> Word
fibhash h = (h * 11400714819323198485) `shiftR` 54
```

Example (excluding out-of-range literal warning):

```> fibhash 123412341234
831
> fibhash 12341234123412341234
269
> fibhash 1234123412341234123412341234
20
```
2. Daniel said

Formatted:

```import Data.Bits

fibhash :: Word -> Word
fibhash h = (h * 11400714819323198485) `shiftR` 54
```
3. Milbrae said

Another implementation in D

```import std.stdio;

ulong fibhash(ulong n, ulong mul=11400714819323198485UL, ulong shift=54UL) {
return (n * mul) >> shift;
}

void main() {
1234567890UL.fibhash.writeln;
}```

449