I have only read the first paragraph, and the following glitch may not matter, but suppose N=11. The integer square root of this is 3, so I set R=3 and peel off 3 chunks of three. I'm left with the final chunk being 4, which is *not* smaller than R as claimed. I have no clue yet whether this cooks the algorithm; I'm reading on.
--Actually 11=3+3+3+2 not 3+3+3+4, but use 14=3+3+3+5 and you're right. Sorry for that bug. No, it does not cook the algorithm since the leftover chunk is never more than about twice as large as the other chunks, which is good enough. (Also, even if it were way larger that still would not matter if the leftover chunk were handled recursively.) Another minor bug is, my final time bound should have had another log factor in it -- log^3 not log^2 --, due to the binary search.