module Math.Utils where

import Data.Bits

{- |
>>> floorSqrt 0
0
>>> floorSqrt 1
1
>>> floorSqrt 2
1
>>> floorSqrt 4
2
>>> floorSqrt (12345 * 12345)
12345
>>> floorSqrt (2^52 + 2^27)
67108864
>>> floorSqrt maxBound
3037000499
-}
floorSqrt :: Int -> Int
floorSqrt :: Int -> Int
floorSqrt Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 = Int
n
  | Bool
otherwise =
      let !k :: Int
k = Int
32 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR (Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)) Int
1
          !x0 :: Int
x0 = Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftL Int
1 Int
k
          !x1 :: Int
x1 = Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR (Int
x0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR Int
n Int
k) Int
1
       in Int -> Int -> Int
go Int
x0 Int
x1
  where
    go :: Int -> Int -> Int
go !Int
x !Int
x'
      | Int
x' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
x = Int -> Int -> Int
go Int
x' (Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftR (Int
x' Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
forall a. Integral a => a -> a -> a
quot Int
n Int
x') Int
1)
      | Bool
otherwise = Int
x

{- |
BSR (Bit Scan Reverse)

>>> floorLog2 0
-1
>>> floorLog2 1
0
>>> floorLog2 2
1
>>> floorLog2 1023
9
>>> floorLog2 1024
10
>>> floorLog2 maxBound
62
-}
floorLog2 :: Int -> Int
floorLog2 :: Int -> Int
floorLog2 Int
x = Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Int
x
{-# INLINE floorLog2 #-}