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.

Advertisements

Pages: 1 2

3 Responses to “Fibonacci Hash”

  1. Daniel said

    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

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: