// Copyright 2023 - 2024 Matt Borland
// Copyright 2023 - 2024 Christopher Kormanyos
// Copyright 2025 - 2026 Justin Zhu
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt

#ifndef BOOST_DECIMAL_DETAIL_CMATH_IMPL_SQRT_LOOKUP_HPP
#define BOOST_DECIMAL_DETAIL_CMATH_IMPL_SQRT_LOOKUP_HPP

// ============================================================================
// Decimal sqrt lookup tables (SoftFloat-style, optimized for base-10)
//
// Design:
// - 90 entries covering range [1, 10) with step = 0.1
// - Perfect decimal alignment: index = (x - 1) * 10
// - k0[i] = 10^16 / sqrt(1 + i * 0.1) at left edge of bin
// - k1[i] = k0[i] - k0[i+1] (slope for linear interpolation)
//
// Usage:
//   int index = int((x - 1) * 10);  // x in [1, 10)
//   T eps = (x - 1) * 10 - index;   // fractional part in [0, 1)
//   T r = (k0[index] - k1[index] * eps) / 10^16;  // 1/sqrt(x) approximation
//
// Table lookup gives ~10 bits precision.
// Combined with Newton refinement in approx_recip_sqrt_impl.hpp, reaches 32+ bits.
// ============================================================================

#ifndef BOOST_DECIMAL_BUILD_MODULE
#include <cstdint>
#endif

namespace boost {
namespace decimal {
namespace detail {
namespace sqrt_lookup {

// recip_sqrt_k0s[i] = 10^16 / sqrt(1 + i * 0.1) at left edge of bin
static constexpr std::uint64_t recip_sqrt_k0s[90] = {
    10000000000000000ULL, 9534625892455923ULL, 9128709291752768ULL, 8770580193070292ULL,
    8451542547285165ULL, 8164965809277260ULL, 7905694150420948ULL, 7669649888473704ULL,
    7453559924999298ULL, 7254762501100116ULL, 7071067811865475ULL, 6900655593423542ULL,
    6741998624632420ULL, 6593804733957870ULL, 6454972243679028ULL, 6324555320336758ULL,
    6201736729460422ULL, 6085806194501845ULL, 5976143046671968ULL, 5872202195147034ULL,
    5773502691896257ULL, 5679618342470648ULL, 5590169943749474ULL, 5504818825631803ULL,
    5423261445466404ULL, 5345224838248487ULL, 5270462766947298ULL, 5198752449100363ULL,
    5129891760425770ULL, 5063696835418333ULL, 5000000000000000ULL, 4938647983247948ULL,
    4879500364742665ULL, 4822428221704121ULL, 4767312946227961ULL, 4714045207910316ULL,
    4662524041201568ULL, 4612656040144425ULL, 4564354645876384ULL, 4517539514526256ULL,
    4472135954999579ULL, 4428074427700476ULL, 4385290096535146ULL, 4343722427630693ULL,
    4303314829119352ULL, 4264014327112208ULL, 4225771273642582ULL, 4188539082916955ULL,
    4152273992686998ULL, 4116934847963091ULL, 4082482904638630ULL, 4048881650894580ULL,
    4016096644512494ULL, 3984095364447978ULL, 3952847075210474ULL, 3922322702763680ULL,
    3892494720807614ULL, 3863337046431278ULL, 3834824944236852ULL, 3806934938134404ULL,
    3779644730092272ULL, 3752933125204007ULL, 3726779962499649ULL, 3701166050988026ULL,
    3676073110469038ULL, 3651483716701107ULL, 3627381250550058ULL, 3603749850782235ULL,
    3580574370197164ULL, 3557840334824100ULL, 3535533905932737ULL, 3513641844631532ULL,
    3492151478847891ULL, 3471050672503116ULL, 3450327796711771ULL, 3429971702850176ULL,
    3409971697352367ULL, 3390317518104051ULL, 3370999312316210ULL, 3352007615769954ULL,
    3333333333333333ULL, 3314967720658979ULL, 3296902366978935ULL, 3279129178919764ULL,
    3261640365267210ULL, 3244428422615250ULL, 3227486121839514ULL, 3210806495339677ULL,
    3194382824999699ULL, 3178208630818641ULL
};

// recip_sqrt_k1s[i] = k0[i] - k0[i+1] (slope for linear interpolation)
static constexpr std::uint64_t recip_sqrt_k1s[90] = {
    465374107544077ULL, 405916600703155ULL, 358129098682476ULL, 319037645785127ULL,
    286576738007905ULL, 259271658856312ULL, 236044261947244ULL, 216089963474406ULL,
    198797423899182ULL, 183694689234641ULL, 170412218441933ULL, 158656968791122ULL,
    148193890674550ULL, 138832490278842ULL, 130416923342270ULL, 122818590876336ULL,
    115930534958577ULL, 109663147829877ULL, 103940851524934ULL, 98699503250777ULL,
    93884349425609ULL, 89448398721174ULL, 85351118117671ULL, 81557380165399ULL,
    78036607217917ULL, 74762071301189ULL, 71710317846935ULL, 68860688674593ULL,
    66194925007437ULL, 63696835418333ULL, 61352016752052ULL, 59147618505283ULL,
    57072143038544ULL, 55115275476160ULL, 53267738317645ULL, 51521166708748ULL,
    49868001057143ULL, 48301394268041ULL, 46815131350128ULL, 45403559526677ULL,
    44061527299103ULL, 42784331165330ULL, 41567668904453ULL, 40407598511341ULL,
    39300502007144ULL, 38243053469626ULL, 37232190725627ULL, 36265090229957ULL,
    35339144723907ULL, 34451943324461ULL, 33601253744050ULL, 32785006382086ULL,
    32001280064516ULL, 31248289237504ULL, 30524372446794ULL, 29827981956066ULL,
    29157674376336ULL, 28512102194426ULL, 27890006102448ULL, 27290208042132ULL,
    26711604888265ULL, 26153162704358ULL, 25613911511623ULL, 25092940518988ULL,
    24589393767931ULL, 24102466151049ULL, 23631399767823ULL, 23175480585071ULL,
    22734035373064ULL, 22306428891363ULL, 21892061301205ULL, 21490365783641ULL,
    21100806344775ULL, 20722875791345ULL, 20356093861595ULL, 20000005497809ULL,
    19654179248316ULL, 19318205787841ULL, 18991696546256ULL, 18674282436621ULL,
    18365612674354ULL, 18065353680044ULL, 17773188059171ULL, 17488813652554ULL,
    17211942651960ULL, 16942300775736ULL, 16679626499837ULL, 16423670339978ULL,
    16174194181058ULL, 16174194181058ULL
};

constexpr int table_size = 90;
constexpr int table_scale = 16;  // values scaled by 10^16

} // namespace sqrt_lookup
} // namespace detail
} // namespace decimal
} // namespace boost

#endif // BOOST_DECIMAL_DETAIL_CMATH_IMPL_SQRT_LOOKUP_HPP