Java programme to compute the nested radical constant

Question

[Image from MathWorld, WolframAlpha

Using the code below I was able to estimate it upto: 1.7579327566180045

public class Sum {
static int count = 0;
static double a = 0;
public static void main(String[] args) {
    int x = 0;
    System.out.println(sum(x));
}

public static double sum(int x){
    count++;
    x++;
    if (count == 11000){
        return a;
    }
    return a = Math.sqrt(x+sum(x));
}

I am however not able to get an answer with more accuracy with the recursion here. Increasing the number of recursive calls from 11,000 gives me a StackOverflowError. I also looked up how I could use the java's BigDecimal here, but I'm unable to implement it here and honestly not sure if that would help.

Question :- how can I make this programme compute the constant to more decimal places and more accurately? I'm not certain if this I can compute it iteratively or not either. I wasn't able to work out an iterative definition.

In addition, I looked into Java 8 Streams too, but those didn't make much sense to me (since i'm new to programming and Java) and not sure if that is applicable here.

Thanks for any help!

Need mathematical precision? Don't use floating point numbers. Start with something like [BigDecimal](https://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html). — Mike 'Pomax' Kamermans, May 07 '16 at 04:27

Mike 'Pomax' Kamermans · Accepted Answer · 2016-05-07T05:08:07.590

If your only problem is the stack: don't use recursion, just use a plain iteration.

If we call the iteration limit n, then the radical constant is:

sqrt(1 + sqrt(2 + sqrt(3 + sqrt(4 + ... sqrt(... + sqrt(n))...))))

which is the same as:

sqrt(...(sqrt(sqrt(sqrt(n) + (n-1)) + (n-2)) + (n-3)) + ... )

So let's just use that:

public class Test {
  public Test(int iterations) {
    int n = iterations;
    double sum = 0;
    while (n > 0) {
      sum = Math.sqrt(sum + n--);
    }
    System.out.printf("Precision using %d iterations: %1.50f\n", iterations, sum);
  }

  public static void main(String[] args) {
    new Test(1);
    new Test(10);
    new Test(100);
    new Test(1000);
    new Test(10000);
    new Test(100000);
    new Test(1000000);
    new Test(10000000);
    new Test(100000000);
  }
}

Of course, since you want precision, this isn't going to help much: now you're no longer running into a stack issue, you're running into the fact that IEEE floating point numbers are not for mathematically precise computation:

Precision using 1 iterations: 1.00000000000000000000000000000000000000000000000000
Precision using 10 iterations: 1.75793261139383100000000000000000000000000000000000
Precision using 100 iterations: 1.75793275661800450000000000000000000000000000000000
Precision using 1000 iterations: 1.75793275661800450000000000000000000000000000000000
Precision using 10000 iterations: 1.75793275661800450000000000000000000000000000000000
Precision using 100000 iterations: 1.75793275661800450000000000000000000000000000000000
Precision using 1000000 iterations: 1.75793275661800450000000000000000000000000000000000
Precision using 10000000 iterations: 1.75793275661800450000000000000000000000000000000000
Precision using 100000000 iterations: 1.75793275661800450000000000000000000000000000000000

As per the official documentation:

This data type should never be used for precise values, such as currency. For that, you will need to use the java.math.BigDecimal class instead. Numbers and Strings covers BigDecimal and other useful classes provided by the Java platform.

This might help: http://stackoverflow.com/questions/13649703/square-root-of-bigdecimal-in-java .... no change after 100 iterations: 1.75793275661800453270881963821813852765319992214684 — Tibrogargan, May 07 '16 at 05:15
Yep, there are a *lots* of suggested ways to implement square root for BigDecimal, I'll leave it up to @GeniusAsis to pick his favourite, based on his exact requirements. — Mike 'Pomax' Kamermans, May 07 '16 at 05:24
@Mike'Pomax'Kamermans thanks for the answer, that is exactly what I was looking for. And now I see how I can use BigDecimal instead of the floating point type. cheers :) — IRSAgent, May 07 '16 at 05:52
Applied @Tibrogargan links to your answer in [my answer](http://stackoverflow.com/a/37085066/5221149). *For information only.* This answer is the right answer, and got my upvote. — Andreas, May 07 '16 at 06:00

score 2 · Answer 2 · edited May 23 '17 at 10:28

Taking the code in answer by Mike 'Pomax' Kamermans, converting it to use BigDecimal using the algorithm in answer by barwnikk from the link provided in comment by Tibrogargan, you get this code:

private static void nestedRadicalConstant(int iterations, int scale) {
    BigDecimal sum = BigDecimal.ZERO;
    for (int n = iterations; n > 0; n--)
        sum = sqrt(sum.add(BigDecimal.valueOf(n)), scale);
    System.out.printf("Precision using %9d iterations: %s\n", iterations, sum);
}
private static final BigDecimal TWO = BigDecimal.valueOf(2);
private static BigDecimal sqrt(BigDecimal a, int scale) {
    BigDecimal x0 = BigDecimal.ZERO;
    BigDecimal x1 = new BigDecimal(Math.sqrt(a.doubleValue()));
    while (! x0.equals(x1)) {
        x0 = x1;
        x1 = a.divide(x0, scale, BigDecimal.ROUND_HALF_UP);
        x1 = x1.add(x0);
        x1 = x1.divide(TWO, scale, BigDecimal.ROUND_HALF_UP);
    }
    return x1;
}

At 1000 iterations, you seem to get 1596 digits of precision. Testing with:

nestedRadicalConstant(1, 2);
nestedRadicalConstant(10, 20);
nestedRadicalConstant(100, 120);
nestedRadicalConstant(1000, 1620);
nestedRadicalConstant(10000, 2000);

Produces this output:

Precision using         1 iterations: 1.00
Precision using        10 iterations: 1.75793261139383098942
Precision using       100 iterations: 1.757932756618004532708819638218138527653199922146837704310135500385110232674446757572344554000259452970932471847765477212
Precision using      1000 iterations: 1.757932756618004532708819638218138527653199922146837704310135500385110232674446757572344554000259452970932471847826956725286405867741108546115435116745974827649802384369489120411842037876481995830644570345768467313417541513449577173273720962022100603227554116598015407552297612944579699112707719478877860007819516309923396999343623052775352496605485188121304121230743966852549640366715265942215947576652412589521440394432605735991324822082490634153150397875302128772604959532494672112007991822456833844067286433074237282346571947808094291349553420592279925860366170372859630816687183328634908728532926587173888717587225690606966741535388517308782986073313679762614334220034550147482219697344628499290204994260780123338419145972718423791086759045639529537528043251120937807502935923611917615270426436487465911939829459953781691083134966345861642367678466818801916873226676954205133566864879409563789163447674389255347895570972640620596122532631802815634393718529817582444581463125494708586493852134993196476027405424112251632598737556657076790516333930301963846032409179377260137724948433124123721498603941391880712274921521093576064227183964712879727605419662075877641516168770731031830438884407663198533406472178289280964677785213403598029666777396176022091845158367038947205930644559617550964376557881938238936999861972092712003303733154006164548042213795996830518359866201345560149007762659936776433223239718347842294405131084630617937696469599012405313392949671129259837927464454348595975072906890699729096515457528663221822249478993545431942135457377664898687489112921130467353566525378019109731173223933551193081888
Precision using     10000 iterations: 1.75793275661800453270881963821813852765319992214683770431013550038511023267444675757234455400025945297093247184782695672528640586774110854611543511674597482764980238436948912041184203787648199583064457034576846731341754151344957717327372096202210060322755411659801540755229761294457969911270771947887786000781951630992339699934362305277535249660548518812130412123074396685254964036671526594221594757665241258952144039443260573599132482208249063415315039787530212877260495953249467211200799182245683384406728643307423728234657194780809429134955342059227992586036617037285963081668718332863490872853292658717388871758722569060696674153538851730878298607331367976261433422003455014748221969734462849929020499426078012333841914597271842379108675904563952953752804325112093780750293592361191761527042643648746591193982945995378169108313496634586164236767846681880191687322667695420513356686487940956378916344767438925534789557097264062059612253263180281563439371852981758244458146312549470858649385213499319647602740542411225163259873755665707679051633393030196384603240917937726013772494843312412372149860394139188071227492152109357606422718396471287972760541966207587764151616877073103183043888440766319853340647217828928096467778521340359802966677739617602209184515836703894720593064455961755096437655788193823893699986197209271200330373315400616454804221379599683051835986620134556014900776265993677643322323971834784229440513108463061793769646959901240531339294967112925983792746445434859597507290689069972909651545752866322182224947899354543194213545737766489868748911292113046735356652537801910986407230565075451949088994252961807114520240492889839699378820767287005364075922299290226616859542304563610837999855263494755487315890823802348384905110801341645915817905877028789375061746193512837109024779585044655168397357131113466177623319647140519047121827755000973602827506971619064114104567151734665774836770974378326977363987102385865012823517670987447776358377974581150446359028968379541355377763

More than 4600 digit seems to fail printing, so I stopped there. Began getting slow too. ;-)

that is awesome! thanks so much. I'm also wondering if you could execute this calculation to more accuracy and (possibly faster) in some other language apart from java? Say in C for example? — IRSAgent, May 07 '16 at 06:09
Yeah, C will probably run faster. Does the C library have a BigDecimal like implementation? Otherwise you'd have to do even that yourself. Unless you can find a good math library out there. ;-) — Andreas, May 07 '16 at 06:13

kpie · Answer 3 · 2016-05-07T05:25:48.480

0

You will get allot more accuracy if you implement your algorithm correctly.

edit: Your implementation is not incorrect but it is not how I would do it... (Line 5 of sum could return the sqrt of x instead of a, which might as well just be 0.)

Secondly the key to doing this all iteratively is going backwards.

k = 11000
ans = 0
while k > 0:
    ans+=k
    ans**=0.5
    k-=1
return(ans)

edited May 07 '16 at 05:25

answered May 07 '16 at 04:53

kpie

9,588
5
28
50

no, as a limited iteration, that's perfectly correct. – Mike 'Pomax' Kamermans May 07 '16 at 04:56
really because if you set 1100 equal to 2 the function will return sqrt(3) when it should be sqrt(1+sqrt(2)) – kpie May 07 '16 at 04:57
the use of a static `count` and `a` are certainly messy, but for a limit at `2` the first run will be `count=1, x=1, a=sqrt(1+sum(1))` which relies on computing `sum(1)` for which `count=2,x=2` and the return is 0, so the final value is `a = sqrt(1 + sqrt(0)) = sqrt(1)`. Wrong, but not in the way you thought: it's simply off by one step. For `3` we get `sqrt(1+sqrt(2 + sqrt(0))) = sqrt(1 + sqrt(2))`, and so forth, so OP's code actually computes the same sequence, just subtly off by one iterative step (since the `sqrt(0)` does not change the sum in any way) – Mike 'Pomax' Kamermans May 07 '16 at 05:05
gag... seriously good call though, i wasn't seeing that all that way through. – kpie May 07 '16 at 05:23

Java programme to compute the nested radical constant

3 Answers3