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

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Fibonacci Hash”

  1. Daniel said
    July 2, 2018 at 4:34 AM

    Here’s a solution in Haskell.

    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
    July 2, 2018 at 4:36 AM

    Formatted:

    import Data.Bits

fibhash :: Word -> Word
fibhash h = (h * 11400714819323198485) `shiftR` 54
  3. Milbrae said
    July 7, 2018 at 7:06 PM

    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

Leave a comment