julia - BigFloats的rationalize()有上限吗？

Question

我有以下代码:

function recursion(i::BigFloat)
    r = BigFloat(0)
    if i >= 1.0
        i = i - 1.0
        r = 1.0/(2.0+recursion(i))
    end
    return r
end

function main()
    solution = 0

    i = BigFloat(1)
    while i < 1000
        sum = 1 + recursion(i)
        print("\nsum: ",rationalize(sum))
        if length(digits(numerator(rationalize(sum)))) > length(digits(denominator(rationalize(sum))))
            solution = solution + 1
            print("     <------- found")
        end
        i = i + 1.0
    end
    
    return solution
end

solution = main()

目标是使用以下等式求 sqrt(two) 的展开式:

(图片取自“2的平方根”wikipedia page)

其中有理表示的分子位数大于分母的位数。

我的代码的逻辑似乎有效，但是有一个上限，在使用 BigFloat 类型时，它似乎破坏了rationalize()函数。

sum: 3//2
sum: 7//5
sum: 17//12
sum: 41//29
sum: 99//70
sum: 239//169
sum: 577//408
sum: 1393//985     <------- found
sum: 3363//2378
sum: 8119//5741
sum: 19601//13860
sum: 47321//33461
sum: 114243//80782     <------- found
sum: 275807//195025
sum: 665857//470832
sum: 1607521//1136689
sum: 3880899//2744210
sum: 9369319//6625109
sum: 22619537//15994428
sum: 54608393//38613965
sum: 131836323//93222358     <------- found
sum: 318281039//225058681
sum: 768398401//543339720
sum: 1855077841//1311738121
sum: 4478554083//3166815962
sum: 10812186007//7645370045     <------- found
sum: 26102926097//18457556052
sum: 63018038201//44560482149
sum: 152139002499//107578520350
sum: 367296043199//259717522849
sum: 886731088897//627013566048
sum: 2140758220993//1513744654945
sum: 5168247530883//3654502875938
sum: 12477253282759//8822750406821     <------- found
sum: 30122754096401//21300003689580
sum: 72722761475561//51422757785981
sum: 175568277047523//124145519261542
sum: 423859315570607//299713796309065
sum: 1023286908188737//723573111879672     <------- found
sum: 2470433131948081//1746860020068409
sum: 5964153172084899//4217293152016490
sum: 14398739476117879//10181446324101389
sum: 34761632124320657//24580185800219268
sum: 83922003724759193//59341817924539925
sum: 202605639573839043//143263821649299118
sum: 489133282872437279//345869461223138161
sum: 1180872205318713601//835002744095575440     <------- found
sum: 2850877693509864481//2015874949414289041
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522
sum: 6882627592338442563//4866752642924153522

它“卡在”分数 6882627592338442563//4866752642924153522 处。大概是因为合理化函数中有某种上限。

为什么会卡在这里？我该如何解决这个问题？

Answer 1

这里有一些问题，所有问题都涉及确保您使用的类型可以达到您想要的精度或大小。

首先，您需要改掉在精确数字中添加小数的习惯，例如 1.0 和 2.0 ，它们被解释为文字 Float64 。当您只处理 64 位 float 时，这很好，但您不想使用 Float64 和 BigFloat 进行代数运算。在这种情况下，由于您的 float 是精确的整数，因此只需使用整数 1 和 2 ，Julia 就会正确提升为 BigFloat 。对于不是精确整数的东西，您可以显式给出文字 Rational ，编译器将有效地将它们转换为适当的类型。或者，您可以显式转换为您需要的数字类型，如 sqrt(big(2)) 中那样 - 尽管通常最好检测输入类型，然后执行 sqrt(T(2)) 之类的操作。与 C++ 不同，如果您输入 1/2 ，您将得到 0.5 作为 Float64 。另一方面， 1/(2+recursion(i)) 会首先将 2+recursion(i) 转换为适当的 BigFloat ，然后取 true 的逆。

其次，如果您查看 rationalize 的文档字符串，您会发现它有一个类型的可选参数，默认为 Int 。这意味着结果必须具有这种类型的分子和分母。但 Int64 只能表示 typemax(Int64) 以内的数字，即 9223372036854775807。而你的“卡住”分子大约有 75% 大，所以你可能无法变得更大。不要使用默认值，只需将其称为 rationalize(BigInt, sum) ，您将能够在顶部和底部获得更大的数字。

第三，请注意 rationalize 的第三个参数，它表示一旦结果在 tol 内(默认为输入的机器精度)，它将停止尝试寻找更好的近似值。对于 sqrt(big(2)) ，大约为 1.7e-77。因此，一旦结果在 rationalize 的距离内， sqrt(big(2)) 就不会再给你任何东西。因此，即使使用 Big* ，您的结果最终也会“卡住”。

无论如何，把所有这些放在一起:

function recursion(i::BigFloat)
    r = BigFloat(0)
    if i >= 1
        i = i - 1
        r = 1/(2+recursion(i))
    end
    return r
end

function main()
    solution = 0

    i = BigFloat(1)
    while i < 1000
        sum = 1 + recursion(i)
        ratio = rationalize(BigInt, sum)
        print("\nsum: ",ratio)
        if length(digits(numerator(ratio))) > length(digits(denominator(ratio)))
            solution = solution + 1
            print("     <------- found")
        end
        i = i + 1
    end
    
    return solution
end

solution = main()

结果看起来像这样

sum: 3//2
sum: 7//5
sum: 17//12
sum: 41//29
sum: 99//70
sum: 239//169
sum: 577//408
sum: 1393//985     <------- found
sum: 3363//2378
sum: 8119//5741
sum: 19601//13860
sum: 47321//33461
sum: 114243//80782     <------- found
sum: 275807//195025
sum: 665857//470832
sum: 1607521//1136689
sum: 3880899//2744210
sum: 9369319//6625109
sum: 22619537//15994428
sum: 54608393//38613965
sum: 131836323//93222358     <------- found
sum: 318281039//225058681
sum: 768398401//543339720
sum: 1855077841//1311738121
sum: 4478554083//3166815962
sum: 10812186007//7645370045     <------- found
sum: 26102926097//18457556052
sum: 63018038201//44560482149
sum: 152139002499//107578520350
sum: 367296043199//259717522849
sum: 886731088897//627013566048
sum: 2140758220993//1513744654945
sum: 5168247530883//3654502875938
sum: 12477253282759//8822750406821     <------- found
sum: 30122754096401//21300003689580
sum: 72722761475561//51422757785981
sum: 175568277047523//124145519261542
sum: 423859315570607//299713796309065
sum: 1023286908188737//723573111879672     <------- found
sum: 2470433131948081//1746860020068409
sum: 5964153172084899//4217293152016490
sum: 14398739476117879//10181446324101389
sum: 34761632124320657//24580185800219268
sum: 83922003724759193//59341817924539925
sum: 202605639573839043//143263821649299118
sum: 489133282872437279//345869461223138161
sum: 1180872205318713601//835002744095575440     <------- found
sum: 2850877693509864481//2015874949414289041
sum: 6882627592338442563//4866752642924153522
sum: 16616132878186749607//11749380235262596085
sum: 40114893348711941777//28365513113449345692
sum: 96845919575610633161//68480406462161287469
sum: 233806732499933208099//165326326037771920630
sum: 564459384575477049359//399133058537705128729
sum: 1362725501650887306817//963592443113182178088     <------- found
sum: 3289910387877251662993//2326317944764069484905
sum: 7942546277405390632803//5616228332641321147898
sum: 19175002942688032928599//13558774610046711780701
sum: 46292552162781456490001//32733777552734744709300
sum: 111760107268250945908601//79026329715516201199301     <------- found
sum: 269812766699283348307203//190786436983767147107902
sum: 651385640666817642523007//460599203683050495415105
sum: 1572584048032918633353217//1111984844349868137938112
sum: 3796553736732654909229441//2684568892382786771291329
sum: 9165691521498228451812099//6481122629115441680520770
sum: 22127936779729111812853639//15646814150613670132332869
sum: 53421565080956452077519377//37774750930342781945186508
sum: 128971066941642015967892393//91196316011299234022705885     <------- found
sum: 311363698964240484013304163//220167382952941249990598278
sum: 751698464870122983994500719//531531081917181734003902441
sum: 1814760628704486452002305601//1283229546787304717998403160
sum: 4381219722279095887999111921//3097990175491791170000708761
sum: 10577200073262678228000529443//7479209897770887057999820682     <------- found
sum: 25535619868804452344000170807//18056409971033565286000350125
sum: 61648439810871582916000871057//43592029839838017630000520932
sum: 148832499490547618176001912921//105240469650709600546001391989
sum: 359313438791966819268004696899//254072969141257218722003304910
sum: 867459377074481256712011306719//613386407933224037990008001809
sum: 2094232192940929332692027310337//1480845785007705294702019308528
sum: 5055923762956339922096065927393//3575077977948634627394046618865
sum: 12206079718853609176884159165123//8631001740904974549490112546258     <------- found
sum: 29468083200663558275864384257639//20837081459758583726374271711381
sum: 71142246120180725728612927680401//50305164660422142002238655969020
sum: 171752575441025009733090239618441//121447410780602867730851583649421
sum: 414647397002230745194793406917283//293199986221627877463941823267862
sum: 1001047369445486500122677053453007//707847383223858622658735230185145     <------- found
sum: 2416742135893203745440147513823297//1708894752669345122781412283638152
sum: 5834531641231893991002972081099601//4125636888562548868221559797461449
sum: 14085805418356991727446091676022499//9960168529794442859224531878561050     <------- found
sum: 34006142477945877445895155433144599//24045973948151434586670623554583549
sum: 82098090374248746619236402542311697//58052116426097312032565778987728148
sum: 198202323226443370684367960517767993//140150206800346058651802181530039845
sum: 478502736827135487987972323577847683//338352530026789429336170142047807838
sum: 1155207796880714346660312607673463359//816855266853924917324142465625655521     <------- found
sum: 2788918330588564181308597538924774401//1972063063734639263984455073299118880
sum: 6733044458057842709277507685523012161//4760981394323203445293052612223893281
sum: 16255007246704249599863612909970798723//11494025852381046154570560297746905442
sum: 39243058951466341909004733505464609607//27749033099085295754434173207717704165
sum: 94741125149636933417873079920900017937//66992092050551637663438906713182313772
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 323466434400377142162623973268164663418//228725309250740208744750893347264645481
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709
sum: 228725309250740208744750893347264645481//161733217200188571081311986634082331709

所以它确实会“卡住”，但只要与 sqrt(big(2)) 相比评估最终结果，你应该会很高兴。