13
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nope, -- is not allowed, sorry for the confusion! I originally planned to have ++ and -- but I decided to take -- out at the last minute. \$\endgroup\$ – iggyvolz Jun 6 '14 at 2:15
  • 5
    \$\begingroup\$ "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. \$\endgroup\$ – primo Jun 6 '14 at 2:56
  • 1
    \$\begingroup\$ Why would you ever want to "change" any variable at all? You imperative guys have strange ways of thinking... \$\endgroup\$ – ceased to turn counterclockwis Jun 6 '14 at 10:20
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Abhijit Jun 6 '14 at 20:21
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Dennis Jun 7 '14 at 2:11
13
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – primo Jun 6 '14 at 9:16
  • 1
    \$\begingroup\$ @primo I don't think you're allowed the *1e10 ... \$\endgroup\$ – Cruncher Jun 6 '14 at 14:54
  • \$\begingroup\$ @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. \$\endgroup\$ – Abhijit Jun 6 '14 at 15:13
  • \$\begingroup\$ 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. \$\endgroup\$ – Abhijit Jun 6 '14 at 19:49
  • 9
    \$\begingroup\$ @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. \$\endgroup\$ – Abhijit Jun 6 '14 at 20:19
6
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – iggyvolz Jun 6 '14 at 20:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Greg Hewgill Jun 7 '14 at 4:13
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – iggyvolz Jun 6 '14 at 2:17
  • \$\begingroup\$ This uses the * operator, which is pretty clearly not permitted. Or am I somehow misunderstanding the given restrictions? \$\endgroup\$ – Greg Hewgill Jun 6 '14 at 2:20
  • \$\begingroup\$ @GregHewgill: OP states, without using any mathematical operators to change the number; these operators are not changing any values. \$\endgroup\$ – Kyle Kanos Jun 6 '14 at 2:21
  • 7
    \$\begingroup\$ 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? \$\endgroup\$ – Greg Hewgill Jun 6 '14 at 2:30
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Kyle Kanos Jun 6 '14 at 20:33
2
\$\begingroup\$

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. ";
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ But you used r/e*r/e, which is clearly a non-++ math operator... \$\endgroup\$ – nneonneo Jun 8 '14 at 2:19
  • \$\begingroup\$ @nneonneo this was posted before the third edit, and I haven't changed it yet \$\endgroup\$ – Οurous Jun 8 '14 at 3:28
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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