@BatCoder Here we get the LSB of n
and set it to m
. On each iteration, we leftshift m
by 1 position. The LSB's of n
become MSB's of m
. This reverses the order of bits. HTH!
skylake26
@skylake26
Posts made by skylake26

RE: My 3ms pure C solution

RE: 34 short lines, Integer Newton, Every Language
@StefanPochmann
i) Output  The program outputs the number of iterations required to calculate the floor of sqrt(x)
ii) To isolate the run time of Newton method, I ignored the cost of generating the seed.
iii) Difficult to prove mathematically this takes constant (atleast for me : /). How do we prove that this will converge after max k iterations? Any ideas?
iv) The base does not matter. I was trying to convey that, if we initialize a seed close to the actual neighborhood of sqrt(x), then the convergence will happen in constant time. This is because we ignore the precision.
v) f(x) = e^x has no derivative defined at f(x)=0. Hence discontinuous derivative. I was trying to convey that there are lot of peculiar functions where Newton method will not converge. 
RE: 34 short lines, Integer Newton, Every Language
Disclaimer: i) Long read ii)Answer based on research of online math articles
For
f(x) = x*x
, the Newton method will always converge given any starting point x>0.
However, there are certain functions where the NewtonRaphson method will fail to converge (discontinuous derivative). Ex:f(x) = e ^ x
.In general, the timecomplexity for ndigit precision of f(x) is O((log n) * F(n)) where F(n) is cost of computing f(x)/ f'(x). In this case, since we are not worried about precision, we are guaranteed to converge after k iterations. Hence, I believe here the time complexity is constant.
Now, the solution above is logarithmic since we have a inefficient seed. The choice of seed = n makes the convergence logarithmic rather than constant time. A better seed will make it constant. If number
N = a * 10 ^ 2n
, a good seed can beS = a * 10^n
A slightly modified version of @StefanPochmann version
#include<iostream> #include<climits> using namespace std; int mySqrt(int x) { int temp = x,count = 0, iterations = 0; long long r = 1; //loop 1 while(temp > 10){ temp /= 10; count++; if(count %2){ r *= 10; } } r *= temp; while (r*r > x){ r = (r + x/r) / 2; iterations++; } cout << "Number: " << x << " Iterations: " << iterations << endl; return r; } int main() { for (long long x=1; x<=INT_MAX; x*=2) { long long r = mySqrt(x); } cout << "all checked" << endl; }
If we discard the iterations for while loop 1, then we can see this is constant time.
Here are a few good resources [1], [2] , [3].

RE: Share my clean accepted C++ Solution without long type or magic number
Nice solution. We do not need the second part of the OR condition. Just
rx > INT_MAX / 10
is sufficient to check for overflow. 
RE: 3 methods for python with explains
@bmay Modulo properties
 associative over + : (a + b)%m = (a % m) + (b%m)
 For * : (a * b)%m = ((a % m) * (b%m)) % m
 (a % m)%m = (a % m)
Applying this to N=(a[0] * 1 + a[1] * 10 + ...a[n] * 10 ^n)
N % 9 = (a[0] * 1 + a[1] * 10 + ...a[n] * 10 ^n) % 9
N % 9 = (a[0] * 1) % 9 + (a[1] * 10)%9 + ... + (a[n] * 10 ^n) % 9
N % 9 = ((a[0] %9) * (1 % 9)) % 9 + ((a[1] %9) * (10 %9))%9 + ... + ( (a[n] %9) * (10 ^n % 9)) % 9Note that 10^k % 9 = 1, that simplifies
N % 9 = ((a[0] %9) ) % 9 + ((a[1] %9))%9 + ... + ( (a[n] %9)) % 9
N % 9 = (a[0] ) % 9 + (a[1])%9 + ... + ( a[n] ) % 9Note that a[i]<10, so a[i] % 9 = a[i], thus
N % 9 = (a[0] + a[1] + ..a[n])