module Exercise05 where

import Data.Bits ( Bits((.&.)) )

-- May or may not be useful: computes the logarithm base 2 (rounded down) of the given number.
-- You don't have to move this into the WETT tags if you want to use it.
log2 :: (Integral a, Num b) => a -> b
log2 = let go acc n = if n <= 1 then acc else go (acc + 1) (n `div` 2) in go 0

{-WETT-}

decompose :: [Integer] -> [Integer]
decompose ds@(d:_) = g ds (log2 d) []

g :: [Integer] -> Integer -> [Integer] -> [Integer]
g _ (-1) xs = xs
g ds i xs = let (res, _) = f ds i in g ds (i-1) (if null xs && res == 0 then [] else res : xs)

f :: [Integer] -> Integer -> (Integer, Integer)
f [x] i = (min (x .&. (2^i)) 1, div x (2^i))
f (x:xs) i = let (sub, p) = f xs i in ((fst(f [x] i) * (p - sub)) + (div x (2^i) * sub), p * div x (2^i))

{-TTEW-}