hmath/ratio/

ln2.rs

use crate::{BigInt, Ratio};

/// It returns an approximate value of ln(2).
/// It gets more and more accurate as `k` gets bigger.
/// For now, `k` should be less than 200.
pub fn ln2_iter(k: usize) -> Ratio {
    let mut result = Ratio::from_denom_and_numer_i32(11354112, 7869871);
    let mut coeff = BigInt::from_i64(4096);

    for i in 0..k {
        let (denom, numer) = LN2_TABLE[i];
        let curr = Ratio::from_denom_and_numer_raw(BigInt::from_i64(denom), BigInt::from_i64(numer));
        result.add_rat_mut(&curr.div_bi(&coeff));
        coeff.mul_i32_mut(64);
    }

    result
}

const LN2_TABLE: [(i64, i64); 205] = [
    //(1920, 1327),
    //(887040, 112619),
    (17821440, 1270037),
    (258424320, 12822709),
    (228009600, 8681597),
    (467470080, 14442269),
    (2517977280, 65453077),
    (23561303040, 528635839),
    (49588156800, 978669859),
    (1922452224, 33865613),
    (87224417280, 1387494551),
    (299978703360, 4349920153),
    (493155062400, 6570252229),
    (195111141120, 2404166671),
    (29885502240, 342519931),
    (1779932743680, 19067679427),
    (2585373436800, 25998200023),
    (1837012020480, 17405773247),
    (2560249063680, 22933828217),
    (1402654256640, 11913933401),
    (9456301008000, 76366364377),
    (785671011840, 6047164573),
    (4124179039680, 30320476471),
    (21395259325440, 150548612359),
    (5490048278400, 37042125839),
    (17435231573760, 112990864601),
    (21945903920640, 136818015419),
    (54779488135680, 329010447649),
    (67830382638720, 393007137709),
    (4168773100800, 23329797653),
    (1590348510660, 8606513893),
    (123457702072320, 646782534283),
    (148850353491840, 755680519039),
    (89226825273600, 439387982867),
    (4256171023104, 20348278757),
    (252506543132160, 1173021889477),
    (298192697362560, 1347112114753),
    (43821101318400, 192660524663),
    (102599159382720, 439306864921),
    (95700242641920, 399344682563),
    (555774264017280, 2261648205427),
    (321588854496000, 1276987536749),
    (370873625210880, 1437888394847),
    (852596054069760, 3229228112809),
    (195383703795840, 723321647441),
    (278998534214400, 1010075810563),
    (158898930130080, 562851067721),
    (1443972045035520, 5006731333459),
    (1635894770643840, 5554793048359),
    (184861986566400, 614983180027),
    (1041956655586560, 3397402417601),
    (2343651218388480, 7492790980813),
    (2629824315108480, 8246993095849),
    (92016953804160, 283148141237),
    (164501980843200, 496874576063),
    (3668677992483840, 10880835749527),
    (4082953498715520, 11894496681883),
    (2267750189080320, 6491167037057),
    (2514548144908800, 7074173204867),
    (222666696903168, 615866933977),
    (6151293698309760, 16731598180477),
    (1696553516125440, 4539387566557),
    (467176992282000, 1229944218469),
    (8220720369377280, 21300998732059),
    (1805525643841920, 4605621252803),
    (4949742597085440, 12432734126651),
    (5420203947513600, 13409140592549),
    (11854705585282560, 28891902317269),
    (12946886110892160, 31091852129809),
    (353041547738880, 835595419357),
    (3845989027396800, 8973412630813),
    (16738908718371840, 38507378219743),
    (18191882900392320, 41271197726659),
    (9874235672421120, 22095741188117),
    (2141450272281600, 4727478341947),
    (23196048234078720, 50527832475577),
    (25099428243415680, 53957543981413),
    (6782804751640320, 14392754410231),
    (3662282435713440, 7671942609323),
    (6321531650918400, 13075718253767),
    (34066800493165440, 69587839025527),
    (18341677535919360, 37005574705679),
    (19732640862654720, 39328292603657),
    (42420838315968000, 83532409158109),
    (1822343527475328, 3545883456865),
    (3055462975272960, 5875580438647),
    (13104123322530240, 24906972070207),
    (56155370042956800, 105511977303079),
    (60113898450103680, 111670853390059),
    (6430228268808960, 11811403050709),
    (34365539206602240, 62425619864651),
    (73411200741542400, 131892431691073),
    (78353932318623360, 139247779035469),
    (20892732869648640, 36731919715921),
    (556714003081320, 968392219903),
    (94876293909196800, 163303861363627),
    (100989926978183040, 172022082573343),
    (53714192086114560, 90554369120867),
    (57102663895960320, 95287692251117),
    (24266969332569600, 40086763328609),
    (128831464921864320, 210696071556577),
    (17088768861615360, 27671803773611),
    (36246581513123520, 58120354997281),
    (153675874084561920, 244029817358959),
    (32559030005040000, 51206530020407),
    (86180494748363520, 134251599936701),
    (91195359015720960, 140727502314479),
    (192902160484938240, 294901861074889),
    (203913650538998400, 308857827117109),
    (2154440402940672, 3233372243107),
    (28439088743913120, 42294330038669),
    (240139577584220160, 353924931314803),
    (253345108999881600, 370063224526279),
    (133575163844855040, 193392460294967),
    (28157682486984960, 40410569604829),
    (296646769611118080, 422041505789677),
    (312382919058537600, 440608585497673),
    (5137634824069440, 7184741470321),
    (86486965741794240, 119925729055171),
    (72765041063869440, 100052812924811),
    (382465869225686400, 521524282669627),
    (200947854315237120, 271750623379409),
    (211070614375272960, 283106464392467),
    (443229596921879040, 589677598582609),
    (93037730707152000, 122782765275449),
    (122011730766132480, 159735121308613),
    (31989601573556880, 41548547094343),
    (536578685942906880, 691442117296699),
    (562312749128296320, 718956372878959),
    (58906718757868800, 74733962917711),
    (308437057346584320, 388306155099701),
    (645766395987525120, 806795157490933),
    (675777660747047040, 837909232583089),
    (88367789221113600, 108746989930373),
    (7392955471941312, 9030169269229),
    (772873352429122560, 937054291209727),
    (807712532156799360, 972110378274403),
    (421925356218643200, 504103943160677),
    (440663177449098240, 522684924118967),
    (184035753802897920, 216723926808773),
    (960448124477911680, 1122980953340677),
    (250543865914003200, 290869464440287),
    (130675339267593120, 150641842927343),
    (1090172701386639360, 1247976353357059),
    (227305832287712640, 258405555999851),
    (592258376874528000, 668657233798751),
    (617090537042622720, 691931107341209),
    (1285568667525342720, 1431697176512509),
    (1338727041544717440, 1480845867523609),
    (17421308489894400, 19141689547229),
    (362637763088018880, 395798076353863),
    (1509316635105377280, 1636444899099463),
    (1570052917167799680, 1691120920469899),
    (816406208713455360, 873624358295417),
    (169764869756505600, 180485700840031),
    (1764616375772490240, 1863974893159777),
    (1833771140550088320, 1924631846903533),
    (476292441150408960, 496714431722041),
    (15459922803247650, 16020959172203),
    (82197247453483008, 84645504616579),
    (2133413076727820160, 2183253266625727),
    (1107188520108929280, 1126030567157939),
    (1148942741022585600, 1161296509297277),
    (2384001976885562880, 2394881115490309),
    (494558256674401920, 493791603880013),
    (320539919837948160, 318107090692319),
    (664663343335992000, 655652658096937),
    (2755861725809525760, 2702253544146319),
    (2856014057546981760, 2783819673179059),
    (295918126790065920, 286734364246633),
    (1532717764584652800, 1476430244026751),
    (3174850301752496640, 3040405661500393),
    (3287500349386619520, 3130015032330709),
    (850865438617608960, 805431222620371),
    (88070298337005600, 82889298718813),
    (3645629652474501120, 3411593345255827),
    (3771995042688324480, 3509826645865063),
    (1950994808108586240, 1805154923332487),
    (2017848140895202560, 1856540688200417),
    (834639872126860800, 763636019785577),
    (4314584602424691840, 3925645315660777),
    (139373100041535360, 126109899000719),
    (1152337953034676160, 1036958659974091),
    (4762912566489369600, 4262639560070359),
    (196828523566915968, 175198904187667),
    (2541423257268698880, 2249937649856801),
    (2624703751488698880, 2311194811672739),
    (5420492257513536000, 4747558008502129),
    (5596198540461809280, 4875423345253309),
    (288831284509620480, 250301449163657),
    (372617164873633680, 321213670893097),
    (6152047924932403200, 5275636874533723),
    (6347249719036786560, 5414728147189519),
    (3273792916129102080, 2778368882421467),
    (675316373775563520, 570171141193153),
    (6964092587176435200, 5849695247193877),
    (7180483228042227840, 6000735906118993),
    (925306027653047040, 769360062924473),
    (1907525464627258560, 1578044158840621),
    (1572712036050355200, 1294534476491219),
    (8102940993121806720, 6636416311661827),
    (4174181943967875840, 3401728739481269),
    (4299975128790512640, 3486922715894087),
    (8857823315028779520, 7147630211465209),
    (1824421622287286400, 1464972471133217),
    (2348232888584943360, 1876398225214663),
    (1208802803241831840, 961234173094451),
];

#[cfg(test)]
mod tests {
    use super::ln2_iter;

    #[test]
    fn ln2_test() {
        assert_eq!(
            ln2_iter(2).to_approx_string(9),
            "0.6931471"
        );
        assert_eq!(
            ln2_iter(3).to_approx_string(12),
            "0.6931471805"
        );
        assert_eq!(
            ln2_iter(4).to_approx_string(14),
            "0.693147180559"
        );
        assert_eq!(
            ln2_iter(5).to_approx_string(16),
            "0.69314718055994"
        );
        assert_eq!(
            ln2_iter(6).to_approx_string(17),
            "0.693147180559945"
        );

        assert_eq!(
            std::f64::consts::LN_2,
            ln2_iter(6).to_ieee754_f64().unwrap(),
        );
    }

}