6

I'm trying to understand a constant 0x9e3779b9.

What kind of data is this? It's not binary, not decimal, what is this?

It's a constant used on the TEA algorithm. It says it's derived from the golden number, but the golden number is 1.618?

gnat
  • 21,442
  • 29
  • 112
  • 288
pandr01d
  • 101
  • 1
  • 1
  • 4
  • 1
    Do you mean the number format or how did they come up with the value? – Matthew Whited Mar 30 '11 at 13:17
  • what about the format? i've never seen it... i read that the value is from (1 + √5)/(2^31) but after i try it the result is 2654435769.4972302964775847707926? – pandr01d Mar 30 '11 at 13:19
  • 13
    In most C style languages `0x` is a prefix for a hexadecimal number. I'm wondering if that is the hex format for the floating point representation of the golden number. Of course that would beg the question of why store an FP value as an integer? Perhaps they optimized the implementation of the TEA algorithm to work with integers instead of floating point values? – Berin Loritsch Mar 30 '11 at 13:21
  • It is http://en.wikipedia.org/wiki/Hexadecimal format. – TZHX Mar 30 '11 at 13:22
  • i think they store it as integer because later it would be multiplied by some other number – pandr01d Mar 30 '11 at 13:28
  • Plugging 9e3779b9 hex into Windows calculator and converting to decimal gives 2654435769. – Simon B Jul 22 '15 at 08:08
  • https://softwareengineering.stackexchange.com/q/402542/353174 – bkgs Dec 16 '19 at 09:54

4 Answers4

36

I think this StackOverflow question answers it:

https://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine

Essentially, it is a magic number, derived from the Golden Ratio irrational number, using the steps:

  1. phi = (1 + sqrt(5)) / 2 = 1,6180339887498948482045868343656.

  2. Then after it, it is calculated 2^32 / phi which results in 2 654 435 769,4972302964775847707926.

  3. Truncate it to have only its integer part 2 654 435 769

  4. Convert it to hexadecimal and you will get 9E37 79B9 (On Windows Calculator choose Qword)

Being it a pre-calculated integer, instead of a taking a float every time and do the computation, you accelerate the calculus of each hash done after.

The notation 0x is for a hexadecimal number, or base 16. The benefit of a base 16 number is that each pair of digits represents one byte exactly. Given a little practice, you can almost see the bit pattern in your mind, assuming you've ever worked with binary numbers.

sergiol
  • 157
  • 1
  • 6
Berin Loritsch
  • 45,784
  • 7
  • 87
  • 160
  • I had just found something similar +1 – Matt Ellen Mar 30 '11 at 13:31
  • okay i guess i have to understand the hash function first – pandr01d Mar 30 '11 at 13:45
  • 1
    @Berin - is there a reason for this particular number? You presumably just need an irregular set of 0 and 1. Is the golden ratio link just arbitrary or is there some deeper mathematical logic? – Martin Beckett Mar 30 '11 at 20:08
  • People with better understanding of hash algorithms would be better suited for that answer. My understanding of this "magic number" is that it is mathematically random, but that's where it ends. – Berin Loritsch Mar 30 '11 at 22:53
  • In the link I provided, the selected answer says that the number is _derived_ from the golden ratio. The answer also has the math that created the answer. – Berin Loritsch Mar 30 '11 at 23:39
  • I can vouch for seeing bit patterns, although I personally find it easier to think in octal. – Ape-inago Apr 01 '11 at 10:58
9

As others have said, the constant is an integer in hexadecimal form. Specifically, it is a 32-bit integer in hexadecimal form. If the constant is a signed integer, then 0x9e3779b9 is negative 1640531527 decimal in two's complement form; therefore, it may be a scaled integer fraction that has been adjusted to deal with non-integral of 2 related problems.

Two's complement negative to positive conversion in hex 

0x9e3779b9 ⊕ 0xffffffff + 0x00000001 = 0x61C88647 = 1640531527 in decimal

or using the 1's complement operator ~ in the C family of languages

~0x9e3779b9 + 0x00000001 = 0x61C88647 = 1640531527 in decimal

Two's complement negative to positive conversion in binary

10011110001101110111100110111001 ⊕ 11111111111111111111111111111111 + 00000000000000000000000000000001 =  01100001110010001000011001000111 = 1640531527 in decimal
bit-twiddler
  • 2,648
  • 1
  • 16
  • 17
2

The number comes from the hexadecimal representation of the golden ratio.

Just like 1/4 is 0.25 (25/100) in decimal is 0.4 (4/16) in hex, the fractional portion of the golden ratio has a different representation in hex than in decimal.

You are not dividing 0x9e3779b9 by 10^8, but 16^8 (or 2/32), and 0x9e3779b9/0x100000000 = 2654435769/4294967296 ≈ 0.6180339886

gnat
  • 21,442
  • 29
  • 112
  • 288
SomeRandomGuy
  • 21
  • 1
-1

As others pointed out here and on https://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine, the number is indeed constructed from the golden ratio.

But there is another important reason why numbers such as pi, phi or e are used in cryptographic functions. Of course, in principle, any "reasonably random" bit sequence could be used as a constant. But it puts the creator of the function under suspicion of having engineered the value, e.g. in order to create a particular weakness in the algorithm (known only to him) that he can then exploit when you use his function.

By constructing the value from well-known "natural" constants, this kind of suspicion can be averted to some degree.

Community
  • 1
mindriot
  • 264
  • 2
  • 4