Powers of 2 in lexical order yield decibels (2019) | Hacker News Reader

Powers of 2 in lexical order yield decibels (2019)

solipsys.co.uk

40 pointsjohndcook10 comments

The lexicographic sort isn't arbitrary:

  1    = 2^0 / 1                                           ~= 2^0
  1.28 = 2^7 / 100   ~= 2^7/(2^6.6439)  ~= 2^(7 - 6.6439)  ~= 2^0.3561
  1.6  = 2^4 / 10    ~= 2^4/(2^3.3219)  ~= 2^(4 - 3.3219)  ~= 2^0.6780
  2.00 = 2^1 / 1                                           ~= 2^1
  2.56 = 2^8 / 100   ~= 2^8/(2^6.6439)  ~= 2^(8 - 6.6439)  ~= 2^1.3561
  3.2  = 2^5 / 10    ~= 2^5/(2^3.3219)  ~= 2^(5 - 3.3219)  ~= 2^1.6780 
  4.0  = 2^2 / 1                                            = 2^2
  6.4  = 2^6 / 10    ~= 2^6/(2^3.3219)  ~= 2^(6 - 3.3219)  ~= 2^2.6780
  8.0  = 2^3 / 1                                            = 2^3

Differences between those powers of two:

These increments are close to 1/3 which is what you need to divide the musical octave (frequency doubling) into 3 steps:

  2^(0/3)  = 1
  2^(1/3) ~= 1.2599
  2^(2/3) ~= 1.5784
  2^(3/3)  = 2

There is a well-known relationship that when you divide a frequency factor of 10 into 10 steps, you get approximately three steps per musical octave (frequency doubling). You can see this on any 31 band graphical equalizer. This relies on the "coincidence" seen the other table shown:

  10^0.0  = 1
  10^0.1 ~= 1.2589
  10^0.2 ~= 1.5849
  10^0.3  = 1.9953

The geometric decade steps provide a close-to-exact doubling also, every three steps.

Right, so where did I get those 6.6439 and 3.3219 numbers? Those are just the approximations of log2(100) and log2(10).

At the heart of the "lexicographic coincidence" seems to be the observation that these logarithms have .64 and .32 fractional parts, or about 2/3 and 1/3.

So for instance since 100 = 2^(log2(100), we can rewrite 1.28 as 128 / 2^(log2(100) which is 2^7/2^(log2(100)).

So then we have powers of two on top and bottom and can subtract them: 2^(7 - log2(100)), which is where we get 7 - 6.6439 = 0.3561.

Pulling a bit out, to try to find intuition:

   log_2(10) ~= 10/3

   10^(1/10) ~= cubeRoot(2)

So the first 10 decibels are ~= the first 10 powers of CubeRoot(2)

"dividing by 10^n until you reach 1<y<10" is the operation: CubeRoot(2)^k -> CubeRoot(2) ^ (k mod 10)

So, the scaling operation on 2^m = CubeRoot(2)^3m is going to land on multiples of 1/3, and then sorting will put them in order.

You want 10 values, so you take the first 10 powers of 2. CubeRoot(2)^{0..9}

Remaining question: why do you get 10 distinct values? Well, it's because 2^a and 2^b only scale to the same value if (by logarithms) a - b = 10j.

For all intents and purposes multiplying by 2 and multiplying it by a power of 10 until it's between 1 and 10 is equivalent to the dynamical system called an irrational rotation.

This equivalence isn't particularly deep but what is important is that irrational rotations are uniquely ergodic. This means that for all intents and purposes this procedure with any starting point will give a set of points that uniformly cover the unit interval (or in this case 1 to 10, logarithmically).

It also helps that 2^10 is a near miss for 10^3.

I’m not sure it is with any starting point. https://mathworld.wolfram.com/PowerFractionalParts.html describes a similar sequence, of which Hardy and Littlewood proved it is equidistributed for almost all real numbers (and the exceptions aren’t all trivial. The golden ratio and 1+√2 are exceptions, for example)

It is, but you're right to question it because it's a very nontrivial property that makes irrational rotations a bit of a special case.

The fact that it's uniquely ergodic (which roughly means that the uniform Lebesgue measure is the only measure that's invariant under irrational rotation) is required to ensure it works for all starting points. Most ergodic systems only ensure that it works for almost all starting points i.e. all starting points except for a measure 0 set.

I think this is a lovely description/derivation:

https://twitter.com/icecolbeveridge/status/14984109481173401...

https://www.youtube.com/watch?v=VEPRK3O9K2s

2 is roughly 10^(0.3)

Suppose that you take powers of 2, and then divide by 10 if it's greater than 10.

    2^7 ~= (10^(0.3))^7 = 10^2.1 --> 10^(2.1 mod 1) = 10^0.1
    2^4 ~= (10^(0.3))^4 = 10^1.2 --> 10^(1.2 mod 1) = 10^0.2
    2^1 ~= (10^(0.3))^1 = 10^0.3 --> 10^(0.3 mod 1) = 10^0.3
    2^8 ~= (10^(0.3))^8 = 10^2.4 --> 10^(2.4 mod 1) = 10^0.4
    ...

where the arrow denotes dividing out as many powers of 10 as you can.

It seems surprising that the numbers are in the right order but of course it's not. Doing lexicographic sort and then dividing out powers of 10 is the same as dividing out powers of 10 and then just doing a numeric sort. So the lex sort is a sort of (accidental) legerdemain here.

The powers to which you raise 2 are given by the inverses of 1, 2, 3 etc mod 10. In other words you're raising (10^0.3) to a power k, chosen so that the remainder 0.3 * k mod 1 is the multiple of 0.1 that you need.

    1 / 3 mod 10 = 7
    2 / 3 mod 10 = 4
    3 / 3 mod 10 = 1
    4 / 3 mod 10 = 8
    ...

They are also given by multiples of 7 mod 3.

Does this generalize? Like taking 2^0, 2^1, ..., 2^99 -> lexicographical sort -> putting the decimal point, and then comparing to 10^0.00, 10^0.01, ...?

I just tried this in python, and it's pretty damn close.

    2^(10/3) ~= 10

    2^(100/30) ~= 100

so it should work.

And I think this trick should work for powers of any a in any base b where there is a k such that

    a^(b/k) ~= b

aka

    k ~= b * log a / log b
    a ~= e^ (k * (log_e b)/ b)

and if b is the base of your logarithm, this simplifies to

    k ~= b * log a
    a = b^(k/b)

   10 * log 2 = 3.0103
    
   10 * log 5 = 6.9897

, so 5 works too....

    >>> approx = lambda a: sorted( [float(scale(str(a**k)[:3])) for k in range(0,10)])

    >>> [10**(k/10.0) for k in range(0,10)]

    [1.0, 1.25, 1.58, 1.99, 2.51, 3.16, 3.98, 5.01, 6.30, 7.94]

    >>> approx(2)
    [1.0, 1.28, 1.60, 2.00, 2.56, 3.20, 4.00, 5.12, 6.40, 8.00]

    >>> approx(5)
    [1.0, 1.25, 1.56, 1.95, 2.50, 3.12, 3.90, 5.00, 6.25, 7.81]

Is it a coincidence that this works for 2 and 5 in base 10, while 2*5 = 10 ?

Reply on news.ycombinator.com