Calculate the square root only using ++

Question

Your task is to calculate the square root of a positive integer without using any mathematical operators to change the number, such as:

• Setting a variable (ex. squareRoot = 5)
• Addition (A+B)
• Subtraction (A-B)
• Multiplication (A*B)
• Division (A/B)
• Square, cube, fourth, etc. roots
• Exponents

Comparison operators (such as <, >, ==, etc) are not considered "mathematical operators" for the purposes of this question and are allowed as long as they do not change the value of a variable.

The only operator that you are able to use is ++. The following exceptions are in place:

• If you wish, you may initialize a variable by setting it to 0.
• If your language does not include the ++ syntax, you may use an equivalent syntax, such as foo+=1 or foo=foo+1
• The square root should be calculated to at least 6 digits beyond the decimal (the hundred-thousands place) and outputted as a whole number of the decimals (ex. if I input 2 it could come out as 14142135624 or 1414213 depending on the rounding). Rounding up or down is not important.

User-defined functions are not allowed. In addition, simulating functions with goto is not allowed as well.

I'm interested to see what everyone submits! Happy coding!

CLARIFICATION

Clarify that number is a positive integer. You are welcome to make code that would do any number but it is not necessary.

CLARIFICATION #2

Clarify that comparison operators are allowed.

CLARIFICATION #3

Addition, subtraction, multiplication, division, and functions to change numbers are not allowed at all, regardless of whether they are saved to a variable or not. I'm sorry that this invalidates a couple existing answers, but I meant to define this group of operators with "change the number" in order to prevent troll answers (ex. I just used the sqrt() function, you only prohibited addition, multiplication, division, and subtraction). Sorry for the confusion.

CLARIFICATION #4

Clarify that we need at least 5 digits. 10 digits caused code to run for a long time.

Answer 1

Python 66

print'%.0f'%reduce(lambda a,b:abs(a)+1e10j,range(-2,input())).real

Output

>>> print'%.0f'%reduce(lambda a,b:abs(a)+1e10j,range(-2,input())).real
121
110000000000
>>> print'%.0f'%reduce(lambda a,b:abs(a)+1e10j,range(-2,input())).real
1000
316227766017

This solution uses Spiral of Theodorus on a complex plane to achieve the result.

Answer 2

Python, 184 characters

The following Python solution uses only the increment operator and no other arithmetic operators at all. However, with the required precision (10 digits), it takes an impossibly long time to run. You can test it with lower precision (3 digits) by reducing 1e20 to 1e6.

import sys;t=0
for _ in range(int(sys.argv[1])):
 for _ in range(int(1e20)):t+=1
q=0
while 1:
 z=0
 for _ in range(q):
  for _ in range(q):z+=1
 if z>=t:break
 q+=1
print(q)

Ungolfed:

import sys

# t = N * 100000000000000000000 (magnitude of twice the precision)
t = 0
for _ in range(int(sys.argv[1])):
    for _ in range(int(1e20)):
        t += 1
q = 0
while True:
    # z = q * q
    z = 0
    for _ in range(q):
        for _ in range(q):
            z += 1
    if z >= t:
        break
    q += 1
print(q)

Answer 3

Fortran 73

read*,t;s=0;do while(abs(s*s/1e10-t)>1e-10);s=s+1;enddo;print*,s/1e5;end

Might take a loooong to actually determine an answer for certain values, but it'll work for sure. While I use * and -, these are not changing any values, only the s=s+1 actually changes anything.

Answer 4

CJam, 26 bytes

q~,1e20,m*,:N!{)_,_m*,N<}g

Try it online. Paste the Code, type the desired integer in Input and click Run. Before you do, I suggest changing 1e10 to 1e4 though.

The Java interpreter handles 1e6 with input “2” in about 15 seconds. 1e20 will require a huge amount of RAM.

Examples

$ cjam <(echo 'q~,1e2,m*,:N!{)_,_m*,N<}g') <<< 4; echo
20
$ cjam <(echo 'q~,1e2,m*,:N!{)_,_m*,N<}g') <<< 2; echo
15
$ cjam <(echo 'q~,1e4,m*,:N!{)_,_m*,N<}g') <<< 4; echo
200
$ cjam <(echo 'q~,1e4,m*,:N!{)_,_m*,N<}g') <<< 2; echo
142
$ cjam <(echo 'q~,1e6,m*,:N!{)_,_m*,N<}g') <<< 4; echo
2000
$ cjam <(echo 'q~,1e6,m*,:N!{)_,_m*,N<}g') <<< 2; echo
1415

Background

Since we're not allowed mathematical operators to change numbers, we're going to use setwise operators to change arrays.

The code starts by "multiplying" the input (“i”) by 1e20, but without any actual multiplication. Instead, we push an array containing “i” integers, an array containing 1e20 integers, take their cartesian product and compute its length.

Then, we push zero and increment until the product of the integer by itself (calculated as above) is no longer smaller than i * 1e20. This causes the square root to be rounded up.

How it works

q~     " Read for STDIN and interpret. ";
,      " Push an array containing that many integers. ";
1e20,  " Push the array [ 0   …   1e20 - 1]. ";
m*,:N  " Get the length of the cartesian product and save it in “N”. ";
!      " Logical NOT. Since the input is a positive integer, this pushes 0. " ;
{      " ";
  )    " Increment the integer on the stack.";
  _,   " Push an array containing that many integers. ";
  _m*, " Get the length of the cartesian product of the array by itself. ";
  N<   " If the product is smaller than the target value, push 1; otherwise push 0. ";
}g     " Repeat the loop if the result was 1. ";

Answer 5

Cobra - 62

Posted before the third edit, no longer valid.

Not only is it short, but it should be overflow-free if n < Decimal.maxValue

def f(n)
    r,e=0d,10000000000
    while r/e*r/e<n,r+=1
    print r

Answer 6

Scala, 117

val z=BigInt(readLine+"0000000000")
print(Stream.from(1)find(x=>(BigInt(0)/:Stream.fill(x,x)(1).flatten){_+_}>=z)get)

Doesn't finish in a reasonable amount of time, even for 2 as input, but it does work. You may notice that I'm doing _+_, but that only ever adds 1, and Scala doesn't have a ++ operator anyway. I could save two characters by replacing the inner Stream with List, but then it would run out of memory. As written, I think it scales only in processing time, not memory usage.

Answer 7

PHP, 124 bytes

It's an exhaustive algorithm. It just tries numbers until the square of that number is bigger than the "goal" number (which is the input times 1Enumber of decimals squared (10.000 for a 2 decimal result). Then it prints that last number.

for(;$a++<$z=$argv[1];)for(;$$a++<1e6;)$g++;for(;$b++<$g;$i=$x=0)for(;$i++<$b;)for($j=0;$j++<$b;)if(++$x>=$g)break 3;echo$b;

Run like this (-d added for aesthetic reasons only):

php -d error_reporting=32757 -r 'for(;$a++<$z=$argv[1];)for(;$$a++<1e6;)$g++;for(;$b++<$g;$i=$x=0)for(;$i++<$b;)for($j=0;$j++<$b;)if(++$x>=$g)break 3;echo"$b\n";' 2

Don't recommend trying this out with anything more than 3 decimals or a number above 10.

Answer 8

Haskell, 70 bytes

s i|r<-[1..i]=foldl1(.)[(+1)|j<-r,k<-r]
f i=[j-1|j<-[0..],s j 0>=i]!!1

f gives the integer square root by finding the largest number whose square is less than or equal to the input. The squaring function s i increments by one for every element of an (i,i) matrix. (Typed on phone so might have typos).