text:
Integer square root of integer
Problem:
In your choice of language, write the shortest function that returns the floor of the square root of an unsigned 64-bit integer.
Test cases:
Your function must work correctly for all inputs, but here are a few which help illustrate the idea:
               INPUT ⟶ OUTPUT

                   0 ⟶  0
                   1 ⟶  1
                   2 ⟶  1
                   3 ⟶  1
                   4 ⟶  2
                   8 ⟶  2
                   9 ⟶  3
                  15 ⟶  3
                  16 ⟶  4
               65535 ⟶ 255
               65536 ⟶ 256
18446744073709551615 ⟶ 4294967295

Rules:

You can name your function anything you like. (Unnamed, anonymous, or lambda functions are fine, as long as they are somehow callable.)
Character count is what matters most in this challenge, but runtime is also important. I'm sure you could scan upwards iteratively for the answer in O(√n) time with a very small character count, but O(log(n)) time would really be better (that is, assuming an input value of n, not a bit-length of n).
You will probably want to implement the function using purely integer and/or boolean artithmetic. However, if you really want to use floating-point calculations, then that is fine so long as you call no library functions. So, simply saying return (n>0)?(uint32_t)sqrtl(n):-1; in C is off limits even though it would produce the correct result. If you're using floating-point arithmetic, you may use *, /, +, -, and exponentiation (e.g., ** or ^ if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1). This restriction is to prevent "cheating" by calling sqrt() or a variant or raising a value to the ½ power.
If you're using floating-point operations (see #3), you aren't required that the return type be integer; only that that the return value is an integer, e.g., floor(sqrt(n)), and be able to hold any unsigned 32-bit value.
If you're using C/C++, you may assume the existence of unsigned 64-bit and 32-bit integer types, e.g., uint64_t and uint32_t as defined in stdint.h. Otherwise, just make sure your integer type is capable of holding any 64-bit unsigned integer.
If your langauge does not support 64-bit integers (for example, Brainfuck apparently only has 8-bit integer support), then do your best with that and state the limitation in your answer title. That said, if you can figure out how to encode a 64-bit integer and correctly obtain the square root of it using 8-bit primitive arithmetic, then more power to you!
Have fun and get creative!

"but O(log₄(n)) time would really be better." - how much better? Is there a bonus? Is that a hard requirement? Is it essentially a separate challenge? Is that just a nice idea that doesn't really affect the scoring?

@JanDvorak — I guess I meant it in more than the bonus sense. It wasn't until after formulating the original question that I realized it would be trivial to write a simple O(√n) looping version in very few number of characters, which isn't really very interesting. So in some sense, it's a separate challenge, but really I am looking for solutions that are good performance, e.g., O(log₂(n)) or O(log₄(n)).

Normally one uses the size of the input rather than the input value to derive algorithmic complexity. In that sense the increment-and-retry algorithm is exponential in speed.

Umm... O(log_2 n) === O(log_4 n). log_4(n) = log_2(n) / log_2(2) = log_2(n) / 2

@JanDvorak — Ah yes. If 2^k ≤ n < 2^{k+1}, k≥0 ∈ ℤ, then O(log₂(n)) = O(log₂(2^k)) = O(k), and O(√n) = O(√{2^k}) = O(2^{k/2}), which is exponential in k, as you point out. I wrote O(log₂(n)) because I was thinking more in terms of the input value n than in terms of n's scale, so without specifying what I meant by n, I'm sure that was pretty confusing.

Does 2/4 count?

@Milo — Right. Don't raise something to the 2/4 power either. Heh. No fractional exponents was really the intention of my statement.

@ToddLehman ok :)

Most floating-point data types don't have the precision needed for this task anyway. 53 significant bits isn't enough for the whole input range.

@user2357112 — Yeah, definitely. Gotta use something like long double in C to get the whole 64-bit unsigned integer range (which does work, BTW...I've verified). Of course, this requires your compiler to implement long double such that sizeof(long double) >= 10.

CJam, 17 (or 10) bytes
{_1.5#\/i}

Try it online by verifying the test cases:
[0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615]{_1.5#\/i}%N*

It won't pass the last test case because of rounding issues, but since 18446744073709551615 isn't an Integer in CJam (it's a Big Integer), we're still good, right?
If not, the following (and slightly longer) code will correct those errors:
{__1.5#\/i_2#@>-}

Not the shortest solution anymore, but faaast.
How it works
__    " Duplicate the integer twice. ";
1.5#  " Raise to power 1.5. Note that, since 1.5 > 1, this doesn't break the rules. ";
\     " Swap the result with the original integer. ";
/     " Divide. ";
i     " Cast to integer. ";
_2#   " Push square of a copy. ";
@     " Rotate the orginal integer on top of the stack. ";
>-    " If the square root has been rounded up, subtract 1. ";

Hahaha! oops, ok, you got me on a technicality there. I should have said no fractional powers. But your code does indeed obey the stated rules, so I'm upvoting it. :)

Does CJam have arbitrary-precision decimals, to cover the whole input range?

Also, nice hack of using NaN -> 0 on cast to int.

Neat idea, it can also be represented in J in the exact same character count: <.@%~^&1.5. Can I post this as an separate answer (since it's basically an exact port of yours)?

@ɐɔıʇǝɥʇuʎs: Go ahead. But I just figured out that my solution may round incorrectly for big numbers, including the last test case. In my defense, it passed my inspection only because 4294967295 and 4294967296 look very similar...

Haskell, 28 26
I believe that this is the shortest entry from any language that wasn't designed for golfing.
s a=[x-1|x<-[0..],x*x>a]!!0

It names a function s with parameter a and returns one minus the first number whose square is greater than a.  Runs incredibly slowly (O(sqrt n), maybe?).

Wouldn't a list index ([...]!!0) be shorter than head?

@isaacg Yes, it would.  Thanks :-)

Golfscript, 17 characters
{).,{.*1$<},,\;(}

I could name my function any way I liked, but I decided not to name it at all. Add two characters to name it, add three to name it and not leave it on the stack, subtract one character if providing a full program is OK.
This abomination runs not in logaritmic time in the value of the input, not in O(sqrt n) time, it takes a whooping linear amount of time to produce the result. It also takes that much space. Absolutely horrendous. But... this is code-golf.
The algorithm is:
n => [0..n].filter(x => x*x < n+1).length - 1

I love it!! Nice work! That is beautifully perverse.

Pyth, 14 characters
DsbR;fgb*TTL'b

Provides a named function, s, which calculates the square root by filtering the list from 0 to n for the square being larger than the input, then prints the last such number. Uses no exponentiation or floats.
Dsb       def s(b):
R;        return last element of
f         filter(lambda T:
gb*TT                     b>=T*T,
L'b                       range(b+1))

Example usage:
python3 pyth.py <<< "DsbR;fgb*TTL'b       \msd[0 1 2 3 4 8 9 15 16 65535 65536"
[0, 1, 1, 1, 2, 2, 3, 3, 4, 255, 256]

Retina (non-competing - Language is newer than the challenge), 43
While working on this answer, it occurred to me that a similar method can be used to calculate integer square roots using retina:
.+
$*
^
1:
+`(1+):(11\1)
1 $2:
1+:$|:1+

1+

This relies on the fact that perfect squares may be expressed as 1+3+5+7+..., and by corollary that the number of terms in this expression is the square root.
Try it online. (First line added to allow multiple testcases to be run.)
Obviously due to the decimal to unary conversion, this will only work for relatively small inputs.

(Language is newer than the challenge)

@mbomb007 Fair enough - Headline edited.  This answer is definitely in the "because it can be done" category, and not meant to compete in the challenge in any meaningful way.

I know what you mean.

Perl, 133 characters
Not the shortest by far, but uses a digit-by-digit algorithm to handle any size input, and runs in O(log n) time. Converts freely between numbers-as-strings and numbers-as-numbers. Since the largest possible product is the root-so-far with the square of a single digit, it should be able to take the square root of up to 120-bit or so numbers on a 64-bit system.
sub{($_)=@_;$_="0$_"if(length)%2;$a=$r="";while(/(..)/g){
$a.=$1;$y=$d=0;$a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for 1..9;$r.=$d;$a-=$y}$r}

Decompressed, that is:
sub {
  my ($n) = @_;
  $n = "0$n" if length($n) % 2; # Make an even number of digits
  my ($carry, $root);
  while ($n =~ /(..)/g) { # Take digits of $n two at a time
    $carry .= $1;         # Add them to the carry
    my ($product, $digit) = (0, 0);
    # Find the largest next digit that won't overflow, using the formula
    # (10x+y)^2 = 100x^2 + 20xy + y^2 or
    # (10x+y)^2 = 100x^2 + y(20x + y)
    for my $trial_digit (1..9) {
      my $trial_product = $trial_digit * (20 * $root + $trial_digit);
      if ($trial_product <= $carry) {
        ($product, $digit) = ($trial_product, $trial_digit);
      }
    }
    $root .= $digit;
    $carry -= $product;
  }
  return $root;
}

Nice! I was wondering when someone would post a Perl answer. BTW, does it work to say if length%2 instead of if(length)%2? That would shave off 1 character. Also, would it work to say $y=$z,$d=$_ if instead of ($y,$d)=($z,$_)if? I think that would shave off 3 more characters.

And this is getting a bit perverse, but I think you can shave off 1 more yet by rewriting the for loop as: $a<($z=$_*(20*$r+$_))or$y=$z,$d=$_ for(1..9);

The first suggestion doesn't work (it tries to take the length of a hash named %2), but the others are valid. I'll work them in.

@ToddLehman postfix for doesn't need parentheses; adding that to your suggestions nets me 6 characters total. Thanks!

Matlab (56) / Octave (55)
It works out the square root by using a fixed point method. It converges in maximal 36 steps (for 2^64-1 as argument) and then checks if it is the lower one of the 'possible' integer roots. As it always uses 36 iterations it has a runtime of O(1) =P
The argument is assumed to be uint64.
Matlab:
function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x=x-1
end

Octave:
function x=q(s)
x=1
for i = 1:36
    x = (x+s/x)/2
end
if x*x>s
    x-=1
end

This is a new method to me, and it happens to be pretty cool. +1

It is basically the https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method which is one of the earliest known numerical methods that is estimated to be around 3700 years old. It can be justified by the http://en.wikipedia.org/wiki/Banach_fixed-point_theorem which has a surprisingly easy proof, it's really nice=)

Ruby — 36 characters
s=->n{g=n;g=(g+n/g)/2 while g*g>n;g}

Nicely done! What is the worst-case execution time?

What about in the event that g*g < n and the answer is still not close to the value desired? Won't the script just stop?

@ToddLehman I honestly don't know. :-/ This is the Babylonian method. Here's what appears to be a good proof of the average complexity. The initial guess of the number itself is pretty bad, but I'd need to sit down and really grok that proof to understand the worst case. Will give it a go when I have some more free time. :-)

@WallyWest My understanding is that the while loop terminates precisely when g converges to floor(√n) which is the desired value. Do you see any case where this would not be true?

C99 (58 characters)
This is an example of an answer I would not consider to be a good one, although it's interesting to me from a code golf point of view because it's so perverse, and I just thought it would be fun to throw into the mix:
Original: 64 characters
uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return r-1;}

The reason this one is terrible is that it runs in O(√n) time rather than O(log(n)) time. (Where n is the input value.)
Edit: 63 characters
Changing the r-1 to --r and abutting it to return:
uint64_t r(uint64_t n){uint64_t r=1;for(;n/r/r;r++);return--r;}

Edit: 62 characters
Moving the loop increment to inside the conditional portion of the loop (note: this has unguaranteed behavior because the order of operations with respect to the preincrement operator is compiler-specific):
uint64_t r(uint64_t n){uint64_t r=0;for(;n/++r/r;);return--r;}

Edit: 60 characters
Adding a typedef to hide uint64_t (credit to user technosaurus for this suggestion).
typedef uint64_t Z;Z r(Z n){Z r=0;for(;n/++r/r;);return--r;}

Edit: 58 characters
Now requiring second parameter being passed as 0 in invocation of the function, e.g., r(n,0) instead of just r(n). Ok, for the life of me, at this point I can't see how to compress this any further...anyone?
typedef uint64_t Z;Z r(Z n,Z r){for(;n/++r/r;);return--r;}

If you are willing to call it C++ and decrement rather than increment you would be able to shave off a couple of characters: uint64_t s(uint64_t n){for(uint64_t r=n;--n>r/n;);return n;}.

@Fors — Nice approach! Unfortunately, won't that cause a divide-by-zero for input of 1? Also, what will it do for an input of 0? Because --n when n==0 would be –1, and these are unsigned values, so –1 would be 2⁶⁴–1.

#define Z uint64_t  ... or typedef will save a couple

@technosaurus — Ah yes, that saves 2. Thank you. :-)

The expression n/++r/r has undefined behavior....

@aschepler — Ya, it's definitely cheating. My compiler (Clang) warns about it. I'll make a note of it above.

Python (39)
f=lambda n,k=0:k*k>n and k-1or f(n,k+1)

The natural recursive approach. Counts up potential square roots until their square is too high, then goes down by 1. Use Stackless Python if you're worried about exceeding the stack depth.
The and/or idiom is equivalent to the ternary operator as
f=lambda n,k=0:k-1 if k*k>n else f(n,k+1)

Edit: I can instead get 25 chars by exploiting the rule "you may use *, /, +, -, and exponentiation (e.g., ** or ^ if it's a built-in operator in your language of choice, but only exponentiation of powers not less than 1)." (Edit: Apparently Dennis already found and exploited this trick.)
lambda n:n**1.5//max(n,1)

I use the integer division operator // of Python 3 to round down. Unfortunately, I spend a lot of characters for the case n=0 not to give a division by 0 error. If not for it, I could do 18 chars
lambda n:n**1.5//n

The rules also didn't say the function had to be named (depending how you interpret "You can name your function anything you like."), but if it does, that's two more characters.

— Thanks, I'll clarify that. It only has to be a function. It doesn't have to be named. So, lambda functions are fine. I would have mentioned this from the start if I'd thought of it. I was thinking too much in terms of C when I posted the question.

Haskell, 147 138 134 128 bytes
Not the shortest code in the world, but it does run in O(log n), and on arbitrary-sized numbers:
h x=div(x+1)2
n%(g,s)|g*g<n=(g+s,h s)|g*g>n=(g-s,h s)|0<1=(g,0)
f(x:r@(y:z:w))|x==z=min x y|0<1=f r
s n=fst$f$iterate(n%)(n,h n)

This does a binary search of the range [0..n] to find the best lower approximation to sqrt(n). Here is an ungolfed version:
-- Perform integer division by 2, rounding up
half x = x `div` 2 + x `rem` 2

-- Given a guess and step size, refine the guess by adding
-- or subtracting the step as needed.  Return the new guess
-- and step size; if we found the square root exactly, set
-- the new step size to 0.
refineGuess n (guess, step)
    | square < n  =  (guess + step, half step)
    | square > n  =  (guess - step, half step)
    | otherwise   =  (guess, 0)
    where square = guess * guess

-- Begin with the guess sqrt(n) = n and step size (half n),
-- then generate the infinite sequence of refined guesses.
--
-- NOTE: The sequence of guesses will do one of two things:
--         - If n has an integral square root m, the guess
--           sequence will eventually be m,m,m,...
--         - If n does not have an exact integral square root,
--           the guess sequence will eventually alternate
--           L,U,L,U,.. between the integral lower and upper
--           bounds of the true square root.
--        In either case, the sequence will reach periodic
--        behavior in O(log n) iterations.
guesses n = map fst $ iterate (refineGuess n) (n, half n)

-- Find the limiting behavior of the guess sequence and pick out
-- the lower bound (either L or m in the comments above)
isqrt n = min2Cycle (guesses n)
    where min2Cycle (x0:rest@(x1:x2:xs))
            | x0 == x2    =   min x0 x1
            | otherwise   =   min2Cycle rest

Edit: Saved two bytes by replacing the "otherwise" clauses with "0<1" as a shorter version of "True", and a few more by inlining g*g.
Also, if you are happy with O(sqrt(n)) you could simply do
s n=(head$filter((>n).(^2))[0..])-1

for 35 characters, but what fun is that?
Edit 2: I just realized that since pairs are sorted by dictionary order, instead of doing min2Cycle . map fst, I can just do fst . min2Cycle. In the golfed code, that translates to replacing f$map fst with fst$f, saving 4 more bytes.
Edit 3: Saved six more bytes thanks to proudhaskeller!

you can replace (div x 2 + rem x 2) with div(x+1)2, at your "half"  function

I actually have a solution of my own which has 49 characters, and solves in O(log n), but i only have 2 upvotes ;-(. I don't understand why

C# 64 62 55
Since this is a code-golf (and I'm terrible with maths), and runtime is merely a suggestion, I've done the naive approach that runs in linear time:
decimal f(ulong a){var i=0m;while(++i*i<=a);return--i;}

(test on dotnetfiddle)
Of course, it's terribly slow for larger inputs.

You might be able to shave off a character by changing return i-1 to return--i?

In the expression i*i<=a, is that guaranteed to be integer arithmetic of the usual type? (I'm not familiar with C#.) If so, and if C# allows implicit integer conversion to boolean like C does, then you might be able to save one more character by changing that to a/i/i.

@ToddLehman That actually happens to be fixed-point arithmetic (Decimal, higher max value and precision), to avoid the overflow since the multiplication result could potentially go one step past UInt64.MaxValue. But C# doesn't have implicit conversions to Boolean anyway. I should be able to change the return though, thanks. I'll do it when I get back to a computer.

C 95 97
Edit Typedef, suggested by @Michaelangelo
This should be more or less a straightforward implementation of Heron algorithm. The only quirk is in computing the average avoiding integer overflow: a=(m+n)/2 does not work for biiiig numbers.
typedef uint64_t Z;
Z q(Z x)
{
   Z n=1,a=x,m=0;
   for(;a-m&&a-n;) n=a,m=x/n,a=m/2+n/2+(m&n&1);
   return a;
}

Nice work with the overflow avoidance —— not only for correctly doing it, but taking care to think about it in the first place and test it. Definitely appreciated.

BTW, it's funny how expensive division can be on some CPUs. Even though this algorithm executes in roughly half as many steps as the abacus algorithm, it has a runtime that's about 5 times slower than the abacus algorithm when I benchmark it on my Core i7 CPU, which doesn't like doing division. Anyway, but runtime isn't important here — only size. :) So nice work!!!

Golfscript - 14 character
{.,\{\.*<}+?(}

Find the smallest number i less than the input n for which n < i*i.  Return i - 1.
I.e. [0..n-1].first(i => n < i*i) - 1
Explanation for those who don't know Golfscript as well, for sample call with input 5:
.        //Duplicate input.  Stack: 5 5
,        //Get array less than top of stack.  Stack: 5 [0 1 2 3 4]
\        //Switch top two elements of stack.  Stack: [0 1 2 3 4] 5
{\.*<}+  //Create a block (to be explained), and prepend the top of the stack.
         //Stack: [0 1 2 3 4]{5\.*<}
?        //Find the first element of the array for which the block is true.
         //So, find the first element of [0 1 2 3 4] for which {5\.*<} evaluates to true.
         //The inner block squares a number and returns true if it is greater than the input.
(        //Decrement by 1

Ooh, that's 3 characters shorter than the previous best Golfscript answer. Nice work!

Fixing this to give the correct answer for input 1 probably takes two chars.

JavaScript 91 88 86: Optimized for speed
function s(n){var a=1,b=n;while(Math.abs(a-b)>1){b=n/a;a=(a+b)/2}return Math.floor(a)}

JavaScript 46: Non optimized for speed
function s(n){a=1;while(a*a<=n)a++;return a-1}

Here is a JSFiddle: http://jsfiddle.net/rmadhuram/1Lnjuo4k/

Welcome to PPCG! You can use 91 88 for strikethrough. I tried making the edit but you were editing at the same time so I'll let you do it.

Or you could do it in 41 characters like this: function s(n){for(a=1;++a*a<n;);return a}

Clojure - 51 or 55 bytes
Checks all numbers from n to 0, giving the first one where x^2 <= n. Runtime is O(n - sqrt n)
Unnamed:
(fn[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Named:
(defn f[x](first(filter #(<=(* % %)x)(range x -1 -1))))

Example:
(map (fn[x](first(filter #(<=(* % %)x)(range x -1 -1)))) (range 50))
=> (0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 7)

Befunge 93 - 48 Bytes or 38 Characters
101p&02p>02g01g:*`#v_01g1-.@
        ^  p10+1g10<

Try it over here.

Ok, that is just cool. Nice work! I entered 17, clicked Creep and then Run, and it came up with 4! :)

Cobra - 62
do(n as uint64)as uint64
    o=n-n
    while o*o<n,o+=1
    return o

Batch - 74
set a=0
:1
set /ab=%a%*%a%
if %b% LSS %1 set /aa=%a%+1&goto 1
echo %a%

Haskell, 53 50 49 characters, O(log n)
s n=until((<=n).(^2))(\g->g-1-div(g^2-n-1)(2*g))n

this solution implements the newton-raphson method, although it searches integers instead of floats.
wiki: http://en.wikipedia.org/wiki/Newton%27s_method
the complexity seems to be about O(log n), but is there a proof of it? please answer in the comments.

\g->div(n+g^2)$2*g saves 7 bytes.

J (10)
Very, very, very inspired by the answer of @Dennis:
<.@%~^&1.5

And a slightly longer, but with better performance (I suspect):
<.@(-:&.^.)

floor(halve under log)
To execute, indented parts are input:
   f=:<.@%~^&1.5
   f 0 8 12 16
0 2 3 4
   g=:<.@(-:&.^.)
   g 0 8 12 16
0 2 3 4

How do you execute this for a given integer?

@Dennis See answer

APL - 12 chars, 19 bytes
{⌊(⍵*1.5)÷⍵}

example use:
{⌊(⍵*1.5)÷⍵}17

returns 4
Test vector
{⌊(⍵*1.5)÷⍵}¨0 1 2 3 4 8 9 15 16 65535 65536 18446744073709551615

returns
1 1 1 1 2 2 3 3 4 255 256 4294967296
Try Online
Big thanks to: user "ssdecontrol" for algorithm

Welcome to PPCG! We normally score APL as one byte per character. Unless the challenge specifies it, there is no need to count in UTF-8. Any existing encoding is fine, and there is an old APL codepage from back in the day which uses a single byte for each character. The fact that APL predates ASCII is a bad reason to penalise it for using non-ASCII characters. ;) (That said, this rather old challenge seems to score by characters anyway.)

@MartinEnder Thanks for the warm welcome and tips :)

0 → 1! Using Dyalog APL, you can set ⎕DIV←1 (which many use as default) to obtain the correct result.

C99 (108 characters)
Here is my own solution in C99, which is adapted from an algorithm in an article on Wikipedia. I'm sure it must be possible to do much better than this in other languages.
Golfed:
uint64_t s(uint64_t n){uint64_t b=1,r=0;while(n/b/4)b*=4;for(;b;b/=4,r/=2)n>=r+b?r+=b,n-=r,r+=b:0;return r;}

Partially golfed:
uint64 uint64_sqrt(uint64 n)
{
  uint64 b = 1, r = 0;
  while (b <= n / 4)
    b *= 4;
  for (; b; b /= 4, r /= 2)
    if (n >= r + b)
      { r += b; n -= r; r+= b; }
  return r;
}

Ungolfed:
uint64_t uint64_sqrt(uint64_t const n)
{
  uint64_t a, b, r;

  for (b = 1; ((b << 2) != 0) && ((b << 2) <= n); b <<= 2)
    ;

  a = n;
  r = 0;
  for (; b != 0; b >>= 2)
  {
    if (a >= r + b)
    {
      a -= r + b;
      r = (r >> 1) + b;
    }
    else
    {
      r >>= 1;
    }
  }

  // Validate that r² <= n < (r+1)², being careful to avoid integer overflow,
  // which would occur in the case where n==2⁶⁴-1, r==2³²-1, and could also
  // occur in the event that r is incorrect.
  assert(n>0? r<=n/r : r==0);  // Safe way of saying r*r <= n
  assert(n/(r+1) < (r+1));     // Safe way of saying n < (r+1)*(r+1)

  return r;
}

Suggestion: No need for a, use n.

Ah yes. Thank you. In my original version, I was maintaining n so that just before returning I could make the assertion (not shown) that r^2 <= n < (r+1)^2. With that assertion omitted, it's longer necessary to keep n intact.

@edc65 — Thanks again for pointing that out. I updated my code to reflect that, as well as added a couple other golf tricks. Also added the original assertions and made n const in the ungolfed version.

JavaScript 73 81 (to comply with 64-bit numbers requirement)
n=prompt();g=n/3;do{G=g,g=(n/g+g)/2}while(1E-9<Math.abs(G-g))alert(Math.floor(g))
Implementing Heron of Alexandria's algorithm...

Nice! Does this work for all unsigned 64-bit integer inputs?

Try as I might this only seems to work up to 32-bit... Much to my disappointment...

Surely the last |0 truncates any value to 32 bit. Using Math.floor instead?

@edc65 You're right actually, seems |0 affects up to 32-bit whereas Math.floor is more effective at 64-bit... I've updated my code, having to take an extra 8 characters in order to do so...

@edc65 I've just had a thought... would ~~x work in 64-bit?

No. All bits operation in js force a conversion to 32 bit. (~ >> >>> << | & ^)

Powershell (52) Limited to Int32 (-2,147,483,648 to 2,147,483,647)
function f($n){($n/2)..0|%{if($_*$_-le$n){$_;exit}}}

I'm screaming at Powershell right now trying to make the last test case work but no matter what I do Powershell winds up using the pipeline variable $_ as an Int32, and I can't find a way around it right now.
So I'll just limit my answer for now. If I can find a better way to handle uint64s I will edit. (The last test case is too big for Powershell's normal Int64 type, by the way!)
Here are a few test cases (with a bit of extra output I used to track the time)
f 17
4
Elapsed Time: 0.0060006 seconds

f 65
8
Elapsed Time: 0.0050005 seconds

f 65540
256
Elapsed Time: 1.7931793 seconds

f 256554
506
Elapsed Time: 14.7395391 seconds

I don't know my O()s, but this seems like a pretty dramatic jump.

Caveat: as of 2011, R had no built-in support for 64 bit integers as I had assumed it did. These answers might be invalid on that technicality, but then again R has changed a lot in the last 3 years.

R, 85
Using Newton's method:
function(n){s=F
x=n
y=(1/2)*(x+n/x)
while(abs(x-y)>=1){x=y
y=(1/2)*(x+n/x)}
trunc(y)}

which converges quadratically. +2 characters to assign the function to a variable for benchmarking:
microbenchmark(q(113424534523616))
# Unit: microseconds
#                expr    min      lq median      uq    max neval
#  q(113424534523616) 24.489 25.9935 28.162 29.5755 46.192   100

R, 37
Brute force:
function(n){t=0
while(t^2<n) t=t+1
t}

And the same check:
microbenchmark::microbenchmark(q(113424534523616),times=1)
# Unit: seconds
#                 expr      min       lq   median       uq      max neval
#   q(113424534523616) 4.578494 4.578494 4.578494 4.578494 4.578494     1

R, 30
The cheap/brilliant exponentiation trick:
function(n) trunc(n^(1.5)/n)

which also happens to be very fast (although not as fast as the built-in):
microbenchmark(q(113424534523616),sqrt(113424534523616))
# Unit: nanoseconds
#                   expr min    lq median    uq  max neval
#     z(113424534523616) 468 622.5  676.5 714.5 4067   100
#  sqrt(113424534523616)  93 101.0  119.0 160.5 2863   100

C, 38
f(n){int m;while(++m*m<=n);return--m;}

Translation of my Forth submission. Slow but correct. O(√n). Tested on OS X (64 bit).

dc, 50 bytes
dc -e"?dsist[lt2/dstd*li<B]dsBx[lt1+dstd*li!<A]dsAxlt1-f"

Spaced out and explained:
               # The idea here is to start with the input and reduce it quickly until it is
               # less than what we want, then increment it until it's just right
?              # Take input from stdin
d si st        # Duplicate input, store in `i' and in `t'
[              # Begin macro definition (when I write in dc, "macro"=="function")
 lt            # Load t, our test term
 2/            # Divide t by two
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li<B          # Load i; if i<(t^2), execute B
] d sB x       # Duplicate, store function as `B', and execute
               # Loop ends when t^2 is less than i
[              # Begin macro definition
 lt            # Load t, our test term
 1+            # Increment
 d st          # Store a copy of this new term in `t'
 d*            # Duplicate and multiply (square)
 li!<A         # Load i; if i>=(t^2), execute A
] d sA x       # Duplicate, store function as `A', and execute
               # Loop ends when t^2 == i+1
lt 1- f        # Load t, decrement, and dump stack

Uh, looks like the last test case crashes. I'll try to fix it.

Resolved. Now accepts very large input; serendipitously, the fix allowed me to remove some ugly code at the beginning.

C, 139 137 136 bytes
My first try at code golf. It looks like it's the shortest in C that fits the "efficient" requirement, as it runs in O(log n) time, using only addition and bit shifts. Though I'm sure it could be shorter yet...
It should work just fine for larger integer values too as long as the a=32 part is changed to a=NUMBITS/2.
typedef uint64_t x;x f(x o){x a=32,t=0,r=0,y=0,z;for(;a--+1;){z=(x)3<<2*a;y*=2;t++<r?y++,r-=t++:t--;t*=2;r*=4;r+=(o&z)>>2*a;}return y;}

Nice work! I haven't run it to test, but the code looks interesting. Is there a reason you wrote (t++) instead of just t++ in the assignment to r?

@ToddLehman Nope, just missed taking those out. Nice catch!

BTW, I love the a--+1 as a way to avoid writing a-- != UINT64_C(-1). Did you learn that trick somewhere or invent it yourself?

@ToddLehman Thanks! I figured that out myself.

C - 50 (61 without global)
typedef uint64_t T;T n,i;f(){while(++i*i<=n);--i;}

It use global variables as parameter and return value to save space.
No global version :
typedef uint64_t T;T f(T n){T i=0;while(++i*i<=n);return--i;}

I don't think using global variables is legal. At least tell how long it would be legitimately and provide a legitimate version

@proud haskeller Why would global variables be forbidden ?

@mantal because you must provide a runnable program/method.

@Marciano.Andrade the code is gave is runnable.

C++ 125
int main()
{
uint64_t y;cin>>y;
double x=y/2,d,z;
while((d=(x*x-y))>0.5)
{
d<0?x+=0.5:x-=0.5;
}
cout<<(uint64_t)x;
}

Nice! How about x+=(d<0)-0.5; ... saves 5 more characters?

BTW, this isn't (but should be) in the form of a function, as mentioned in the problem statement. (Okay, technically, yeah, main is a function, but it's not callable from inside a program like an f(y) would be.)

I think you can omit the innermost pair of parentheses and write while((d=x*x-y)>0.5) instead of while((d=(x*x-y))>0.5). Saves 2 more characters. :)

Every 0.5 can be changed to .5

Forth, 43
: f -1 begin 1+ 2dup dup * - 0< until 1- ;

O(√n)

GolfScript (15 chars)
Pick any one of
{):x,{.*x<},,(}
{:x,{).*x>!},,}
{.,\{1$)/<}+,,}
{,.,{1$)/<}+,,}

I've followed the other GolfScript answers in interpreting "You can name your function anything you like" as meaning "You may leave a block which does the job on the stack". These are currently the shortest GolfScript answers which correctly handle inputs 0 and 1.
Online demo

Yup, that sounds good! A block on the stack is fair game. As long as it's callable. Nice work!

JavaScript (ES6) 61 bytes
n=>n&&eval('g=n;while(Math.abs(g-(g=(n/g+g)/2))>1e-9);g-g%1')

Tests:

f=n=>n&&eval('g=n;while(Math.abs(g-(g=(n/g+g)/2))>1e-9);g-g%1')

console.log(f(0) == 0);
console.log(f(1) == 1);
console.log(f(2) == 1);
console.log(f(3) == 1);
console.log(f(4) == 2);
console.log(f(8) == 2);
console.log(f(9) == 3);
console.log(f(15) == 3);
console.log(f(16) == 4);
console.log(f(65535) == 255);
console.log(f(65536) == 256);
console.log(f(18446744073709551615) == 4294967296);

I hope you can excuse the last test, since JavaScript interprets the literal value 18446744073709551615 as 18446744073709552000. This is because JavaScript uses the IEEE 754 standard, which can only store every consecutive positive integer up to 9007199254740992 (2^53).
An alternative method that's even shorter is below. However, it does not meet the speed optimization requirements:
JavaScript (ES6) 30 bytes (non-competing)
n=>eval('for(a=0;a*a<=n;)a++')

Tests:

f=n=>eval('for(a=0;a*a<=n;)a++')

console.log(f(0) == 0);
console.log(f(1) == 1);
console.log(f(2) == 1);
console.log(f(3) == 1);
console.log(f(4) == 2);
console.log(f(8) == 2);
console.log(f(9) == 3);
console.log(f(15) == 3);
console.log(f(16) == 4);
console.log(f(65535) == 255);
console.log(f(65536) == 256);
// console.log(f(18446744073709551615) == 4294967296)

f=n=>eval('for(a=4294967290;a*a<=n;)a++')

console.log(f(18446744073709551615) == 4294967296);

The last test case hypothetically evaluates to true, but would take around a month to execute.

Dyalog APL, 8 bytes
⌊*∘1.5÷⊢

⌊n³⁄₂∕n⌋ as follows:
*∘1.5 the power-1.5 function
⊢ the pass-through function
(*∘1.5) ÷ ⊢ is the power-1.5 divided by the number itself
⌊ floor
Uses ⎕DIV←1 which often is default.
For the fun of it, here is a generalized solution that lets you calculate any root without raising to any power < 1:
⌊⊣(*÷⊣)(1+(÷⊢))

Swift 2, 43 bytes
let f={a in (0..<a).filter{$0*$0<=a}.last!}

Try here. There is a caveat - it won't compile unless the function is called, ie f(255), as type inference is unable to infer the return type.

Mathematica, 20
⌊#^1.5/1~Max~#⌋&

Pyke, 7 bytes (noncompeting)
#Xt)ltt

Try it here!
Finds the first number where i*i>=n and takes 2 from the number of numbers it had to check to get there

C++17, 80 bytes
auto f(auto n){auto x=1ul<<32,a=x-x;for(;x/=2;)a+=(a+x)*(a+x)<=n?x:0;return a;};

Explanation
This computes one bit per iteration, accumulating the result in a.
Tests
int main()
{
    return
        + (f(0) != 0)
        + (f(1) != 1)
        + (f(1) != 1)
        + (f(2) !=  1)
        + (f(3) !=  1)
        + (f(4) !=  2)
        + (f(8) !=  2)
        + (f(9) !=  3)
        + (f(15) !=  3)
        + (f(16) !=  4)
        + (f(65535) != 255)
        + (f(65536) != 256)
        + (f(18446744073709551615ul) != 4294967295)
        ;
}

I'm probably hugely missing something, but why is it x-x and not just plain 0? :)

It's a while ago now, but I think that using plain 0 rather than 0ul (or, equivalently x-x) caused the compiler to complain that it can't deduce auto (because a and x are not the same type).

Tellurium(non-competing), 8 bytes
@s|Iqg^`

This defines a function named s that converts input to an integer (I), calculates the square root (q) and rounds it to the floor (g)
The function can be called using =s.
Alternatively, 7 bytes
{Iqg^}f

This one defines an anonymous function that can be called using ä.

Lua, 74 bytes
n=io.read() if n==0 then print(0) os.exit() end print(math.floor(n^1.5/n))

Try it online!


text:
'Number' Crunching Benchmark
I just want to do some benchmarking of different programming languages. So here is a tip: You can use as many characters as you want. In the end there is only the time your program needed.
So, here is the Task:
Task
After searching for a good task that would require a lot of computation, I came up with the problem Is a word in a given Type-1 grammar?
For people not knowing what this is: Formal Grammar  Chomsky-Hierarchy
Maybe there is a better algorithm but I came only up with brute forcing.
So, write a code that brute forces the Grammars as fast as possible.
Rules

Parallel execution is allowed
Delete your cache after every tested word
Add your complete compiler command for optimized result
You can use any algorithm and language you want, as long as the job gets done.
Add to your answer what files are read/how to set the files that should be read.

I Guarantee

Input is always well formatted
Variables are always capital letters, Terminals always small ones
Words only consist of Terminals
No empty Word

Input
For equal footing we need to define what the input looks like. The input is a file. I write multiple grammars and words in one file. The structure can be described with following Pseudocode:
foreach(Grammar G) do
    write('{');
    foreach (Variable V in G) do
        write(T + ',');
    od
    deleteLast();
    write('}');
    linebreak();
    write('{');
    foreach (Terminal T in G) do
        write(V + ',');
    od
    deleteLast();
    write('}');
    linebreak();
    write('{');
    foreach(Production P in G) do
        write(P + ',');
    od
    write('}');
    linebreak;
    write(StartSymbol(G));
    linebreak;
    foreach(Word W for G) do
        write(W + ',');
    od
    deleteLast();
    linebreak;
od
deleteLastLinebreak();

An Example
Output
The output has to be put in a file as well. The formatting of the output does not matter. It should be recognizable which result belongs to which word.
An Example
Example
Here is an example written in C# by myself.
Main Class
Data Classes
Test System
The system the code will run on is following:

Arch Linux
RunTime you need (if available; Please add in answer)
Intel i7-4700MQ 3.4GHz
16GB RAM

How do I test
After the code is compiled I'll run a bash script that runs your program a certain amount of times and calculates the average and median run time.
Good Luck and may the best code win.
My Benchmark: Not completed after 8-9 hours of runtime.
My Benchmark (after changing some words):

mean: 39.5157
median: 39.448687194

PS: Here is the originally planned input, which took ages with my program. Grammars are slightly changed in the new input and words are way shorter.

Will you test submissions on fixed or random input? In the former case, minimum runtime is usually the better/fairer metric than average.

@MartinBüttner fixed, but I want to see what the average runtime is, because there is also other stuff running (OS for example). A minimum runtime test would be good if I'd have a dedicated machine for number crunching. Since I don't have one, the programs need to share the processor with other stuff, that varies in its needs...

That's exactly why I'd prefer minimum runtime. Any deviation from the minimum runtime is due to other stuff running. There is no variation in the amount of processor instructions that are carried out by each program, so any fluctuations in runtimes is due to other programs or the OS doing stuff in between. Hence, the closest you get to the true performance of the code is the minimum runtime. I don't think averaging is any fairer, because it only penalises programs where you happen to get an unrelated CPU spike during one of the runs.

@MartinBüttner following problem: my C# code (sequential) is currently running. I've started 8 hours ago. You can't have a run without spikes from other programs. And there is no way for controlling how often they happen. So, if I take the minimum runtime I could have run a program which was only interrupted 10-200 times per run and another was 50-100 times interrupted. The average might balance this deviation.

Another option would be the median to mitigate the effects of outliers.

@MartinBüttner I'll look at both...

But how do you decide a winner from both numbers?

@MartinBüttner one for each....

As the code is rather long, it can be found here (Java 8): http://pastebin.com/Q5Buuqfx
How I did it:
Instead of brute-force creating the possible word combinations and then try to find a match I instead did the reverse and tried to collapse the target word to find the starting point. As a result the path the algorithm has to traverse is much less branched, and the words from the example can all be verified in about 35 ms (on my machine).
As a side-effect of the reverse-search I do not need the first two lines of each task (variables, terminals).
In addition I utilize the Java 8 streaming technology, which allows to easily activate parallel processing with just a single change in one line of code.
Usage: java Grammar <inputFile>
Edit: Did some code cleanup and further speed tests and it ironically turned out, that the algorithm is so fast, that setting up the parallel stream takes longer than the actual task. I now use a single-CPU stream() instead and the complete example input set is processed in ~35 ms on my machine instead of ~80 ms if I use parallelStream().
Edit2: Further testing reveals some strange effects with parallelStream and certain types of Collections. A TreeSet seems to work best in both single and parallel processing. I did some tests on your extended input set and it seems to work fine, except for the task with the looping rules (CD->DC,DC->CD). Detecting and removing those would cause the search to verify instantly.

I'll run it as soon as I get home. I just arrived at work.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Where are the runs in this infinite string? (CCCCCC Found!)
Starting with the string ABC, consider the result of repeatedly appending the last half of itself to itself (using the larger half if the length is odd).
We get the progression:
ABC
ABCBC
ABCBCCBC
ABCBCCBCCCBC
ABCBCCBCCCBCBCCCBC
etc...

Let S represent the resulting infinite string (or sequence) that results as this procedure is repeated forever.
Goal
The goal in this code challenge is to find the index of the first occurrence of runs of C's in S.
It's easy at first: C first occurs at index 2, CC at 4, CCC at 7, CCCC at 26, but CCCCC is all the way at index 27308! After that my memory runs out.
The winner will be the submission that correctly generates the most run indices (in order, starting at C). You can use any sort of algorithm but be sure to explain it if you aren't using basic brute force. The input and output can be in any easy to understand format.
Important Note: I do not officially know whether or not S actually contains all runs of C's. This question is derived from this one on the Mathematics Stack Exchange, in which the author hasn't found CCCCCC either. I'm curious if anyone here can.  (That question is in turn based on my original question on the topic.)
If you can prove that not all runs of C occur in S then you will win automatically since this question will no longer be valid. If no one can prove that nor find CCCCCC then the winner will be the person who can get the highest lower bound on the index of CCCCCC (or whatever the largest unsolved run is if CCCCCC is found).
Update: Humongous kudos to isaacg and r.e.s. who have found CCCCCC at the astronomical index of 2.124*10^519. At this rate I can't imagine finding CCCCCCC with any method that relies on brute force. Good work guys!

I don't get it - You're saying you've found CCCCC at index 27308, but later it sounds like you don't know where it first occurs. Did you mean CCCCCC?

@isaacg Oops. 6 C's is the one that's hard to find. I'll fix that.

If the conjecture is wrong, there is a N for which c^N is the longest run. I'm pretty sure it should be possible to construct a longer sequence, leading to a contradiction and proving the conjecture. I also don't think it's too hard, but on the other hand problems can easily underestimated...

I am definitely coming back here at midnight with my new batch of votes - for both the question and the answers!

For those who are searching, this can make it a bit easier:
If you remove the first "A" then you only have to play with "AB" and you append half+1 for the next iteration.

CCCCCC found at 2.124*10^519.
Precise index is 2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215
Found by r.e.s., using the (old version of) code below, after 3.5 hours of searching.
Around that index, the string is: ...BCCBCBCCCBCCCCCCBCCB...
To verify, change the indicated line in the code below to start at 2946, instead of 5. Verification takes 20 seconds.
Update: Improved program. Old program searched ~10x more locations than necessary.
New version finds the CCCCCC in only 33 minutes.
How the code works: Basically, I only look at the regions which correspond to the ends of incremental strings, and calculate the letters by looking recursively back to the original string. Note that it uses a memo table, which may fill up your memory. Put a cap on the length of the memo table if necessary.
import time
import sys
sys.setrecursionlimit(4000)
ULIMIT=4000
end_positions=[]
current_end=2
while len(end_positions)<ULIMIT+3:
    end_positions.append(current_end)
    next_end=((current_end+1)*3+1)//2-1
    current_end=next_end
memo={}
def find_letter(pos):
    if pos in memo:
        return memo[pos]
    if pos<3:
        return 'ABC'[pos]
    for end_num in range(len(end_positions)-1):
        if pos>end_positions[end_num] and pos<=end_positions[end_num+1]:
            delta=end_positions[end_num+1]-end_positions[end_num]
            if len(memo)>5*10**6:
                return find_letter(pos-delta)
            memo[pos]=find_letter(pos-delta)
            return memo[pos]
time.clock()
for end_num in range(5,ULIMIT+1): # This line.
    diff = 1 # Because end_num is guaranteed to be a C
    while True:
        last_letter=find_letter(end_positions[end_num]+diff)
        if not last_letter=='C':
            break
        diff+=1
    if end_num%100==0:
        pos_str=str(end_positions[end_num])
        print(end_num,'%s.%s*10^%i'%(pos_str[0],pos_str[1:5],len(pos_str)-1),
        len(memo),diff,time.clock())
    if diff>=6:
        print(end_num,end_positions[end_num],diff,time.clock())

Current max searched to: 4000 iterations
CCCCCC found at iteration(s):
2946

This is Python right?

Yeah, I'll add that.

(+1) Your program, with sys.setrecursionlimit(4000) and
ULIMIT=4000, found (in about 3.5 hours on my system) the first occurrence of CCCCCC at index = 2.124*10^519. The exact index is in the next comment ...

2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215

Awesome! I never suspected it was so close to succeeding.

@r.e.s. I'll edit that into my answer, and verify it on my machine.

No wonder @Calvin'sHobbies ran out of memory. Basically useless information, but damn do I find it cool.

This is amazing you guys! This problem is more insane than I thought.

CCCCCC found at 2.124*10^519.
The following ruby code was used to search for CCCCCC.

SEARCH = 6

k = [5,3]

getc=->i{
  j=i
  k.unshift(k[0]+(k[0]+1)/2)while(k[0]<=j)
  k.each_cons(2){|f,g|j-=f-g if j>=g}
  "ABC"[j]
}

while true
  x=k[0]
  x-=1 while getc[x]=="C"
  x+=1
  l=1
  l+=1 while getc[x+l]=="C"

  break if l>=SEARCH
end

puts x
puts (x-14..x+l+13).map{|i|getc[i]}*""

The index is the same as in @isaacg's answer.
The runtime of above code for 6 is in the order of ten seconds on my computer. Nevertheless, it is still search for an answer for CCCCCCC (if you want to try it yourself set constant SEARCH to 7).
You can use getc to find the character at a specific position i as it is done in the last line where the string around the index is printed.

Good job speeding it up - my solution was very rough and unpolished.

Something weird: I've run the above code up to iteration #34000 after removing the break and changing the tests around a bit, and it only finds the one run of 6. Is this a problem with the code (I doubt it) or is it just an odd property of the sequence?

@isaacg Note that we only check on the breaks of each sequence and thus miss all the copy-sequences C^6. At the breaks those seem to be very rare - thus I think we won't see a C^7 soon.

I know, but since one was found on a sequence break after only 2946 iterations, I'd expect to see a second one by 40000 iterations, which is where I am now.

@isaacg You may use the (much much faster) code here: http://ideone.com/HoEKOB. Even with that I couldn't find another C^6 at a sequence point (even less a C^7).

Awesome! That's really far out there. I wonder why there's such a big gap,.

@isaacg The next one: C^6 @ 8.582*10^11815, after 67070 iterations. Can anyone run the code (http://ideone.com/HoEKOB) on a faster machine than my laptop :-)

Um, did you misprint the iteration number, or did you not change the index number in your previous comment?

Oh, also, how long did it take?

Only 1900 seconds. It finds the first C^6 after 400 milliseconds.

Impressive. That's something like 31500 times faster than the original code that found the first C^6.

I'm trying out the code on my desktop, we'll see if it's faster.

Alright, I found the second C^6, right where you said it was, but it took me 3900 seconds. I'm using my computer for a bunch of other tasks, though. Also, I got 67098 iterations, not 67070. Same index #, though.

Just FYI ... I ran your Java program with SEARCH=7 until it terminated (in about 18 hours) due to "java.lang.OutOfMemoryError: Java heap space". In that time it found nothing beyond the already-reported second "sequence point"-occurrence of C^6, which it had found in 4800 seconds.

@r.e.s. Just FYI: the 6th C^6 comes at iteration 177684 @ 1.45*10^31289.

Thanks ... What was the running-time for that? I notice that the number of times C^k occurs at sequence points, before the first occurence of C^(k+1), has so far been a non-decreasing sequence. E.g., C^5 occurs this way about 125 times before C^6 appears. This might suggest that C^7 won't appear until C^6 has occurred well over 125 times at sequence points. If there are only 6 of these occurrences in 177684 iterations, the first C^7 might indeed be inaccessibly waaaaay out there.

@r.e.s. It was at 51024 seconds. I only gave 4g heap memory to the jvm and the gc was already eating up 90% of the performance.

For a 3x faster Ruby program: in the while true loop, just change x=k[0] to x=k[0]-1 and delete the next two lines (the lines beginning with x-= and x+=). This works because every intermediate string ends in 'BC'.

(Not an answer, but too long for a comment.)
The following is a Python translation of @Howard's Ruby program (sped up by a factor near 3 by having only one getc in the search loop). On my system, this finds the first C^6 in 3 seconds. In 93 hours, it finds no C^7 in 231,000 iterations, so the first C^7 (if it exists) must occur after the leftmost 10^40677 positions in the infinite string.
import time

L = [5, 3]      #list grows "backwards" (by insertion on the left)

def getc(i):    #return the letter at index i
    while L[0] <= i: L.insert(0,L[0] + (L[0] + 1)//2)
    for k in range(len(L)-1):
        if i >= L[k+1]: i -= L[k] - L[k+1]
    return 'abc'[i]

def search(k):  #find the first occurrence of c^k
    start = time.time()
    iter = 0
    while True:
        iter += 1
        if iter % 1000 == 0: print iter, time.time()-start
        p = L[0] - 1
        l = 1
        while getc(p+l)=='c': l += 1
        if l == k: break
    return p, iter, time.time()-start

k = 6

(indx, iter, extime) = search(k)
print 'run length:', k
print 'index:', indx, '    (',len(str(indx)),'digits )'
print 'iteration count:', iter
print 'neighborhood:', ''.join([getc(i) for i in range(indx-1,indx+k+10)])
print 'execution time:', extime

With PyPy, it finds C^6 in less than a second on my machine.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
How much time will I need to unlock my Android phone?
Scenario
I am using pattern matching lockscreen and I sadly forgot my pattern. I would like to know how much time I will need to unlock it. Here are the specifications of Google's lock screen, that we will use for this challenge.

Every 5 wrong code, the user has to wait 30 seconds before any further entry.
A pattern must, at least, consist in 4 points (see below)
A point can be only used once, but you can go over it several times (see image right below):

Here, the center point is only used once, even if we go over it again for this particular pattern.
Hypothesis & Facts
We'll assume we're superheroes and that we can draw any pattern in 1 second, we never need to eat or sleep. Yeah, we're superhumans.
I'm a very unlucky person. "Worst case scenario" is my daily life so the pattern I will attempt last will be the right one.
What do we have to pwn?
For those who don't know it, Android (and other phones now) offers the ability of unlocking the phone through drawing a pattern on a 9-point matrix. This matrix can be described as follow :
C(A)  M(B)  C(C)
M(D)  X(E)  M(F)
C(G)  M(H)  C(I)

C standing for "corner point"
M for "middle point"
X for "center point"
I have given identifiers to the points to make it easier

The permitted direct connections are as follows :
Corner point :

Middle point :

Center point :

However, as pointed out by steveverrill, "once the centre has been used (and therefore becomes unavailable) a direct connection between the bottom left and top right corner becomes unambiguous and therefore possible". Same goes for every "middle point", if e.g. the point B has already been counted, then a direct connection between A and C is possible. If e.g. F has already been counted, then a direct connection between C and I is possible. Etc...
Rules

The point of this challenge is to return how much time (in human readable form, aka year/day/month/hour/whatever the time you find) I will need to unlock this damn phone.
You can't hardcode the number of possible valid patterns (don't even Google it, you fool), calculate it (that's actually the fun part, isn't it ?)
Shortest piece of code wins
Good luck !

What is the maximum pattern length (in moves not points)? Can each connection between two points only be traversed once?

Since there are 9 points, I would say 8 "moves" ;). And since a point can only count once, yes

I don't have Android, but I'd like to point out that your example appears to violate the permitted direct connections. I'm guessing that once the centre has been used (and therefore becomes unavailable) a direct connection between the bottom left and top right corner becomes unambiguous and therefore possible.

As a user of this lock screen, I'm almost entirely sure that with enough finger precision, you can connect any two unused points.

@Ourous: At least on my phone, if you move your finger around a dot to connect dots on either side of it, the dot in between is inserted into the sequence and counted as used anyway.

@steveverrill : You're right, I added a tip about that. I hope you don't mind I quoted you directly, since I thought it was a good explanation.

"You can't hardcode the number of possible valid patterns" is not an observable requirement.

Rebmu: 197 175 168 167 characters
Generates combinations as a series of numbers (ex. 12369 is top-left to top-right to bottom-right), checks if combination is valid, and increments a counter if it is. This might take a while* to run. Returns the number of seconds needed to unlock the phone.
B[[2 13][4 17][6 39][8 79][5 19][5 28][5 37][5 46][a 0]]Fdz[Q1feCb[st[a]paStsC/1 Qa^Qa^e?NNfiAtsC/2 e?NNfiArvTSc/2]]rpJ987653088[StsADj1233iA^e?SuqSf[++K]]adKmp30dvK 5

Unmushed and commented:
; for each subarray c:
; the sequences c/2 and c/3 are invalid before the point c/1 is pressed
; a 0 - a is never in the sequence, therefore 0 is always invalid
b: [[2 13] [4 17] [6 39] [8 79] [5 19] [5 28] [5 37] [5 46] [a 0]]
; checks (most) conditions of validity
f: dz[
    ; set q to 1
    q: 1
    ; foreach array in b as c
    fe c b [
        ; set a to be portion of s before c/1
        st [a] pa s ts c/1
        ; q = q and (a does not contain c/2) and (a does not contain reverse of c/2)
        q: a^ q
           a^ e? nn fi a ts c/2
              e? nn fi a ts rv c/2
    ]
]
; repeat 98765308 times, with j = 1 to 98765308
; 987653088 = 987654321 (largest valid combination) - 1234 (smallest valid combination) + 1
rp j 987653088 [
    ; set s to j+1233 (smallest valid combination - 1) as a string
    s: ts ad j 1233
    ; if f returns trues and s does not contain duplicates, increment k
    i a^ e? s uq s
          f
     [++ k]
]
; print k (number of combinations) + 30 * (k/5) -> number of seconds needed
ad k mp 30 dv k 5

The program loops from 1 to (987654321-1233), checking 1233+loop counter (therefore checking 1234 to 987654321).
If the number 987653088 is replaced with, 9876-1233 or 8643, then the program will find the time taken for all 4-point combinations.
Output for 9876-1233=8643 (4-point combinations):
>> rebmu %combinations.rebmu
== 11344

Output for 98765-1233=97532 (4 and 5-point combinations):
>> rebmu %combinations.rebmu
== 61426

Output for 987654-1233=986421 (4,5,6-point combinations):
>> rebmu %combinations.rebmu
== 243532

*4/5-point took me about 8 seconds to run; 4-6 took about 77 seconds. It might take ~24 hours or longer depending on who runs this to calculate number of combinations for 4-9 point combinations.


text:
Draw the Sawtooth Alphabet
A simple one today. Write the shortest program that draws a "sawtooth alphabet" given a positive integer for the height. You must write the name of your programming language when you come to the letter it starts with.
For example, if your language is Python and the input is 1 the output should be:
ABCDEFGHIJKLMNOPythonQRSTUVWXYZ

If the input is 2 the output should be:
 B D F H J L N Python R T V X Z
A C E G I K M O      Q S U W Y

If the input is 4 the output should be:
   D     J     Python     V
  C E   I K   O      Q   U W
 B   F H   L N        R T   X Z
A     G     M          S     Y

Notes

A always starts at the bottom left.
Input can be via stdin or function call or similar. Output to stdout.
Input above 26 doesn't need to work.
No trailing spaces.

Are programming languages with one letter names allowed? (C, J, K, etc.)

@isaacg Sure. I'd imagine it might be easier in them.

Can the input simply be expected to be stored in a variable?

@MartinBüttner Yes, that's fine.

How do answers deal with reduced terminal spaces (in other words, what can I do if the screen can't handle the width or height of the sawtooth)?

@DoktoroReichard Is there relly a terminal that can't fit 26 characters? No matter what, the output should still be the same as it would be when displayed on a large terminal. Its not your problem if a small terminal can't display it properly.

Btw, this isn't a sawtooth wave, this is a triangle wave :P

@qwr ...dang it

For one letter languages you could have used something like: Ah, Bee, Cee, Dee, Ee, Eff … Eks, Why, Zed.

Is it acceptable to use ANSI escape sequences to position the chars?

if n holds the height:
C + escape codes: 81
x;main(y){for(y=n--;x<26;x++)printf("\033[%d;%dH%c",n?x/n&1?y++:y--:y,x+1,x+65);}

C: 110
x;char a[702]={[0 ...701]=32};main(y){for(y=--n;x<26;a[x*27-1]=10)a[27*(n?x/n&1?y++:y--:y)+x]=x+++65;puts(a);}

I admit defeat. What on earth. :D

May I ask for compilation instructions? cc gives error "<bebe.c:1:17: error: ‘n’ undeclared (first use in this function)”.

well it is way worse than it looks. firstly the second one contains trailing spaces, secondly they both relies on that n is a global variable set to a number of your choice (as Martin has previously asked).

Oh, so I have to provide n in any way I can. Lol. Still impressed.

C, 134
n,m,c,p;
main(r){
for(scanf("%d",&n),m=--n?n*2:1;n+r--;puts(""))
for(c=-1,p=1;c++<25;)
p+=(c-n-r)%m*((c-n+r)%m)?1:1-printf("%*c",p,c+65);
}

Compiles on gcc with a few warnings. Newlines aren't included in the character count.
122 characters if the input is already stored in n.
Thanks to user2992539, tolos and edc65 for improvements.

You can use puts("") instead of printf("\n").

Save 4 characters with p-=(c-n+r)%m*((c-n-r)%m)?0:printf("%*c",p,c+65); instead of if((c-...

Sorry for previous (deleted) comment.I was wrong. Playing with signs and abusing the fact that the first argument of main is 1 if there are no parameters: 134 n,m,c,p; main(r){ for(scanf("%d",&n),m=--n?n*2:1;n+r--;puts("")) for(c=-1,p=1;c++<25;) p+=(c-n-r)%m*((c-n+r)%m)?1:1-printf("%*c",p,c+65); }

TI-BASIC - 148 bytes (raw text), 186 bytes (graphic)
In response to the OP, the wonderful TI-83 (and newer) comes with a size of 16 x 8 (just using the standard large text) or with a size of 94 x 62 pixels (which with small text is worth about 10 lines).
Now, this has a little problem (to which I would like clarification). The size impositions can't be "ignored" by the interpreter; in other words, if we were to try to set the sawtooth height at 20, it would give an error preventing the full execution of the code. I could write code that would, in an infinite environment, produce the correct output, except it wouldn't run on the machine.
With this being said, I present you the (running) versions of the programs. They all depend on the variable N being set to the desired height in lines before running:

Raw text approach
:ClrHome
:"ABCDEFGHIJKLMNOPQRSTI-BASICUVWXYZ"→Str1
:8→R
:For(C,1,16
:If N=1
:Then
:0→F
:Else
:If R<2 or 10-R>N
:1→F
:If R>7
:-1→F
:End
:If C≠20
:Then
:Output(R,C,sub(Str1,C,1
:Else
:Output(R,C,sub(Str1,C,8
:C+7→C
:End
:R+F→R
:End

In order to make this work regardless of the terminal, change For(C,1,16 to For(C,1,33 and remove the upper bound checking (R<2 or). Here is the output with 5→N:

Graphic approach (this may also need AxisOff for clarity)
:ClrDraw
:N*6→N
:"ABCDEFGHIJKLMNOPQRSTI-BASICUVWXYZ"→Str1
:57→R
:For(C,1,56
:If N=6
:Then
:0→F
:Else
:If R<7 or 64-R>N
:6→F
:If R>51
:-6→F
:End
:If C≠20
:Then
:If C>50
:Then
:Text(R,C,sub(Str1,C-23,1
:Else
:Text(R,C,sub(Str1,C,1
:End
:Else
:Text(R,C,sub(Str1,C,8
:C+30→C
:End
:R+F→R
:End

This one works OK, with two minor quirks. The height is still a problem, although the width isn't. However, I didn't space the letters, so in some cases (when the letter starts to rise or decline from the sawtooth), the letters may be chopped off by their successors. To make it work regardless of the terminal, remove the upper bound check (R<7 or). Then follows the graph:

Now I have to port this to my graphing calculator

Quick comment: Instead of 0→F you can do Delvar F which saves 1 byte once tokenized.
Also, I'm sure you can factor the Output/Text towards the end thanks to an inline boolean test condition for the coordinate, and for the C+7→C, write it in a short if (no then/else/end)

Pure Bash (no coreutils), 181 bytes
m=$1
for l in A Bash {C..Z};{
((m))||s=++
((m>$1-2))&&s=--
for((m=$1==1?1:m,m$s,i=0;i<$1;i++));{
((i-m))&&a[i]+=${l//?/ }||a[i]+=$l
}
}
shopt -s extglob
printf %s\\n "${a[@]%%+( )}"

Output:
Piped to cat -E just to prove there are no trailing newlines.
$ ./sawtooth.sh 1 | cat -E
ABashCDEFGHIJKLMNOPQRSTUVWXYZ$
$ ./sawtooth.sh 5 | cat -E
       E       M       U$
      D F     L N     T V$
     C   G   K   O   S   W$
 Bash     H J     P R     X Z$
A          I       Q       Y$
$

JavaScript (ES6) 231 244
Edit Bug fix, some reordering and a different way of managing height==1
Moreover, changed to a function as this is allowed by OP, so no prompt() for input
No changes to the general algorithm that probably is NOT the best for this challenge
F=h=>{for(p=s=[i=z=b=t=''];++p<h;)i=1,z=b=' ',s[p]=t;for(p=--h,k=64;++k<91;)s[p]+=t+String.fromCharCode(k),k-74||(s=s.map((x,q)=>x+(p-q?'         ':'avascript'))),p-=i,p<0|p>h?(i=-i,p-=i+i,t=z,b=t+t):t+=b;console.log(s.join('\n'))}

Explained
F=h=>{
  // row in s for output must be initialized to ''. In the same step I make other initializations
  for(p=s=[i=z=b=t='']; ++p < h;) // initialize for height 1, all increment and spacing can be null
    i=1,z=b=' ',s[p]=t; // the for body is entered only if height > 1, initializing spacing and increment to the right values
  for(p=--h,k=64;++k<91;)
    s[p]+=t+String.fromCharCode(k),
    k-74||(s=s.map((x,q)=>x+(p-q?'         ':'avascript'))), // if 'J' modify each line of output adding the name or spacing
    p-=i,p<0|p>h?(i=-i,p-=i+i,t=z,b=t+t):t+=b; // index bouncing
  console.log(s.join('\n'))
}

Examples
1
ABCDEFGHIJavascriptKLMNOPQRSTUVWXYZ

3 going up
  C   G            K   O   S   W
 B D F H Javascript L N P R T V X Z
A   E   I            M   Q   U   Y

4 on top
   D     Javascript     P     V
  C E   I          K   O Q   U W
 B   F H            L N   R T   X Z
A     G              M     S     Y

7 going down
      G                    S
     F H                  R T
    E   I                Q   U
   D     Javascript     P     V
  C                K   O       W
 B                  L N         X Z
A                    M           Y

Ruby, 112 bytes
o="#{' '*29}
"*h
26.times{|i|o[(h-i%(h<2?1:2*h-2)-1).abs*30+i+(i>17?3:0)]=(i+65).chr}
puts o.gsub('R   ','Ruby')

Expects the input to be stored in h.
Let me know if this needs clarification.

Very minor but you can remove the space after %.

@Calvin'sHobbies Ha, I didn't trust my syntax highlighting there :D. Will fix it later.

You can replace puts o... with $><<o....

JAVA (393)
As always a great language for golfing:
public class P{public static void main(String[]a){int h=Integer.valueOf(a[0]);String x="ABCDEFGHIJKLMNOPQRSTUVWXYZ";String[]l=new String[h];Arrays.fill(l,"");int i=h-1;int d=-1;for(char c:x.toCharArray()){for(int n=0;n<l.length;n++){String k=(n==i)?(c=='J')?"Java":c+"":(c=='J')?"    ":" ";l[n]+=k;}if(i==0&&d==-1)d=1;if(i==h-1&&d==1)d=-1;if(h>1)i+=d;}for(String s:l){System.out.println(s);}}}

Unfortunately, you forgot the import for java.util.Arrays;. :-(

But you can imporve your code: eliminate String x="ABC...Z"; and replace the for(char c... loop header with for (char c=65;++c<91;){, I love chars in Java=)

Further you can replace c=='J' with c==74, saves two more bytes in total.

I am sure you can do even better if you condense the if you use some XORs for those if statements, but here my improved version: (325) public class p{public static void main(String[]a){int h=Integer.valueOf(a[0]),i=h-1,d=-1,n;String[]l=new String[h];for(n=0;n<h;l[n++]="");for(char c=64;++c<91;){for(n=0;n<h;n++){String k=n==i?c==74?"Java":c+"":c==74?"    ":" ";l[n]+=k;}if(i==0&d==-1)d=1;if(i==h-1&d==1)d=-1;i+=h>1?d:0;}for(String s:l)System.out.println(s);}} @Quincunx: no more need for import.util.Arrays; =)

J : 75 bytes
NB. without IO |:26([:u:65+i.@[)`(($(,|.@}.@}:)@i.)<"1@,.i.@[)`(' '$~,~)}5
2(1!:2)~|.26([:u:65+i.@[)`(($(,|.@}.@}:)@i.)<"1@,.i.@[)`(' '$~,~)}".1!:1[1

Using the wonderful Amend conjunction. As usual the IO is ugly and clunky, not going into details there. The core solution takes 3 gerunds (a sort of noun-ified verb (aka. function)):

a) generating the alphabet
b) generating the indices
c) generating the matrix to make amends to
x (abc}) y

a) is a pretty trivial lookup in the ascii table
c) is even more trivial
b) is the interesting one. The morale is that the horizontal indices are supposed to be starting from 0 going to y-1 and back down, repeating this 26 times. Eg. for y == 4:
0 1 2 3 2 1 0 1 2 3 2 1 ...

Implementing this gives for b):
($(,|.@}.@}:)@i.) <"1@,. i.@[)       NB. is equivalent too
(tine0 tine1 tine2)                  NB. a fork with tines defined as
tine0 =:
  hook0 =: hook0_0 hook0_1           NB. a dyadic hook: x (g h) y -: x g h y
     hook0_0 =: $                    NB. reshape
     hook0_1 =: (hook1_0 hook1_1)@i. NB. do hook1 after making 0-y
       hook1_0=: ,                   NB. append to self
       hook1_1=: |.@}.@}:            NB. rotated version of y after beheading and curtailing
tine2 =: i.@[                  NB. generate 0-x
tine1 =: <"1@,.                NB. glue together coordinates.

And oh yea, handy fact: J's name is ... "J".

Is it worth to use amend?  It seems easier to me to say something like 3 :'|:(26$1+(i.1=y),}:|i:<:y)|.@{."+u:65+i.26' The ugly part in that solution is the 8 characters just to special case height 1, but this can probably be shortened a bit.

Thanks for the suggestion! Yours is indeed far shorter, and amend is probably overkill. Since it's so different, maybe you'd want to post it as a solution yourself?

The spec says "no trailing spaces" and my solution does print trailing spaces.

R (204)
f=function(x) {
  m=matrix(" ",x,26)
  i=x
  d=ifelse(x==1,0,-1)
  for (j in 1:26) {
    m[i,j]=LETTERS[j]
    if (!((i+d) %in% 1:x)) d=-d
    i=i+d
  }
  for (i in 1:x) cat(m[i,],"\n",sep="")
}

Result
> f(1)
ABCDEFGHIJKLMNOPQRSTUVWXYZ
> f(2)
 B D F H J L N P R T V X Z
A C E G I K M O Q S U W Y
> f(3)
  C   G   K   O   S   W
 B D F H J L N P R T V X Z
A   E   I   M   Q   U   Y
> f(7)
      G           S
     F H         R T
    E   I       Q   U
   D     J     P     V
  C       K   O       W
 B         L N         X Z
A           M           Y

I see what you did there! Very smart...

+1 Neat! You can get rid of the spaces around your for statements though (for(i in 1:x)cat(... for instance) or the one around %in%.

J, 67 57 61 characters
echo@dtb"1@|.@|:@(26&,$(u:65+i.26)#~1 j.26$(0#~1=]),<:#-&0 2)

Use as a function:
   echo@dtb"1@|.@|:@(26&,$(u:65+i.26)#~1 j.26$(0#~1=]),<:#-&0 2)
   D     J     P     V
  C E   I K   O Q   U W
 B   F H   L N   R T   X Z
A     G     M     S     Y

Explanation: this solution uses a different approach than the other J solution.  Instead of generating a sawtooth wave 0 1 2 3 2 1 0 1 ..., I looked at the spacing between consecutive letters.  For instance, for n=4 if you go from the A upwards, wrap over to the second column and reach B, then you find four spaces between A and B.  This pattern of spacing between letters is very regular: for n=4 the pattern is 4 4 4 2 2 2 4 4 4 ....
So the idea is to first build the flattened (and transposed) array, and then re-shape it and flip it so it look right.  The output routine is straightforward (for being J, at least): dtb is "delete trailing blanks" and "1 says "operate on each line".  dtb and echo are both provided by the standard library.
Thanks to Zsbán Ambrus for some golfing help.

48 byte solution.  This works in J 901 but not TIO (can't figure out why it's failing there).  And I'm pretty sure it could be golfed further too.

Javascript - 248 224 235
z=~~prompt(),y="ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("");y[9]="Javascript";for(w=[],v=0;v<z;v++)w[v]="\n";v--;for(i=0;i<26;i++){for(j=0;j<z;j++)w[j]+=j-v?i-9?" ":"          ":y[i];~~(i/(z-1))%2?v++:v--;}if(z==1)w=y;console.log(w.join(""))

Here is a link to the jsfiddle, where you can test it.
edit: Made a console log for a monospaced font and removed the commas if input==1.

Suggestions: 1: parseInt and Math.floor can be both changed with an integer coercing operation like |0 or ~~. 2: it's shorter to build the w array directly, without split. for(w=[],v=0;v<z;v++)w[v]="\n";

... and there is not an output statement (console.log or whatever you use in your fiddle, it's part of the char count)

@edc65 Thank you for the tips. You were right I forgot the output here so i added an alert, but there is no mono spaced font so it looks pretty chaotic.

@izlin Instead of (i==9?"          ":" ") you could use (i^9?" ":"          "), which saves a character.

HELP! can anyone explain? (Why is there twice v=0?)

@flawr It could be removed, nice observation.

The output for input 1 contains commas.

MetaPost (207)
numeric h,d,y;h=5;d=-1;y=1;u=5mm;pair p;string s;for x=1upto26:p:=(x,y)*u;s:=char(x+64);if x=13:s:="MetaPost";elseif x>13:p:=(x+2,y)*u;fi;label.rt(s,p);if(y=h)or(y=1):d:=d*-1;fi;if h=1:d:=0;fi;y:=y+d;endfor;

You can try it here.

Perl 119
$s.=/26/?++$r&&$/:$m-1&&$r-abs$_%(2*$m-2)+1-$m?$"x(1+3*/15/):/15/?Perl:(A..Z)[$_]for(0..26)x($m=<>);print$s=~s/\s+$//rg

This program takes input from STDIN and prints the result to STDOUT.
And bonus - a version that is against the rules as it prints trailing spaces, but adds some interaction:
#!/usr/bin/perl -p
$r=0;$_=join'',map{/26/?++$r&&$/:$m-1&&$r-abs$_%(2*$m-2)+1-$m?$"x(1+3*/15/):/15/?Perl:(A..Z)[$_]}(0..26)x($m=$_)

...and some tests below:
1
ABCDEFGHIJKLMNOPerlQRSTUVWXYZ
2
 B D F H J L N Perl R T V X Z
A C E G I K M O    Q S U W Y
4
   D     J     Perl     V
  C E   I K   O    Q   U W
 B   F H   L N      R T   X Z
A     G     M        S     Y
6
     F         Perl         Z
    E G       O    Q       Y
   D   H     N      R     X
  C     I   M        S   W
 B       J L          T V
A         K            U

Bash (213) (223)
read i
p=0
d=1
printf '\n%.0s' `seq $i`
for l in {A..Z}
do (($p==$i-1))&&((p=$p*-1))
(($i==1))&&p=0
(($p!=0))&&echo -en "\033[s\033[${p#-}A"
[[ "$l" == "B" ]]&&l="Bash"
echo -en $l"\033[s\033[${p#-}B"
((p++))
done

Minor tweaks and we're down to 213.
The original one had a minor bug. Tested and confirmed to work on bash version 4.2.37.
Thanks to @manatwork for pointing out the bug and some tips.

I edited your post by adding syntax highlighting to it, but now I see that it wrongly highlighted a part of your code as a comment, so I rolled it back. I just said this in case you were wondering why I rolled it back :)

@ProgramFOX That's alright. Thanks anyhow!

I think there is minor bug somewhere, as the output is slowly descending. (At least in Bash 4.3.) Some minor improvements to reduce the size to 194 characters: omit the sigil in arithmetic evaluation, do not try to double-quote inside double-quoted string: http://pastebin.com/zKa3zdwR

Can you use newlines instead of some of the ; just to make it a tiny bit more readable?  It won't affect your golf score

Javascript (204 185 150 145)
h=m=4;d=h>1?-1:0;o=[];for(a=0;a<35;a++){for(r=h;r;r--)o[r]=(o[r]||"")+(r==m?"ABCDEFGHIJavascriptKLMNOPQRSTUVWXYZ"[a]:" ");if(a<9||a>17){m+=d;if(m<2||m==h)d=-d}}console.log(o.join("\n"))

EDIT
Saved 13 bytes by not building an array and .join("\n"). Required flipping the for loops. Then, with help from C coding son, made code entirely too clever to save another 12 bytes.
Here is the readable version showing the logic change.
for (row = height; row; row--) {
    rowOfNextActiveLetter = 1;
    direction = height > 1 ? -1 : 0;
    output = "";
    for (a = 0; a < 35; a++) {
        output += (row == rowOfNextActiveLetter ? "ABCDEFGHIJavascriptKLMNOPQRSTUVWXYZ"[a] : "");
        if (a < 9 || a > 17) {
            rowOfNextActiveLetter -= direction;
            if (rowOfNextActiveLetter < 2 || rowOfNextActiveLetter == height)direction = -direction
        }
    }
    console.log(output)
}

Golfed (161):
for(r=h;r;r--){m=1;d=h>1?-1:0;o="";for(a=0;a<35;a++){o+=(r==m?"ABCDEFGHIJavascriptKLMNOPQRSTUVWXYZ"[a]:" ");if(a<9||a>17){m-=d;if(m<2||m==h)d=-d}}console.log(o)}

Golfed and obfuscated (149):
for(r=h;r;r--,console.log(o))for(m=1,d=h>1?1:0,o="",a=0;a<35;)if(o+=r==m?"ABCDEFGHIJavascriptKLMNOPQRSTUVWXYZ"[a]:" ",a<9|a++>17)d=(m+=d)<2|m==h?-d:d

Reversed Alphabet and loop (145):
for(r=h;r;r--,console.log(o))for(m=d=1,o="",a=35;a;)if(o+=" ZYXWVUTSRQPONMLKtpircsavaJIHGFEDCBA"[r==m?a:0],a<18|a-->26)d=h<2?0:(m+=d)<2|m==h?-d:d

I like it even if I don't understand it full. But anyway you can cut 9 chars removing substr and using direct index .substr(a,1) => [a]

You can narrow it further by using bitwise operators and coalescing iterators for 182:
h=m=4;d=1<h?-1:0;o=[];for(a=0;35>a;a++){for(r=h;r;r--)o[r]=(o[r]||"")+(r==m?"ABCDEFGHIJavascriptKLMNOPQRSTUVWXYZ"[a]:" ");if(9>a|17<a)if(m+=d,2>m||m==h)d=-d}console.log(o.join("\n"))

whoops, cleaned up one too many spaces

C#/LINQ:
using System;
using System.Linq;

namespace SawtoothAlphabet
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Int32.Parse(args[0]);   // eg 4
            Console.WriteLine(
                String.Join(Environment.NewLine, Enumerable.Range(0, N).Select(line =>
                    String.Concat(Enumerable.Range(0, 26).Select(i =>
                        line == Math.Abs(i % (2 * (N - 1)) - (N - 1))
                            ? (i == 2) ? "C#" : Char.ConvertFromUtf32(i + 'A')
                            : (i == 2) ? "  " : " ")
            ).TrimEnd())));
        }
    }
}

Brief explanation: Enumerable.Range(0, N).Select(...) causes a string to be generated for each line which is eventually concatenated into a single string with String.Join(Environment.NewLine, ...). For each line we cycle through all 26 characters with Enumerable.Range(0, 26).Select(...), the test at the start of the lambda expression determines whether to generate a character or space while the i==2 checks for "C" and converts it to either "C#" or two spaces depending on the line. The String.Concat(...) converts the resulting IEnumerable<char> for each line into a string before passing it to TrimEnd(...) to cleanly strip away any trailing whitespace.

Haskell – 432 Bytes (unfortunately...)
This turned out to be much harder than I expected to accomplish purely, hence the hefty byte count. I am sure I (or someone) could do better, but I've spent too much time on this as it is. The golfed version is as follows:
import Data.Matrix
import Data.Vector(toList)
r=repeat
s h=y h$l(take 26(case h of 1->r 1;_->concat$r$[h,h-1..1]++[2..h-1]))['A'..'Z']$matrix h 32(const ' ')<|>matrix h 1(const '\n')
l _[]m=m
l(x:i)(r:e)m=l i e$u m(let z=26-length i in if z<9 then z else z+6)x r
l _ _ m=m
u m c r h=case h of 'H'->t c r"Haskell"m;_->setElem h(r,c)m
t _ _[]m=m
t c r(x:i)m=t(c+1)r i$setElem x(r,c)m
y h m=concat[toList$getRow x m|x<-[1..h]]

To run, load the code into ghci and execute putStr $ s Int where Int is your desired height. You could also add
import System.Environment
main :: IO ()
main = fmap (s . read . head) getArgs >>= putStr

under the imports in a text file, compile it with ghc, and pass the height as a command line argument. Ungolfed version:
import System.Environment
import Data.Matrix
import Data.Vector (toList)

main :: IO ()
main = fmap (sawtooth . read . head) getArgs >>= putStr

type M = Matrix Char

sawtooth :: Int -> String
sawtooth height = let mat     = matrix height 32 (const ' ') <|> matrix height 1 (const '\n')
                      numbers = take 26 (case height of 1 -> repeat 1
                                                        _ -> concat $ repeat $ [height,height-1..1]++[2..height-1])
                      chars   = ['A'..'Z']
                  in toString height $ makeMatrix numbers chars mat

makeMatrix :: [Int] -> String -> M -> M
makeMatrix []     []     mat = mat
makeMatrix (x:xs) (s:ss) mat = makeMatrix xs ss $ updateMatrix
                                                    mat (let z = 26 - length xs in if z < 9 then z else z + 6) x s
makeMatrix _      _      mat = mat

updateMatrix :: M -> Int -> Int -> Char -> M
updateMatrix mat col row char = case char of 'H' -> insertHaskell col row "Haskell" mat
                                             _   -> setElem char (row, col) mat

insertHaskell :: Int -> Int -> String -> M -> M
insertHaskell _   _   []     mat = mat
insertHaskell col row (x:xs) mat = insertHaskell (col+1) row xs $ setElem x (row, col) mat

toString ::Int -> M -> String
toString height mat = concat [ toList $ getRow x mat | x <- [1..height] ]

I believe you can replace const with pure (using the Applicative instance for functions) to save a few bytes.

K, 60 bytes
`0:'{+{x!y}.'+(26#{(!x),|1_!x-1}x;(((x-1)#" "),)'`c$65+!26)}

Pretty straightforward, and it looks like I just edged out the J solution. :)
First, generate an alphabet:
  `c$65+!26
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"

And a sawtooth wave of an appropriate length:
  26#{(!x),|1_!x-1}5
0 1 2 3 4 3 2 1 0 1 2 3 4 3 2 1 0 1 2 3 4 3 2 1 0 1

Pad each letter of the alphabet with leading spaces:
  (((5-1)#" "),)'"ABC"
("    A"
 "    B"
 "    C")

Zip the alphabet and the square wave together, and rotate each row:
  +(0 1 2;("  A";"  B";"  C"))
((0
  "  A")
 (1
  "  B")
 (2
  "  C"))

  {x!y}.'+(0 1 2;("  A";"  B";"  C"))
("  A"
 " B "
 "C  ")

And the transposition of that is our answer:
  +{x!y}.'+(0 1 2;("  A";"  B";"  C"))
("  C"
 " B "
 "A  ")

Try it here in oK.

C, 214 169 bytes, no trailing spaces
Thank to @edc65 and @tolos for their helpful suggestions.
#define C ((c-i+n-65)%z&&(c+i+n-67)%z)
n,i,m,c,z;main(){scanf("%d",&n);z=n<2?1:2*n-2;for(;i++<n;){for(m=c=64;c++<90;)m=C?m:c;for(c=64;c++<m;)putchar(C?32:c);puts("");}}

It's a lost battle, but I persist: #include <stdio.h> is not needed in many cases, be it gcc or any other compiler. It's standard and valid C anyway.

@edc65: Depends on what you consider "valid C". It is AFAIK valid K&R C, but ANSI/ISO C demands that variadic functions (which include scanf and printf) are given prototypes, otherwise you'll get undefined behaviour. #include <stdio.h> is, of course, the shortest way to give a prototype to both scanf and printf.

@celtschk valid K&R is enough for me in code golf. And 'in many cases' (when just using puts for instance) is valid C89. What I want stress out is that is not a strange behaviour of gcc. (Thks for the note about variadic functions, anyway)

Globals are type int and initialized to zero. Might as well drop int declaration for main if you aren't returning anything. Can drop extra parens, replace ' ' with 32 and if(!C)m=c with a ternarny statement, and as I just learned (above) replace printf("\n") with puts("") for 18 characters: n,i,m,c,z;main(){;scanf("%d",&n);z=n<2?1:2*n-2;for(;i<n;i++){for(m=c=65;c<91;c++)m=C?m:c;for(c=65;c<=m;c++)printf("%c",C?32:c);puts("");}}

PHP (216) (205)
New version:
$b=array_fill(65,26,' ');$b[80]='   ';$b=array_fill(0,$i,$b);for($j=--$i,$x=64;++$x<91;$i||$j=0){$b[$j][$x]=chr($x);$x==80&&$b[$j][$x]='PHP';$j+=($d=$j<($d?$i:1))*2-1;}echo join("\n",array_map('join',$b));

Old version:
$b=array_fill(0,$i,array_fill(0,28,' '));for($j=--$i,$x=-1;++$x<28;$i||$j=0){$q=&$b[$j];$q[$x]=chr($x-($x&16)/8+65);$x==15&&($q[++$x]='H')*$q[++$x]='P';$j+=($d=$j<($d?$i:1))*2-1;}echo join("\n",array_map('join',$b));

expects the variable $i to be the height.

Perl 5 + -p, 79 bytes
Not the shortest, and I think there's a chance this isn't valid (as it uses ANSI escape sequences to position the letters...) - happy to remove if this is deemed invalid.
//;$_=$/x$_;$|-=++$-<$'?0:($-=1),$\.=$_.($|?".":".[A")x($'>1)for A..O,Perl,Q..Z
Try it online!
Explanation
The initial // is purely to store the current value of $_ in $' so $_ can be used in the body of the loop, saving a variable assignment. Then $_ is set to $/ (newline) $_ times, to move the cursor down the screen.
The main body of the program is the for loop that iterates over the alphabet, replacing P with Perl as a bareword. $| can be used as a binary toggle when decremented so if the post-incremented $- is less than $', subtract nothing, keeping the value the same, otherwise, set $- to 1 and decrement that. Next, append to $\ (which is automatically output after $_ at the end of the program thanks to -p) the current letter ($_ - implicitly set by the for loop) with if $| is truthy, form feed (to move the cursor down a line) otherwise \x1b[A to move the cursor up one line, $'>`` times. This last condition is to satisfy the requirement of input 1` being a straight line and feels the most out of place in the answer...

Python - 137
Input to be stored in i. e.g. i=8
l=[""]*h;k=j=0;y=h-1;exec'l[y]+=" "*(j-len(l[y]))+chr(k+65)+"ython"*(k==15);j=len(l[y]);y-=1^k/(h-(h>2))%2*-2;k+=1;'*26;print"\n".join(l)

C: 142 139 characters
Dreadfully long, I expect to be able to shorten it a bit:
char a[26][27],i,j,p,d;main(n){for(scanf("%d",&n);i<26;d^=!p^p+2>n,p+=d-(d^n>1),i++)for(j=n;j--;a[j][i]=p^j?32:i+65);while(n)puts(a[--n]);}

Slightly more readable:
char a[26][27], i, j, p, d;
main(n) {
    for (
        scanf("%d", &n);
        i < 26;
        d ^= !p ^ p + 2 > n,
        p += d - (d ^ n > 1),
        i++
    )
        for (
            j = n;
            j--;
            a[j][i] = p ^ j
                ? 32
                : i + 65
        );

    while (n)
        puts(a[--n]);
}

Edit: I missed the "no trailing spaces"-rule, but I will be back.

Scala, 246 bytes
def f(h:Int)={val a=Seq.fill(h)(Array.fill(32)(' '));var(r,x,d)=(h-1,0,if(h==1)0 else-1);def p(c:Char){a(r)(x)=c;x+=1};for(c<-'A'to'Z'){p(c);if(c==83)"cala"foreach p;r+=d;if(r==0|r==h-1)d*= -1};for(z<-a)println(new String(z)replaceAll(" +$",""))}

reformatted and commented:
def f(h: Int) = {
  val a = Seq.fill(h)(Array.fill(32)(' '));
  // r - row; x - x coordinate, column; d - direction
  var (r, x, d) = (h - 1, 0, if(h==1) 0 else -1);
  def p(c: Char) { // p for "put the character"
    a(r)(x) = c;
    x += 1
  };
  for(c <- 'A' to 'Z') {
    p(c);
    if(c == 83)      // 83 == 'S'
      "cala" foreach p;
    r += d;
    if(r == 0 | r == h - 1)     // | is shorter than ||
      d *= -1
  };
  for(z <- a)
    println(new String(z) replaceAll (" +$", ""))  // trimming trailing whitespace
}

Results:
scala> f(4)
   D     J     P         V
  C E   I K   O Q       U W
 B   F H   L N   R     T   X Z
A     G     M     Scala     Y

scala> f(5)
    E       M           U
   D F     L N         T V
  C   G   K   O   Scala   W
 B     H J     P R         X Z
A       I       Q           Y

scala> f(1)
ABCDEFGHIJKLMNOPQRScalaTUVWXYZ

Racket
Here's a clean functional version: suggestions to shorten it welcome.
(define (sawtooth n)
  (define (ST i d m lns)
    (if (null? m)
        lns
        (let* ([v (first m)]
               [spc (make-string (string-length v) #\space)]
               [I (+ i d)])
          (ST I
              (if (or (zero? I) (= (sub1 n) I)) (* d -1) d)
              (rest m)
              (for/list ([ln lns] [j n])
                       (~a ln (if (= i j) v spc)))))))
  (displayln
   (string-join
    (ST (sub1 n)
        (if (= n 1) 0 -1)
        (string-split "A B C D E F G H I J K L M N O P Q Racket S T U V W X Y Z")
        (make-list n "\n")))))

Output
> (sawtooth 1)
ABCDEFGHIJKLMNOPQRacketSTUVWXYZ

> (sawtooth 2)
 B D F H J L N P Racket T V X Z
A C E G I K M O Q      S U W Y

> (sawtooth 8)
       H                  V
      G I                U W
     F   J              T   X
    E     K            S     Y
   D       L     Racket       Z
  C         M   Q
 B           N P
A             O

JavaScript, 168 bytes
f=(n,o=0,a=[...Array(n)])=>o<26?f(n,o+1,a.map((s='',i)=>s+(o-9?String.fromCharCode(65+o):'JavaScript').replace(i*i-(o%(2*n-2)-n+1)**2&&/./g,' '))):a.map(s=>s.trimEnd())

Try it online!
Returns an array of lines.
Ungolfed and explained:
f = (
  n,                 // input
  o = 0,             // offset for recursion (current step)
  a = [...Array(n)]  // array containing output lines
) =>
  o < 26 ?    // if not at end yet
    f(        // call function again
      n,      // with same input
      o + 1,  // increment offset
      a.map((s = '', i) =>  // add next letter to each line of a
        s +                 // current line
        (
          o - 9 ?                          // if letter is not J
            String.fromCharCode(65 + o) :  // current letter
            'JavaScript'                   // else 'JavaScript'
        ).replace(
          // replace with spaces if not at a triangular wave point
          i != Math.abs(o % (2 * n - 2) - n + 1) &&
          /./g, ' '
        )
      )
    ) :
    a.map(s => s.trimEnd())  // return array with trailing spaces removed

Scala, 332 bytes
Golfed version. Try it online!
object P extends App{val h=args(0).toInt;val x="ABCDEFGHIJKLMNOPQRSTUVWXYZ";val l=Array.fill[String](h)("");var i=h-1;var d= -1;for(c<-x.toCharArray){for(n<-l.indices){val k=if(n==i){if(c=='S')"Scala"else c.toString}else{if(c=='S')"    "else" "};l(n)+=k};if(i==0&&d== -1)d=1;if(i==h-1&&d==1)d= -1;if(h>1)i+=d};for(s<-l){println(s)}}

Ungolfed version. Try it online!
object P extends App {
  val h = args(0).toInt
  val x = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  val l = Array.fill[String](h)("")
  var i = h - 1
  var d = -1
  for (c <- x.toCharArray) {
    for (n <- l.indices) {
      val k = if (n == i) {
        if (c == 'S') "Scala" else c.toString
      } else {
        if (c == 'S') "    " else " "
      }
      l(n) += k
    }
    if (i == 0 && d == -1) d = 1
    if (i == h - 1 && d == 1) d = -1
    if (h > 1) i += d
  }
  for (s <- l) {
    println(s)
  }
}

authors: 娱乐天地娱乐代理--平台总代

authors: 恒行2娱乐代理--平台总代

authors: 摩登5娱乐代理--平台总代

authors: 洲际娱乐代理--平台总代

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/