Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!


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


Clarify that comparison operators are allowed.


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.


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

share|improve this question
Nope, -- is not allowed, sorry for the confusion! I originally planned to have ++ and -- but I decided to take -- out at the last minute. – iggyvolz Jun 6 '14 at 2:15
"without using any mathematical operators to change the number" - I think this might need clarification. Do you mean that these operators may not be used at all, or, that they may be used, but only if the result isn't saved to a variable, e.g. while r*r<n*10e20:r+=1 - fairly trivial. Also, you might consider reducing the required output to 10^8 or so. First, because 10^10 is larger than 2^31, and second, because it will take a while to increment that high. – primo Jun 6 '14 at 2:56
Why would you ever want to "change" any variable at all? You imperative guys have strange ways of thinking... – ceased to turn counterclockwis Jun 6 '14 at 10:20
I am flagging to close this question. To much radical changes to the question. You should actually get this question validated through Sandbox or else you would frustrate people investing effort to answer. – Abhijit Jun 6 '14 at 20:21
Reducing the number of required digits is meaningless without time/memory limits. My code can handle 5 digits, but my machine doesn't have enough RAM. – Dennis Jun 7 '14 at 2:11

Python 66

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


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

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

share|improve this answer
I think that will need to be wrapped in int(...*1e10), otherwise very nice. Although, taking abs of a complex value is more or less sqrt in disguise. – primo Jun 6 '14 at 9:16
@primo I don't think you're allowed the *1e10 ... – Cruncher Jun 6 '14 at 14:54
@primo: Instead of multiplying by 1e10, I took a bit different route. And though I agree that abs may be sqrt in disguise, yet I feel its completely legal as currently stated in the problem. – Abhijit Jun 6 '14 at 15:13
I see a downvote, and its quite depressing. I had high hope for this answer, so any one who downvoted, please leave back a comment. – Abhijit Jun 6 '14 at 19:49
@iggyvolz: I am really surprised that you keep on expanding your question and adding more restrictions. People invest time and effort to write an answer and you can;t expect them to be psycic. – Abhijit Jun 6 '14 at 20:19

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
while 1:
 for _ in range(q):
  for _ in range(q):z+=1
 if z>=t:break


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:
    q += 1
share|improve this answer
I clarified the question, you can do it to as many digits as you want (at least 5). I'm not familiar with python, but I'm assuming that int() is just a type caster? If so, that is fine because it doesn't change the value of the number. – iggyvolz Jun 6 '14 at 20:13
@iggyvolz: Right, you need that to convert the string argument value (specified on the command line) to an integer. A plain function wouldn't need that. – Greg Hewgill Jun 7 '14 at 4:13

C - 161 143 137

Note: this is value*1e8, so it would be 138 bytes for value * 1e21. 10^20 wasn't tested as eight digits (four digits of precision in the result) was already taking a while to run.

edit: Reusing square result from previous loop for 100x speedup and 14 fewer bytes!

edit: 100000000 to 1e8 for six bytes!

Accepts a single command line argument and outputs the calculated square root for input value * 100,000,000



// uncomment to fix implicit declaration of printf
//#include <stdio.h>

i=0, j,    /* i,j are loop counters */
t,         /* t is target (input * 10^8) */
s;         /* s is the square and input value */

int main(a,b)char**b;
    // swap the implicit variable declarations with this line to fix warnings
    //int i=0,j,t,s;

    // read first command line argument and parse as int

    // These two loops effectively multiple the target by 10^8.
    // The order of the conditions inside the first while() matters.
    // I wanted to declare i=1e8 and say while(j=0,i--) but oh well
    // Note:
    // Save three bytes at the cost of two orders of magnitude slowdown by replacing
    //     while(j++<s)
    // with
    //     while(j++<atoi(b[1]))
    // and commenting out the above line s=atoi(b[1]);
    while(j=0, i++<1e8)

    // This starts the counter (i) at 0 and squares each value. The
    // difference between successive squares (s) is the length of the side times
    // two, plus one. For example 3*3=9; the length of each side is 3; the
    // distance to the next square 16 is 3+3+1. The difference from 16 to
    // the next square 25 is 4+4+1, etc. The loop finishes when a calculated
    // square (s) is larger than the target (t).
    for(s=i=0; s<t; j=0, i++, s++)
            s++, s++;

    printf("%d", i);

    // need a return value
    //return 0;

Sample run at 10^8, which is approximately four digits of precision on the calculated value:

$ time ./a.out 2
real    0m0.871s
user    0m0.868s
sys     0m0.000s
share|improve this answer
You can golf this down to 135 fairly easily by reusing some variables and replacing while with for loops. – ecatmur Jun 6 '14 at 15:28
Good point on reusing variables, I dropped n and reused s. I'm not really seeing how to improve by changing to for loops though. – tolos Jun 6 '14 at 16:07
So? while(j=0,i++<1e8)while(j++<s)t++; --> while(i++<1e8)for(j=0;j++<s;t++); – edc65 Jun 6 '14 at 19:19

CJam, 26 bytes


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.


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


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. ";
share|improve this answer

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.

share|improve this answer
Wow, guess I didn't think about using operators for changing static values. That's perfectly fine and +1 (if I had 15 reputation to upvote) – iggyvolz Jun 6 '14 at 2:17
This uses the * operator, which is pretty clearly not permitted. Or am I somehow misunderstanding the given restrictions? – Greg Hewgill Jun 6 '14 at 2:20
@GregHewgill: OP states, without using any mathematical operators to change the number; these operators are not changing any values. – Kyle Kanos Jun 6 '14 at 2:21
But that's still using the * operator to change a number, you're just not saving the result anywhere. If the OP wanted to simply disallow assignments (other than s=s+1), then why mention all the disallowed arithmetic operators? – Greg Hewgill Jun 6 '14 at 2:30
@iggyvolz: Changing the rules ~20 hours later is bad form. Please do not do that and use the sandbox to work out the kinks in your problem instead. – Kyle Kanos Jun 6 '14 at 20:33

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)
    while r/e*r/e<n,r+=1
    print r
share|improve this answer
But you used r/e*r/e, which is clearly a non-++ math operator... – nneonneo Jun 8 '14 at 2:19
@nneonneo this was posted before the third edit, and I haven't changed it yet – Ourous Jun 8 '14 at 3:28

Scala, 117

val z=BigInt(readLine+"0000000000")

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.

share|improve this answer

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).

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.