[Week Eighteen] Programming Contest - Square Roots

General Discussion Off Topic
1

Welcome back to the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here

This week’s challenge is to write a method that takes in two integers, and returns the square root of the first number with the precision of the second, as a String. The second parameter specifies the number of digits AFTER the decimal point to calculate the square root. Your method also should not round at all.

Examples:

root(1, 0) -> 1. or 1
root(2, 10) -> 1.4142135623
root(3, 3) -> 1.732
root(5, 10) -> 2.2360679774
root(10, 0) -> 3. or 3
root(10, 10) -> 3.1622776601
root(50, 10) -> 7.0710678118
root(50, 50) -> 7.07106781186547524400844362104849039284835937688474
root(100, 10) -> 10.000000000

Also, if you like these weekly programming problems, please make some suggestions for the contest or specific challenges (in the main thread)! This takes time out of my Sunday and its not always fun! Using suggested challenges makes it a lot faster and easier for me.

Imports are allowed for this challenge!

Challenge Closes: Sunday 3/6/16

Good luck!

2

Quick question, if its a whole number, is it necessary to carry out all the zeroes?

3

The second parameter is the amount of digits you need after the decimal point, the only time you don’t need to carry the zeros is if that number is 0, in which case your only finding the integer value of the square root.

4

This seems to be a bit too trivial

83 characters

public static String r(int v,int n){return String.format("%."+n+"f",Math.sqrt(v));}

public static String root(int v, int n) {
    return String.format("%." + n + "f", Math.sqrt(v));
}
5 
    public static void main(String[] args) {
        System.out.println(root(50, 50));
    }

    public static String root(int v, int n) {
        return String.format("%." + n + "f", Math.sqrt(v));
    }

produces:

7.07106781186547550000000000000000000000000000000000

double isn’t precise enough… (Although I assume there’s some BigDecimal method you could use)

6

Well BigDecimal does not support taking square roots.

7

But there are square root algorithms. You could potentially implement one for a BigDecimal, and terminate it at x digits.

8

My Answer:
192 Characters:

public static String s(int n,int p){BigDecimal l=new BigDecimal(2),t,a=new BigDecimal(n).setScale(p),b=a.divide(l);n=-9;do{t=b;b=(t.add(a.divide(t,3)).divide(l,3));n++;}while(n<p);return""+b;}

Expanded/Prototype Version:

    public static String squareRoot(int number, int precision) {
        int counter = -9; //Precision stuffs

        BigDecimal t;
        BigDecimal num1 = new BigDecimal(number).setScale(precision);
        BigDecimal num2 = num1.divide(new BigDecimal(2));

        do {
            t = num2;
            num2 = (t.add(num1.divide(t, BigDecimal.ROUND_FLOOR))).divide(new BigDecimal(2), BigDecimal.ROUND_FLOOR);
            counter++;
        } while (!(t.subtract(num2)).equals(BigDecimal.ZERO) && counter < precision);

        return num2.toString();
    }

It’s based on the babylonian method (I think)

9

@meguy26
That fails for root(81, 1) -> 9 returning 21.2 instead. When the precision is small enough you are not doing enough iterations to get an accurate answer. If you initialize n to -9 this fixes this issue.

10

Well thanks for telling me rather than “stealing” the code… I was more proving that the precision stuff was possible, but I’ll fix it.

11

This is along the same lines. It’s slightly longer, but doesn’t error on values less than 1.
Seems to be accurate enough.

Minified (207 chars)

public static String r(int i,int p){BigDecimal v=new BigDecimal(i).setScale(p),l=v,t=BigDecimal.ONE,d=t.add(t);while(i>0&&!l.equals(l=t=v.divide(t,1).add(t).divide(d,1)));return i<0?"NaN":l.toPlainString();}

178 chars if we can assume the input is greater than 0 like the post above

public static String r(int i,int p){BigDecimal v=new BigDecimal(i).setScale(p),l=v,t=BigDecimal.ONE,d=t.add(t);while(!l.equals(l=t=v.divide(t,1).add(t).divide(d,1)));return""+l;}

Readable

public static String sqrt(int in, int places)
{
    BigDecimal val = new BigDecimal(in).setScale(places);
    BigDecimal last = val;
    BigDecimal test = BigDecimal.ONE;
    BigDecimal two = test.add(test);

    while (in > 0 && !last.equals(last = test))
    {
        test = test.add(val.divide(test, RoundingMode.FLOOR)).divide(two, RoundingMode.FLOOR);
    }
    return in < 0 ? "NaN" : last.toPlainString();
}