Связь между числом умножений для вычисления n ^ k и двоичной кросс-суммой n

Question

Использование тождеств ...

       x^0 = 1
    x^(2n) = (x*x)^n
  x^(2n+1) = x * (x*x)^n

... мы можем написать функцию на Haskell, которая вычисляет k th степень x с меньшим, чем k умножений.

nat_pow :: Double -> Integer -> Double
nat_pow x 0 = 1
nat_pow x k
  | m==0 = nat_pow (x*x) n            -- k == 2*n  <=>  m == 0
  | otherwise = x * nat_pow (x*x) n   -- k == 2*n+1
  where
    (n,m) = k `divMod` 2              -- n <- k `div` 2; m <- k `mod` 2

Например:

nat_pow x 6
= nat_pow x^2 3
= x^2 * natpow (x^2)^2 1
= x^2 * (x^2)^2  *  natpow ((x^2)^2)^2) 0
= x^2 * (x^2)^2  *         1

Далее, мы можем посмотреть на сумму кросс-суммы числа с основанием 2.t.

crossSum_2 42 = 3                     (because (42)_10 = (101010)_2)

Вопрос: Какая связь между количеством умножений nat_pow x k требуется и crossSum_2 k?

Что у меня до сих пор :

Пусть Q (k) - двоичная кросс-сумма k; M (k) число умножений nat_pow n k. Тогда я вижу, что

M(2k)   = 1 + M(k)
M(2k+1) = 1 + M(2k)

Q(2k)   =     Q(k)
Q(2k+1) = 1 + Q(k)

Так что можно сказать, что

1. Q (n) - количество «нечетных» случаев nat_pow; следовательно,
2. M (n)> = Q (n) всегда выполняется.

Тем не менее, я думаю, что должно быть что-то еще.

Answer 1

M(2k)   = 1 + M(k)
M(2k+1) = 1 + M(2k)

Q(2k)   =     Q(k)
Q(2k+1) = 1 + Q(k)

Фактически мы можем сделать параллель между двумя определениями еще ближе.В M(2k+1) = 1 + M(2k) мы можем развернуть уравнение, которое мы имеем для M(2k):

M(2k)   =     1 + M(k)
M(2k+1) = 1 + 1 + M(k)

Q(2k)   =     Q(k)
Q(2k+1) = 1 + Q(k)

Теперь ясно, что по сравнению с Q, M добавляет еще один на каждый «рекурсивный вызов»,Таким образом, M(k) будет Q(k) плюс общее количество рекурсивных вызовов M, что в данном случае также является общим числом битов в k.(Существует только одна морщина: мы не писали о базовых случаях для Q и M выше. Как только мы учтем это, это изменит ответ? Как должны выглядеть базовые случаи в контрфактуальноммир, чтобы дать другой ответ на вопрос "это меняет ответ?"?)