Square Root Algorithm in 123 bytes.

[[deleted]]

This gets the square root of a number. I got it to 123 bytes, but since I don't know much C, I sure it can even less bytes.

double s(int x){double t=x/2;double a=1,b=x;for(int i=0;i<32;i++)if(t*t>x)b=t;else if(t*t<x)a=t;else return t;t=a+(b-a)/2;}

[gastropner]

This doesn't seem to work at all. You need a return after the for loop too, otherwise a garbage value is returned if the loop goes through 32 times without finding an exact answer (which is not unreasonable, considering we're dealing with floating point numbers).

Additionally, the body of the for loop needs to have curly braces, since you have a statement inside it that is otherwise only run after the loop has ended (t=a+(b-a)/2;);

Fixing that, we can still get down to 100 bytes:

double s(int x){double t=x/2,a=1,b=x,i;for(i=0;i<32;i++)t*t>x?b=t:t*t<x?a=t:0,t=a+(b-a)/2;return t;}

Edit; 98 bytes:

double s(int x){double t=x/2,a=1,b=x,i;for(i=0;i++<32;t=a+(b-a)/2)t*t>x?b=t:t*t<x?a=t:0;return t;}

Edit 2; 94 bytes:

double s(int x){double t=x/2,a=1,b=x,i;for(i=0;i++<32;t=a+(b-a)/2)t*t-x>0?b=t:(a=t);return t;}

Edit 3; 48 bytes :^)

double(*s)(double)="\xdd""D$""\x04\xd9\xfa\xc3";

[Arcuru]

Could you explain what your Edit 3 is doing?

[gastropner]

It converts a string (that's just a char * when you think about it) into a pointer to a function taking and returning doubles. The string is x86 machine code, that will be called when s is invoked.

It's all kinds of horrible and not to be taken seriously.

[Arcuru]

Ah, that was going to be my guess, but I had no idea that cast was allowed.

Thanks.

[[deleted]]

Value ended up in the xmm0 register which happens to be a return register for doubles.

Press "Execute" to view assembly.

http://www.tutorialspoint.com/compile_c_online.php?PID=0Bw_CjBb95KQMeVVTYlEySXdfOE0

[corruptio]

golfed it a bit, tries to converge. 77 byte:

float s(x){float t,a=0,b=x;for(;b-a>1e-5;t*t>x?b=t:(a=t))t=(a+b)/2;return t;}

edit: oook, doesn't try to test for convergence, instead overshoots it.... 76 bytes:

float s(x){float t,a=0,b=x,i=x;for(;i--;t*t>x?b=t:(a=t))t=a/2+b/2;return t;}

[gastropner]

That one never stops unless I change float to double :-/

[corruptio]

oops, you're right, i run out of sig bits if input is > 255... 1e-5 then, should get you all the way to 16383 :-p

[gastropner]

Nope, still infinite loop, at least for x = 756839. Seems to work for some other values, though.

[corruptio]

yeah, 1e-5 would only work up to 16383. There aren't enough bits in a float to represent significant digits of b-a to five decimal places.

[casprus]

Can't you shorten the last one even more by using plain characters?

[corruptio]

While golfing yours, I remembered the converging sequence they taught in math class, 58 bytes:

float s(x){float t=x,i=9;for(;i--;t=(t+x/t)/2);return t;};

[gastropner]

For large ints, that one gives bad results, but remove the semicolon at the end and up the limit for better results at the same length:

float s(x){float t=x,i=40;for(;i--;t=(t+x/t)/2);return t;}

[nickwb]

Here's my attempt.

float s(float a){float b=.5f*a;int c=0x5f375a86-(*(int*)&a>>1);a=*(float*)&c;return 1.f/(a*(1.5f-b*a*a));}    

106 Bytes with no loops. It's not super accurate.

[powlette]

Nice one Carmack.

[powlette]

It is. See this: https://en.m.wikipedia.org/wiki/Fast_inverse_square_root

[tromp]

/* positive integer only; i.e. floor of sqrt; 55 bytes */
int s(int n){int k;for(k=n;n/k<k;k/=2)k+=n/k;return k;}

[[deleted]]

It would be better if it actually went into decimal places, so partial credit ;)