import type { BigDecimal } from './type'

export const squareRoot = ({ value, decimals }: BigDecimal): BigDecimal => {
  // Adjust decimals to be a multiple of 2
  const adjustedDecimals = decimals % 2 === 0 ? decimals : decimals + 1
  const adjustedValue = value * 10n ** BigInt(adjustedDecimals - decimals)
  return {
    value: squareRootBigInt(adjustedValue),
    decimals: Math.floor(adjustedDecimals / 2),
  }
}

const squareRootBigInt = (value: bigint): bigint => {
  if (value === 0n) {
    return 0n
  }
  const isNegative = value < 0n
  const absValue = isNegative ? -value : value
  if (absValue < 2n) {
    return absValue
  }
  if (absValue === 4n) {
    return isNegative ? -2n : 2n
  }

  const newtonIteration = (n: bigint, x0: bigint): bigint => {
    const x1 = (n / x0 + x0) >> 1n
    if (x0 === x1 || x0 === x1 - 1n) {
      return x0
    }
    return newtonIteration(n, x1)
  }

  const result = newtonIteration(absValue, 1n)
  return isNegative ? -result : result
}